🐢 5. Sorting

🫧 버블 정렬 (Bubble Sort)

: 바로 가까이에 있는 두 숫자끼리 비교를 해서 당장

더 작은 숫자를 앞으로 보내주는 것을 반복

구현은 쉽지만 가장 비효율적인 알고리즘

실행 수행시간 가장 느리다

버블 정렬의 시간 복잡도는 N^2

#include <stdio.h>

int main(void) {
	int i, j, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for (i = 0; i< 10; i ++) {
		for (j = 0 ; j< 10; j++){
			if (array[j] > array[j+1]) {
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
			}
		}
}
	for (i = 0; i<10; i++) {
		printf("%d " , array[i]);
	}
	return 0;
}
// 1 2 3 4 5 6 7 8 9 10

🫧 병합 정렬 (Merge Sort)

: 분할 정복 방법을 채택한 알고리즘

퀵 정렬과 동일한 시간 복잡도 가짐

퀵 정렬은 피벗 값에 따라 편향되게 분할됨

병합 정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 N*logN 보장

피벗 값이 없고 항상 반으로 나눈다

이 단계의 크기가 logN이 되도록 만들어줌

합치는 순간에 정렬 수행하기

너비가 N번, 높이가 logN

#include <stdio.h>

int number = 8;
int sorted[8]; // 정렬 배열은 반드시 전역변수로 선언

void merge(int a[], int m, int middle, int n) {
	int i = m;
	int j = middle + 1;
	int k = m;
	// 작은 순서대로 배열에 삽입
	while (i <= middle && j <= n)  {
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j ++;
		}
		k++;
	}
	// 남은 데이터 삽입
	if (i > middle) {
		for (int t =j; t<=n;t++) {
			sorted[k] = a[t];
			k++;
		}
	} else {
		for (int t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	// 정렬된 배열 삽입
	for (int t =m; t <=n; t++) {
		a[t] = sorted[t];
	}
}

void mergeSort(int a[], int m, int n) {
	// 크기가 1 보다 클 경우
	if (m <n) {
		int middle = (m + n) /2;
		mergeSort(a, m, middle);
		mergeSort(a, middle +1, n);
		merge(a, m ,middle, n);
	}
}

int main(void) {
	int array[number] = {7,6,5,8,3,5,9,1};
	mergeSort(array, 0, number-1);
	for (int i=0; i <= number; i ++) {
		printf("%d ", array[i]);
	}
}
// 1 3 5 5 6 7 8 9

🫧 퀵 정렬 (Quick Sort)

: 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다

퀵 정렬에는 기준값이 있다 -> 피벗(Pivot)

첫번째 원소를 피벗 값으로 설정하고 사용

퀵 정렬의 시간 복잡도는 N*logN

#include <stdio.h>

int number = 10;
int data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

void quickSort(int* data, int start, int end) {
	if (start >= end) {		// 원소가 1개인 경우 그대로 두기
		return;
	}

	int key = start; // 키는 첫번째 원소 (pivot)
	int i = start + 1;
	int j = end;
	int temp;

	while (i <= j)  {	// 엇갈릴 때까지 반복
		while (i <=end && data[i] <= data[key]) {	// 키 값보다 큰 값을 만날 때까지
			i++;
		}
		while ( j > start && data[j] >= data[key]) {		// 키 값보다 작은 값을 만날 떄까지
			j--;
		}
		if (i > j) {	// 현재 엇갈린 상태면 키 값과 교체
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else {	// 엇갈리지 않았다면 i와 j 교체
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}
	quickSort(data, start, j -1);
	quickSort(data, j+1, end);
}

int main(void) {
	quickSort(data, 0, number - 1);
	for (int i = 0; i< number; i++) {
		printf("%d ", data[i]);
	}
}
// 1 2 3 4 5 6 7 8 9 10

🫧 기수 정렬 (radix)

: 주어진 수 들간의 비교를 하지 않고 버킷을 사용해 정렬하는 방법으로, 낮은 자리(1의 자리)에서 높은 자리(10^n 자리) 순으로 버킷에 넣는 방법으로 정렬한다.

원소값이 모두 k 자릿수 이하의 자연수인 특수한 경우에 사용할 수 있는 정렬방법이다.

1. 가장 낮은 1의 자릿수만 가지고 모든 수를 정렬한다.
2. 그 다음으로 낮은 10의 자릿수만으로 정렬한다.
3. 이 과정을 마지막 자릿수까지 반복한다.

from collections import deque

def radixSort():
    nums = list(map(int, input().split(' ')))
    buckets = [deque() for _ in range(10)]

    max_val = max(nums)
    queue = deque(nums)
    digit = 1 # 자릿수

    while (max_val >= digit): # 가장 큰 수의 자릿수일 때 까지만 실행
        while queue:
            num = queue.popleft()
            buckets[(num // digit) % 10].append(num) # 각 자리의 수(0~9)에 따라 버킷에 num을 넣는다.

        # 해당 자릿수에서 버킷에 다 넣었으면, 버킷에 담겨있는 순서대로 꺼내와 정렬한다.
        for bucket in buckets:
            while bucket:
                queue.append(bucket.popleft())
        print(digit,"의 자릿 수 정렬: ", list(queue))
        digit *= 10 # 자릿수 증가시키기

    print(list(queue))