Sort에 관한 고찰

프로그래밍의 기본이라고 할 수 있는 sort, 오늘은 이 sort에 대해 탐구해보려 합니다.

정렬 알고리즘에는 여러가지가 있습니다.

 

Bubble Sort

Selection Sort

Insertion Sort

Merge Sort

Quick Sort

Heap Sort

Radix Sort

Counting Sort

 

하이브리드 정렬

Timsort ( Insertion + Merge)

Introsort (Quick + Heap)

 

등등..

 

이중에서 최고의 정렬은 무엇일까요

 

최고의 정렬이란건 없습니다. 상황에 적합한 정렬이 있을 뿐입니다.

 

1. 메인 메모리에 데이터가 들어가는가?

안된다면 외부 정렬 알고리즘을 써야합니다. 주로 이런 알고리즘은 Quick sort와 Merge sort를 기반으로 합니다. ( 또한 SSD를 이용하면 오버헤드를 줄일 수 있습니다.)

2. 입력의 분포를 알고있는가? 

정렬이 많이 되어있다면 Timsort가 좋을것입니다. (Timsort는 Insertion과 Merge를 섞음, Swift의 기본 sort이기도 합니다.)

 

3. 정렬할 원소가 무엇인가?

object를 비교해야한다면, comparison sorting(비교 정렬)을 해야합니다. 하지만 그게 아니라면 counting sort나 radix정렬을 고민해볼 수 있습니다.

 

4. 코어를 많이 가지고 있는가?

Quicksort, MergeSort, MSD radixSort, 등은 paralleize(병렬)로 잘 작동합니다. 하지만, heapsort는 그렇지 않습니다.

 

5. 데이터가 어떻게 표현되는가?

만약 Array에 담겨져 있다면, quick sort가 locality of reference(참조 지역성) 때문에 더 빠를 수 있습니다. merge sort는 추가 공간이 필요하기 때문에 더 느릴 수 있습니다.

만약 Linked list에 담겨져 있다면, 참조 지역성이 없어지기 때문에 qucik sort와 merge sort를 다시 비교해봐야 합니다.

 

 

Bubble Sort

인접한 요소를 비교하여 정렬하는 알고리즘, 시간복잡도는 O(N^2)입니다.

void bubble_sort(int n, int *arr)
{
    for (int i = 0; i < n - 1; i++) // 배열 크기 - 1 만큼 반복합니다.
    {
        for (int j = 0; j < n - i - 1; j++) // 인접 원소를 탐색합니다. 마지막 i개의 원소는 볼 필요가 없습니다.
        {
            if (compare(arr[j], arr[j + 1]))
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

 

최적화 할 수 있을까?

배열이 이미 정렬된 경우에도 항상 시간복잡도는 O(N^2)입니다. 이를 최적화 하여 

내부루프에서 스왑이 발생하지 않으면 break문을 추가해 줄 수 있습니다.

void bubble_sort(int n, int *arr)
{
    bool swapped;
    
    for (int i = 0; i < n - 1; i++)
    {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (compare(arr[j], arr[j + 1]))
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (swapped == false)
            break;
    }
}

 

최적화 된 버블 소트

최악, 평균 시간복잡도 : O(N^2), 최악의 경우는 어레이가 reversed sorted 됐을 때 일어납니다.

최선 시간복잡도: O(N), 이미 정렬됐을 경우입니다.

보조 공간: O(1)

엣지 케이스: 요소가 이미 정렬 됐을 경우 시간복잡도가 O(N)입니다.

InPlace정렬입니다.

Stable정렬입니다.

 

Selection Sort

반복문을 돌면서 정렬되지 않고 남은 정렬에서 최소값을 뽑아서 swap하는 알고리즘입니다.

 

void selection_sort(int n, int * arr)
{
    int min_index;
    
    for (int i = 0; i < n - 1 ; i++)
    {
        min_index = i;
        for (int j = i + 1; j < n ; j++)
        {
            if (compare(arr[min_index], arr[j]))
                min_index = j;
        }
        int temp = arr[min_index];
        arr[min_index] = arr[i];
        arr[i] = temp;
    }
}

시간복잡도 : O(N^2)입니다.

보조 공간: O(1), Selection Sort는 swap을 O(N)번 이상 하지 않습니다. ( 메모리 쓰기가 cost가 많이들때 유용합니다.)

UnStable정렬입니다. ( 하지만 스왑하지않고 밀어내는 방식으로 구현하면 안정적이게 만들 수 있습니다.)

Inplace 정렬입니다.

 

Insertion Sort

정렬 된 곳과 정렬되지 않은 곳으로 나눠 정렬된 곳으로 원소를 하나씩 삽입하는 정렬입니다.

void insertion_sort(int n, int *arr)
{
    for (int i = 1; i < n ; i++)
    {
        int key = arr[i];
        int j;
        for (j = i - 1; j >= 0 && compare(arr[j], key); j--) // 넣어줄 공간을 만들고 밀어내야함
            arr[j + 1] = arr[j];
        arr[j + 1] = key;
    }
}

 

시간복잡도 O(N^2)

보조 공간: O(1)

엣지 케이스: 원소가 revered ordered 되어있을 경우 시간이 제일 오래걸리며, 이미 정렬되어있을 경우 O(N)이 걸립니다.

InPlace정렬입니다.

Stable정렬입니다.

online 입니다.( 전체 입력을 모르고 하나씩 입력이 들어와도 사용 가능한 알고리즘입니다.)

용도: 원소가 적을때나, 입력이 거의 정렬되어 있을 경우 유용합니다.

삽입될 인덱스를 찾을 때 이진 탐색을 사용할 수도 있으나 원소를 삽입할 시 어레이를 밀어내야 하기 때문에 시간복잡도는 여전히 O(N^2)이 됩니다.

 

Merge Sort

QuickSort와 유사합니다, 머지 소트는 Divide and Conquer 알고리즘입니다.

 

 

void merge (int *arr, int l, int m, int r)
{
    int n1 = m - l + 1;
    int n2 = r - m;
    
    // 새로운 어레이 만들기;
    int L[n1], R[n2];
    
    // 데이터 복사

    memcpy(L, arr + l, n1 * sizeof(int));
    memcpy(R, arr + m + 1, n2 * sizeof(int));
    
 
    
    int i = 0;
    int j = 0;
    int k = l;
    //  이미 정렬되었기 때문에 O(N)으로 정렬
    while ( i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 남은 원소 카피
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
    
}
// l은 left index, r은 right index
void merge_sort(int *arr, int l , int r)
{
    if (l >= r)
        return ; // 재귀 끝
    int m = l + (r - l) / 2;
    merge_sort(arr, l, m);
    merge_sort(arr, m + 1, r);
    merge(arr,l,m,r);
    
}

시간복잡도: 모든 경우에 대해 O(NlogN)

보조 공간: O(N)

 

Stable정렬입니다.

응용: 퀵소트에 비해서 Linked list의 정렬에 유용합니다.  linked list일 경우엔, 추가공간이 필요하지 않습니다.

external sorting에 이용됩니다.

 

단점 :

- 작은 작업의 경우 다른 정렬 알고리즘 보다 느립니다.

- O(N)의 보조 공간이 필요합니다.

- 배열이 정렬되어 있어도 전체 과정을 거칩니다.

 

Quick Sort

Merge Sort와 유사합니다. 퀵 소트도 Divide and Conquer 알고리즘입니다.

피벗을 고르고 피벗을 중심으로 주어진 배열을 분할합니다. 피벗을 선택하는 방법은 여러가지가 있습니다.

1. 항상 첫번째 원소

2. 항상 마지막 원소

3. 랜덤 원소

4, 중간 원소 (medain)

 

항상 마지막 원소로 피벗을 선택한 코드입니다.

 

int partition_(int *arr, int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);
    
    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            _swap(&arr[i], &arr[j]);
        }
    }
    _swap(&arr[i + 1], &arr[high]);
    return (i + 1);
    
}

// 메인 함수
// low -> 시작 인덱스
// high -> 마지막 인덱스
void quick_sort(int *arr, int low, int high)
{
    if (low < high)
    {
        int pi = partition_(arr, low, high);
        
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

 

이 코드를 백준에 돌려본다면?

시간초과가 납니다. 이유는 quick sort는 운이 안좋은 경우 시간복잡도가 O(N^2)가 되기 때문입니다.

아마 특정 테스트 케이스가 pivot을 항상 마지막 원소로 하는 알고리즘을 저격한듯 합니다. 이를 해결하려면 어떻게 해야할까요?

바로 pivot을 랜덤하게 잡으면 됩니다.

 

int partition_(int *arr, int low, int high)
{
    int random_int = rand() % (high - low);
    random_int += low;
    
    _swap(&arr[random_int], &arr[high]);
    int pivot = arr[high];
    int i = (low - 1);
    
    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            _swap(&arr[i], &arr[j]);
        }
    }
    _swap(&arr[i + 1], &arr[high]);
    return (i + 1);
    
}

// 메인 함수
// low -> 시작 인덱스
// high -> 마지막 인덱스
void quick_sort(int *arr, int low, int high)
{
    if (low < high)
    {
        int pi = partition_(arr, low, high);
        
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

성공입니다!

 

시간복잡도: 최악 O(N^2) ( 항상 작은요소 or 항상 큰 요소를 피벗으로 선택할 때)

best, average : O(nlongn)

특징: 최악의 경우가 O(N^2)임에도 불구하고 Merge Sort, Heap Sort에 비해 실제로 더 빠릅니다. (내부 정렬, 참조 지역성)

기본 구현은 stable하지 않지않습니다.

Inplace입니다.

 

 

Heap Sort

힙 소트는 Binary Heap 데이터 구조를 기반으로하는 알고리즘입니다. 

void heapify(int *arr, int n, int i)
{
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    
    if (l < n && arr[l] > arr[largest])
        largest = l;
    
    if (r < n && arr[r] > arr[largest])
        largest = r;
    
    if (largest != i) {
        _swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}


void heap_sort(int *arr, int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);
    
    for (int i = n - 1; i > 0; i--)
    {
        _swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
    
}

참고:

힙 정렬은 inplace 입니다.

일반적으로 stable하지 않습니다.

시간복잡도는 O(NlogN)입니다.

힙 소트는 Quick, Merge에 비해 좋지 않아서 자주 사용하진 않지만, heap 데이터 구조는 자주 사용합니다.

 

Counting Sort

counting sort는 특정 범위 내의 key를 기반으로 정렬하는 알고리즘 입니다.

1. 입력 데이터의 범위가 정렬할 개체 수보다 크지 않은 경우 효과적입니다.

2. 비교 기반 정렬이 아닙니다. 시간복잡도는 O(N + K)입니다. K 는 데이터의 범위중 가장 큰값 입니다.

Radix Sort

int getMax(int arr[], int n)
{
    int mx = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > mx)
            mx = arr[i];
    return mx;
}

void count_sort(int *arr, int n, int exp)
{
    int output[n];
    int i, count[10] = { 0 };
    
    for (int i = 0; i < n; i++)
    count[(arr[i] / exp) % 10]++;
    
    for (int i = 1; i < 10; i++)
    count[i] += count[i - 1];
    
    for (i = n - 1; i >= 0; i--)
    {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    
    for (i = 0 ; i < n; i++)
    arr[i] = output[i];
}

void radix_sort(int *arr, int n)
{
    int m = getMax(arr, n);
    
    for (int exp = 1; m / exp > 0; exp *= 10)
    count_sort(arr, n, exp);
}

시간복잡도는 O(D(N + K))입니다. D는 자리수입니다. 일반적으로 숫자일 땐 K는 10이 됩니다.(0~ 9) 

References

stackoverflow.com/questions/32234711/which-sorting-algorithm-works-best-on-very-large-data-set

www.geeksforgeeks.org/