정렬의 방법에는 Ascending Ordering(오름차순 정렬)과 Descending Ordering(내림차순 정렬) 2가지가 있다. 여기서는 Ascending Ordering으로 정렬하는 것을 기준으로 할 것이다.

비교기반 정렬알고리즘

데이터의 Key를 한번에 두 개씩 비교하여 정렬을 수행하는 알고리즘으로 최악의 경우 O(n log(n))의 시간이 걸리는 것이 최선이라는게 증명 되었다.

(참고)
Stable속성: 정렬 후에 중복된 key에 대한 data의 순서가 그대로 유지 되는지에 대한 것
Inplace속성: 추가적인 공간이 필요없는 것

1. Bubble Sort(Exchange Sort)

앞에서부터 차례대로 두개씩 비교해 가면서 큰 수를 뒤로 옮기는 정렬 알고리즘.

1) C++ Code

void Bubble_Sort(int data[], int size) {
    int temp;
    for(int i=0; i<size; i++) {
        for(int j=0; j< size-(i+1); j++) {
            if(data[j] > data[j+1]) {
                temp = data[j+1]
                data[j+1] = data[j];
                data[j] = temp;
            }
        }
    }
}

(참고: 오름차순 버블 정렬을 구현할 때 다음 두 선택지가 있을 것이다.)
-앞에서부터 비교해 가면서 큰 수를 뒤로 옮긴다.
-뒤에서부터 비교해 가면서 작은 수를 앞으로 옮긴다.

2) 특징

(비교횟수: 배열의 요소들을 서로 비교하는 횟수)
(지정횟수: 배열의 요소를 대입(=)하는 횟수)

3) 참고사항

이미 정렬되어 있는 배열을 정렬하는 경우에는 Bubble Sort는 지정이 이루어지지 않는다.

이 때문에 정렬되어있는 경우 선택정렬보다 버블정렬이 더 빠르다.

2. Insertion Sort

한쪽을 정렬된 부분이라고 생각하고, 배열의 원소들을 차례대로 이 부분에 삽입하는 정렬알고리즘

1) C++ Code

void Insertion_Sort(int data[], int size) {
    for(int i = 1; i < size; i++) {
        int temp = data[i];
        int j = i;
        while(j >= 1 && data[j - 1] > temp) {
            data[j] = data[j - 1];
            j--;
        }
        data[j] = temp;	//while문에서 j--후에 나왔음
    }
}

(참고: 오름차순 삽입 정렬을 구현할 때 다음 두 선택지가 있을 것이다.)
-정렬된 부분의 앞쪽부터 뒤쪽까지 비교한다.
-정렬된 부분의 뒤쪽부터 앞쪽까지 비교한다.

2) 특징

(비교횟수: 배열의 요소들을 서로 비교하는 횟수)
(지정횟수: 배열의 요소를 대입(=)하는 횟수)

3) 참고사항

n의 크기가 큰 자료구조일수록 지정횟수가 Selection Sort에 비해 더 많다.

즉, n의 크기가 클수록 Insertion Sort보다 Selection Sort가 더 빠르다

3. Selection Sort

배열에서 가장 작은수를 찾아 앞쪽으로 옮기고 이것을 나머지 배열에 대해서도 반복하는 방법

1) C++ Code

void Selection_Sort(int data[], int size) {
    int small_index;
    for(int i = 0; i < size - 1; i++) {
        small_index = i;
        for(int j = i + 1; j < size; j++) {
            if(data[j] < data[small_index])
                small_index = j;
        }
        int temp = data[i];
        data[i] = data[small_index];
        data[small_index] = temp;
    }
}

(참고: 오름차순 선택 정렬을 구현할 때 다음 두 선택지가 있을 것이다.)
-정렬된 부분을 앞쪽에 둔다.
-정렬된 부분을 뒤쪽에 둔다.

2) 특징

(비교횟수: 배열의 요소들을 서로 비교하는 횟수)
(지정횟수: 배열의 요소를 대입(=)하는 횟수)

3) 참고사항

Selection Sort는 다른 n^2 정렬 알고리즘에 비해 더 빠르지만, Stable하지 않다는 단점이 있기 때문에 보통 Selection Sort보다는 Insertion Sort를 더 많이 사용한다.

4. Merge Sort

n개의 원소를 가지는 배열을 1개의 원소를 가지는 n개의 배열로 나누고, 이 배열들을 합치면서 정렬해가는 알고리즘

1) C++ Code

// 이미 정렬이 되어있는 배열을 합치는 함수
void Merge(int* result, int* data1, int d1_size, int* data2, int d2_size) {
    int i, j, k;		// i는 data1배열의 index  
    i=0; j=0; k=0;		// j는 data2배열의 index
    				    // k는 data1과 data2를 합친 result의 index
    while(i < d1_size && j < d2_size) {
        if(data1[i] <= data2[j]) {
            result[k] = data1[i];
            i++;
        }
        else{
            result[k] = data2[j];
            j++;
        }
        k++;
    }

    if(i == d1_size) {
        for(; j < d2_size; j++) {
            result[k] = data2[j];
            k++;
        }
    } 
    else if(j == d2_size) {
        for(; i < d1_size; i++) {
            result[k] = data1[i];
            k++;
        }
    }
    delete[] data1, data2;
}
/* 
1. data1과 data2를 가리키는 i와 j중 더 작은값을 result에 넣는다.
2. 이 과정을 i와 j중 하나라도 data1, data2의 크기보다 커지지 않을 때 까지 반복한다.
3. 2번에서 result에 전부 대입하지 못한 data를 result에 대입한다.*/


// MergeSort: 배열을 나누는 과정을 한 후 합치는 과정을 하도록 구현해 정렬 실행
void Merge_Sort(int* data, int size) {
    if(size > 1) {
        int* data1 = new int[size/2];
        copy(data, data + size/2, data1);
        int* data2 = new int[size - size/2];
        copy(data + size/2, data + size, data2);

		Merge_Sort(data1, size/2);
        Merge_Sort(data2, size - size/2);

        Merge(data, data1, size/2, data2, size - size/2);	
    }
}
/* 
(재귀함수 주의)
1. 입력받은 data를 data1과 data2로 나눈다.
2. data1과 data2도 같은 방법으로 size>1일 때까지 나눈다.
3. 나눈 data1과 data2를 다시 data에 합쳐 넣는다. */

2) 특징

(2개로 분할할 때나 4개로 분할할 때나 모두 n log(n) 의 복잡도로 계산된다.)

1. Stable을 결정하는 부분을 잘 찾아보자.
2. 시간복잡도함수를 유도하고 직접 계산해보자

3) 참고사항

1. 실제로는 Inplace하다는 매우 큰 단점때문에 Quick Sort보다 빠르지만 잘 사용되지 않는다.

2. 다음 그림을 보면 좀 더 쉽게 이해할 수 있을 것 같다.

5. Quick Sort

Pivot을 기준으로 Pivot보다 큰 원소들과 Pivot보다 작은 원소들로 나누는 것을 반복 하여 수를 정렬하는 알고리즘

1) C++ Code

// QuickSort: l과 r을 통해 Pivot의 자리를 찾아주고 이를 반복하여 정렬
void Quick(int* data, int start, int end) {
    if(start>=end) return;

    int pivot = data[end];
    int l = start;
    int r = end-1;
    while(l<r) {
        while(l<=r && data[l]<=p)
            l++;
        while(l<=r && data[r]>=p)
            r--;
        if(l<r)
            swap(data[l], data[r]);	
    }

    if(data[l]>data[end]) // 마지막에 원소가 2개남을 경우를 대비
        swap(data[l], data[end]);

    Quick(data, start, l-1);
    Quick(data, l+1, end);
}
/*
1. 분할의 기준이 될 Pivot을 설정한다. (여기서는 배열의 끝(data[end])으로 함)
2. 피벗을 기준으로 
   왼쪽에 있어야 할 원소들을 가리키는 l
   오른쪽에 있어야 할 원소들을 가리키는 r 을 설정한다.
3. l++로 피벗보다 큰 원소를 찾고
   r--로 피벗보다 작은 원소를 찾는다. 그 후 두 원소를 swap한다.
   그리고 이것을 l이 r보다 크거나 같아지기 전까지 반복한다.
4. 마지막에는 l이 pivot보다 큰 원소를 가리키고 있으므로 l과 pivot을 swap해준다.
   (이 때 이 pivot의 자리는 정렬된 배열에서의 자리와 같을 것이다.) */

//Quick_Sort를 시작하는 함수
void Quick_Sort(int* data, int size){
    Quick(data, 0, size-1);
}
// Quick(배열, 시작index, 끝index)

2) 특징

(최악의 경우: pivot이 가장 크거나 작은값일 때)
(최선의 경우: pivot이 중간값일 때)

1. Stable을 결정하는 부분을 잘 찾아보자.
2. 시간복잡도 함수를 유도하고 직접 계산해보자

3) 참고사항

Quick Sort의 성능 향상 방법

1. 재귀호출대신 스택을 사용한다.
   (통상적으로 함수 호출은 스택을 이용한 방법보다 시간이 더 걸린다.)

2. 나누어진 크기가 일정 크기 이하로 작아지면 삽입정렬을 시행한다.
   (n의 크기가 작을 때에는 Insertion Sort가 Quick Sort보다 빠르다.)

3. Pivot을 최대한 중간값이 되도록 설정한다.
   (예를들면 3개를 뽑아 그 중 중간값을 Pivot으로 설정)

---

(참고)
만약 위의 코드에서 Pivot을 맨 앞으로 보내 계산하는 방법을 사용했다면
swap(data[start], data[r])이 되었을 것이다.
(이 때 l=start+1로 변경)

6. Shell sort

전체 배열에서 어떤 Gap만큼 떨어진 원소들 끼리 SubList를 구성하고 이에대해 Insertion Sort를 반복 실행하는 알고리즘이다. 이때 Gap은 점점 줄어들고 마지막에는 Gap이 1이되어 Insertion Sort를 실행한다.

1) C++ Code

// data에서 Gap만큼 떨어진 모든 SubList들을 골라 Insertion Sort수행
void InsertionSort(int data[], int size, int gap) {
    for (int i = gap; i < size; i++) {
        int temp = data[i];
        int j = i;
        while (j >= gap && data[j - gap] > temp) {
            data[j] = data[j - gap];
            j -= gap;
        }
        data[j] = temp;
    }
}
/*
1. data[0:gap-1]을 정렬된 부분이라고 생각하고 정렬 시작.
2. size까지 i++만큼 이동하면서 정렬을 완료한다.
  (size까지 +gap만큼 이동하면서 정렬 완료 후 i++을 하는게 아니다.)
  (이해가 되지 않으면 위의 2.Insertion Sort 참고, 1 <-> gap)*/

// Gap을 줄여가면서 ShellSort 수행
void ShellSort(int data[], int size) {
    vector<int> gap;
    int g = 1;
    int i = 1;
    for(int gap=1, i=1; gap < data.size(); i++) {
        gap.push_back(g);
        g = (9 * pow(9 / 4, i) - 4) / 5;
    }
    while (!gap.empty()) {
        InsertionSort(v, gap.back());
        gap.pop_back();
    }
}
/*
1. gap을 1부터 설정된 식으로 size보다 작을 때까지 stack에 저장한다.
2. stack에서 gap을 하나씩 꺼내가며 위의 InsertionSort에 넣는다. */

2) 특징

(정렬되어 있을수록 Insertion Sort의 성능이 좋아진다는 점을 활용한 알고리즘이다.)

3) 참고사항

gap 설정방법에 따른 시간복잡도는 다음 링크 참고.
https://en.wikipedia.org/wiki/Shellsort

7. Heap Sort

원소들을 하나씩 힙에 넣어 Max Heap힙을 만들고 해당 Heap에서 Pop()한 원소를 리스트의 뒤에 넣는 과정을 반복하며 정렬하는 알고리즘.
(Heap에서 Pop()은 가장 큰 원소가 삭제된다.)

1) C++ Code

// data[i], data[2*i], data[2*i+1]의 SubTree에 대해 MaxHeap의 조건을 유지하도록 하는 함수.
void Max_Heapify(int data[], int size, int depth) {
	int v = data[depth];
	for (int i = 2 * depth; i <= size; i *= 2) {
		if (i < size && data[i] < data[i + 1])
			i = i + 1;
		if (v >= data[i])
			return;
		else {
			int temp = data[i / 2];
			data[i / 2] = data[i];
			data[i] = temp;
		}
	}
}
/* 
1. data[2*depth]와 data[2*depth+1] 중 큰 것을 선택한다.
2. 위에서 구한 것과 data[depth]를 비교한다.
3. data[depth]가 더 크면 해당 SubTree에서는 MaxHeap을 유지중이라는 것므로 종료한다.
4. 위에서 구한것이 더 크면 data[depth]와 swap한다. 
5. 4번에 의해 아래 SubTree에서는 MaxHeap이 깨졌을 수도 있다.
   따라서 이 과정을 2*depth부터 size까지 *2하면서 반복한다. */

// Heap을 만들고 Sort하는 함수
void HeapSort(int data[], int size) {
	int n = size - 1;
	for (int i = n / 2; i >= 1; i--)
		Max_Heapify(data, n, i);

	for (int i = n - 1; i >= 1; i--) {
		int temp = a[1];
		a[1] = a[i + 1];
		a[i + 1] = temp;
		Max_Heapify(data, i, 1);
	}
}
/*
1. Heapify함수를 size/2부터 1까지 역순으로 실행하면 Max_Heap이 완성된다.
2. data[1]과 data[i+1]을 바꾸고 i--한다.
   (i+1을 정렬된 부분으로 생각하기 때문)
3. 원래 Max_Heap이 완성된 상태였으므로 data[1]에 대해 Heapify해준다.
   (root에 있는 원소의 자리만 찾아주면 되기 때문) */

2) 특징

(Heapify: log(n)의 복잡도를 가지는 알고리즘)
(Heap을 만들 때: Heapify를 n번 수행)
(Heap에서 꺼낼 때: Heapify를 n번 수행)

1. Heap을 만드는 과정과 Heap에서 Pop하는 과정을 나누어 기억하자.
   (그릴 줄도 알아야 한다.)

3) 참고사항

1. 퀵정렬보다는 2배정도 느리다.
2. Heap의 조건
   

(Complete Binary Tree는 마지막 Level을 제외한 모든 Node들이 가득차 있고, 마지막 Level에는 가장 왼쪽부터 Node들이 채워져 있는 상태를 말한다.)

분포기반 정렬알고리즘

데이터의 분포를 미리 알고있는 경우 사용할 수 있다.
이러한 알고리즘들은 평균적으로 실행시간이 O(n)으로 비교기반보다 훨씬 더 좋은 성능을 가진다.

(단, 데이터에 대한 사전정보가 있어야 한다는 점 때문에 동적인 환경에서 사용이 불가능하다는 것이 큰 단점이다.)

1. Counting Sort (계수정렬)

1) 미리 알고있어야 하는 정보

데이터의 범위

2) 정렬과정

0. 다음과 같은 데이터가 있고, 우리는 이 데이터의 범위가 1~4라는 것을 알고 있다.
   

1. 먼저 Count배열에 0~i까지 데이터의 수를 넣어 계산한다. ( O(n) )
   

2. 그 후 새로운 배열 int b[ ]를 만든 후 아래와 같이 Count배열을 활용해 알맞은 위치에 값을 넣는다. ( O(n) )
   

3. 마지막으로 정렬된 b배열을 다시 a배열에 복사한다. ( O(n) )
   

3) 특징

(데이터의 크기만큼의 추가적인 배열이 필요하다)

2. Radix Sort (기수정렬)

1) 미리 알고있어야 하는 정보

배열의 최대 자리수

2) 정렬과정 (10진법)

0. 다음과 같은 데이터가 있고, 우리는 이 데이터의 자리수가 2라는 것을 알고있다.
   

1. 먼저 결과를 담을 배열 1개와 진법의 수 만큼의 배열 1개를 만든다.
   • int result[8]; : 결과를 담을 배열
   • int Q[10]; : 진법의 수 만큼의 배열

1. 먼저 1의 자리수를 기준으로 정렬을 수행하여 진법배열에 저장한다.
   

2. 데이터를 이 배열에서 꺼내 순서대로 결과배열에 담는다.
   

3. 이 결과리스트를 가지고 10의자리, 100의자리, ... 순서로 다시 1~2를 반복한다.
   

3) 특징

(각 자리수마다 O(n)만큼의 시간이 걸려 전체적으로는 O(kn)의 시간이 걸린다.)
(데이터의 크기만큼의 추가적인 배열과 진법 크기만큼의 추가 배열이 필요하다.)

병렬 정렬알고리즘

지금까지 배운 정렬 알고리즘들은 전부 한번에 2개의 원소만 비교하여 동작할 수 있었다.
하지만 병렬처리를 하는 GPU나 쓰레드설정 등을 통해 동시에 비교하도록 하면 정렬 속도가 더 빨라지게된다.

이 때, 주의할 점은 동시에 실행되는 비교가 서로에게 영향을 주어선 안된다는 것이다.
따라서 이 병렬정렬 알고리즘에서는 서로에게 영향을 주지 않는 대상을 한번에 많이 골라야 하는 것이 관건이다.
이렇게 되면 최대한 많은 비교를 한번에 할 수 있기 때문이다.

위의 조건을 만족하는 대상을 고르기 위한것이 Sorting Network이다.

참고로 다음 두 Sorting Network를 보자 (en.wikipedia 참고)

• Bubble Sort의 Sorting Network
• Insertion Sort의 Sorting Network

해당 사이트에 들어가서 확인하면 알 수 있듯이 결국엔 Bubble Sort와 Insertion Sort의 Sorting network는 동일하게 동작하게 된다는 것을 알 수 있다.

• 동일한 Sorting Network

(참고로 여기선 두 원소 중 큰것이 화살표 방향으로 이동하게 표현했다.)

1. Bitonic Sort

Bubble sort의 Sorting network를 좀 더 Paralel하게 시행하는 정렬이다.
참고로, 이 Sorting Network는 데이터의 개수별로 이미 전부 모양이 정해져 있다.

(8개 BitonicSort 예시)

2. Odd even transposition Sort

홀수번 반복과 짝수번 반복에서 정렬 방법을 나누어 Paralel하게 시행하는 정렬

예시)

3. Odd even merge sort

Odd Even Transposition Sort를 다시 병렬정렬의 장점을 최대한 활용하여 몇 구간을 합쳐 Paralel하게 작동하도록 한 알고리즘.

1. 시간복잡도 증명하기
2. 시간복잡도 구하기
3. 마스터 이론
4. 정렬알고리즘: 머지소트, 퀵소트, 쉘정렬, 힙정렬
5. 병렬정렬