정렬 (14) - 총정리

0. 정렬 표

느린 비교 정렬 $O(n^2)$	빠른 재귀 정렬 $O(nlogn)$	트리구조를 이용한 정렬 $O(nlongn)$	비교하지 않는 정렬 $O(n)$
Selection Sort	Quick Sort	Heap Sort	Counting Sort
Bubble Sort	Merge Sort		Radix Sort
Insertion Sort
Shell Sort

 

1. Review : 느린 비교 정렬

$O(n^2)$ ~ $O(n^{1.5})$ 정도의 성능을 보이는 정렬방법. 2개의 for loop가 사용되며, 원소들을 비교하여 교환하는 방식으로 구현된다.

 

1) Selection Sort : 현재 시작점부터 끝까지 중 가장 작은 원소(min)를 반복적으로 선택하여 앞으로 보내는 방식으로 구현된다. $O(n^2)$의 시간복잡도를 가진다.

void selection_sort(int *arr, int size){
	
	for(int i = 0 ; i < size ; i++){
    	int min = i;
    	
        for(int j = i; j < size ; j++){
        // 이전에 정렬된 부분 제외하고 i부터 끝까지
        
            if(arr[j] < arr[min]){
            // 최소값을 찾았을 때
            
            	min = j;
            }
        }
        
        swap(&arr[min], &arr[i]);
    }
}

 

 

2) Bubble Sort : 인접요소 (k, k+1)을 반복하여 비교해서 가장 큰 원소를 맨 뒤로 보낸다. 마찬가지로 $O(n^2)$의 시간복잡도를 가지지만, 매우 잦은 반복으로 인해 속도가 가장 느리다.

void bubble_sort(int *arr, int size){
	for(int i = 0 ; i < size - 1 ; i++){
	// 마지막 칸은 자동 정렬되니까 size - 1 까지
		
        for(int j = 0 ; j < size - i - 1; j++){
		// 전체 루프 size - 1에서 정렬된 i 전까지

			if(arr[j] > arr[j+1]){
				swap(&arr[j], &arr[j+1]);
			}
		}
	}
}

 

3) Insertion Sort : 현재 시작점의 원소를 이미 정렬이 된 배열의 알맞은 위치에 삽입한다. $O(n^2)$의 시간복잡도를 가지지만, 거의 정렬된 배열을 정렬할 때에는 거의 0에 가까운 시간만에 매우 빠르게 정렬할 수 있다.

void insertion_sort(int *arr, int size){
	
    for(int i = 1 ; i < size ; i ++){
		int curr = arr[i];
		int j = i - 1;
		// 아래에서 j 써야해서 여기에서 선언

		for(; curr < arr[j] && j >= 0; j--){
		//arr[j]가 curr보다 크면 점점 앞으로 감
			
			arr[j + 1] = arr[j];
		}
        
		arr[j + 1] = curr;
	}
}

 

4) Shell Sort : Insertion Sort의 개선버전으로 배열을 거의 정렬이 된 상태로 만드는 것에 초점을 맞춘다. 일정한 Gap을 가진 H개의 원소들을 반복해서 삽입정렬하고(Gap은 지속적으로 감소), 최종적으로 Gap = 1이 되었을 때, 위와 동일한 삽입 정렬을 수행하는데 속도가 더 빠르다. $O(n^{1.5})$정도의 속도를 보인다.

 

void interval_insertion_sort(int *arr, int size, int start, int gap){
	// 0 → start
	// 1 → gap
	// 위 처럼 바꾸면 대강 비슷함.
	
    for(int i = gap ; i < size ; i += gap){

		int curr = arr[i];
		int j = i - gap;

		for(; j >= start && curr < arr[j] ; j -= gap){
			arr[j + gap] = arr[j];
		}

		arr[j + gap] = curr;
	}
}

void shell_sort(int *arr, int size){
	
    for(int gap = size/2 ; gap > 0 ; gap /= 2){
	// gap이 0이 되기 전까지 계속 작아짐

		for(int i = 0 ; i < gap ; i++){
		// i=0 → [0, 5] / i=1 → [1, 6] / ...
			
			interval_insertion_sort(arr, size, i, gap);
		}
	}
}

 

2. Review : 빠른 재귀 정렬

$O(nlogn)$의 성능을 보이는 정렬 방법. 배열을 절반으로 분할(Partition)하거나 합치는(Merge)로직과 자기 자신을 분할하여 2번 재귀호출 하는 방식으로 구현된다.

 

1) Quick Sort : 현존하는 비교 정렬 방법 중 가장 빠르다고 알려진 Quick 정렬은 Partition 함수를 실행하여 Pivot이라는 수를 고르고, Pivot을 기준으로 왼쪽은 작게, 오른쪽은 크게한다. 재귀적으로 호출하여 모든 부분을 그렇게 만들면 전체 배열이 정렬된다. $O(nlogn)$의 시간복잡도를 가지지만 Pivot이 편향되는 최악의 경우 $O(n^2)$의 시간복잡도를 가진다. (아래 예시는 Pivot을 가장 우측 원소로 설정한 경우)

int partition(int arr[], int l, int r){
	int center = (l + r) / 2;
	int pivot = arr[center];

	while(l <= r){
		while(arr[l] < pivot) l++;
		while(arr[r] > pivot) r--;

		if(l <= r){
			swap(arr, l, r);
			l++; r--;
		}
	}
    
	return l;
}

void quick_sort(int *arr, int l, int r){
	
    if(l < r){
		int p = partition(arr, l, r);

		quick_sort(arr, l, p-1);
		quick_sort(arr, p, r);
	}
}

 

2) Merge Sort : Mid = (l + r) / 2를 계산하여 양측을 분할하고, 분할된 두 배열(Run)의 원소들 중 작은 순서 temp 배열에 넣어 하나의 배열로 합친다. 재귀적으로 호출하여 모든부분을 그렇게 만들면 전체 배열이 정렬된다. 항상 $O(nlogn)$의 시간복잡도가 보장되지만, temp 배열을 항상 생성해야하기 때문에  공간복잡도가 좋지 않다.

void merge(int *arr, int l, int r){
	int mid = (l + r) / 2;
	int temp[r];
	
    int lp = l; // 왼쪽 시작
	int rp = mid + 1; // 오른쪽 시작
	int tp = 0; // temp 포인터

	while(lp <= mid && rp <= r){
	// 두 배열 모두 안끝났을 경우

		if(arr[lp] <= arr[rp]){
			temp[tp] = arr[lp]; // 더 작은 원소 기록
			lp++; tp++;
		} else{
			temp[tp] = arr[rp]; // 더 작은 원소 기록
			rp++; tp++;
		}
	}
    
	while(lp <= mid){
	// 왼쪽 배열 안끝났을 경우
    
		temp[tp] = arr[lp];
		lp++; tp++;
	}
    
	while(rp <= r){
	// 오른쪽 배열 안끝났을 경우
    
		temp[tp] = arr[rp];
		rp++; tp++;
	}
    
	for(int i = 0 ; i < tp ; i++){
	// 원본 배열에 기록
    
		arr[l + i] = temp[i];
	}
}

void merge_sort(int *arr, int l, int r){

	if(l < r){
		int mid = (l + r) / 2;

		merge_sort(arr, l, mid);
		merge_sort(arr, mid+1, r);

		merge(arr, l, r);
	}
}

 

3. Review : 트리 구조를 이용한 정렬 

트리구조(부모, 자식 원소간의 관계)를 이용하여 정렬을 수행하는 방식으로, 대표적으로 Heap Sort가 있다.

 

1) Heap Sort : Heap 구조를 이용하여 정렬하는 방식으로, 전체 배열을 최대 Heap으로 만들고, 최대 원소를 제거하여 뒤에 넣고, 나머지 부분들을 다시 Heap으로 만든다. 계속 반복하여 최대 원소들을 뒤에 계속 추가하면 정렬이 완성된다. $O(nlogn)$의 시간복잡도를 보이고 공간복잡도 역시 매우 우수하나, 일반적으로 Quick Sort보다는 약간 느리다고 알려져있다.

void heapify(int *arr, int size, int i) {
    int c = 2 * i + 1;
    // 왼쪽 자식 선택

    if (c < size - 1 && arr[c] < arr[c + 1])
        c++;
    // 오른쪽 자식 존재하면서
    // 오른쪽 자식이 더 크면 오른쪽 자식 선택

    if (c < size && arr[i] < arr[c])
        swap(arr, i, c);
    // 부모보다 자식이 더 크면
    // 둘이 바꿈

    if (c < size / 2)
        heapify(arr, size, c);
    // 내부노드에 한정하여 반복
}

void sort(int *arr, int size) {
    for (int i = size / 2; i >= 0; i--) {
        heapify(arr, size, i);
    }

    for (int i = size - 1; i >= 0; i--) {
        swap(arr, i, 0);
        heapify(arr, i, 0);
    }
}

 

4. Review : 비교하지 않는 정렬

다른 정렬기법들과 다르게 원소간의 크기를 비교하지 않고, 숫자를 센다던지 (Counting Sort), 자리수별로 값을 저장하여 (Radix Sort) 정렬을 수행한다. $O(n)$의 매우 빠른 속도를 가지지만, 공간효율이 좋지 않다던지, 정렬가능한 자료형이 한정적이라는 제한이 뒤따른다.

 

1) Counting Sort : 각 원소의 수를 세서 차례대로 출력하는 방식. 배열 원소의 개수에 상관없이 $O(n)$의 빠른 시간복잡도를 가지지만 배열 원소의 최대값이 커지면 너무 큰 Count 배열을 선언해야하기 때문에 비효율적이다.

void counting_sort(int *arr, int size){
	
    int count[max];
    for(int i = 0; i < max ; i++){
		count[i] = 0; // 초기화
	}
    
	for(int i = 0 ; i < size ; i++){
		int val = arr[i];
		count[val]++; // 개수 세기
	}
    
	for(int i = 0 ; i < max ; i++){
		for(int j = 0 ; j < count[i] ; j++){
			printf("%d ", i);
		}
	}
}

 

2) Radix Sort : 1의 자리, 10의 자리, 100의 자리 ... 순으로 값을 큐에 저장하고, FIFO로 출력하여 기존 배열에 덮어 쓴다. $O(n)$의 시간복잡도를 가지지만, 양의 정수끼리 혹은 음의 정수끼리만 정렬가능하고, 실수 등은 정렬이 불가능하다는 단점이 있다.

int get_max_radix(int *arr, int size){
	int max_val = 0;
	for(int i = 0 ; i < size ; i++){
		if(max_val < arr[i]){
			max_val = arr[i];
		}
	}
    
	int max_radix = 1;
	while(max_val / 10 > 0){
		max_val /= 10;
		max_radix *= 10;
	}
    
	return max_radix;
}

void radix_sort(int *arr, int size){

	int max_radix = get_max_radix(arr, size);
	queue<int> Q[10]; // Queue 10개 (1 ~ 9 자리)

	for(int i = 1 ; i <= max_radix ; i *= 10){
		for(int j = 0 ; j < size ; j++){

			int k = 0;
			// 자리수
            
			if(arr[j] >= i){
				k = (arr[j] / i) % 10;
				// (1, 10, 100)보다 크면 계산하고
				// 작으면 0으로 처리함
				// (e.g. 10의자리에서 2 -> 02 -> 0)
			}
            
			Q[k].push(arr[j]);
		}
        
		int idx = 0;
		for(int j = 0 ; j < 10 ; j++){

			while(!Q[j].empty()){
				arr[idx] = Q[j].front();
				Q[j].pop();
				idx++;
			}
		}
	}
}

 

5. Sound of Sorting

각 정렬 방식들의 전체적인 움직임을 확인해보자.

 

6. 속도 비교

• 10000개의 원소를 가진 랜덤배열(0 ~ 9999)을 정렬시킴.
• 총 50회 반복하여 시간을 계산한 후 평균을 측정함. 
• 결과 : Counting > Merge > Radix >= Quick > Shell > Insertion > Selection > Bubble

selection : 90.000000 msec
bubble : 257.640015 msec
insertion : 57.180000 msec
shell : 15.180000 msec
quick : 1.060000 msec
merge : 0.720000 msec
heap : 1.320000 msec
counting : 0.040000 msec
radix : 1.000000 msec

 

gusdnd852/Sorting-Comparison