[Data Structures] 챕터10. 정렬

쉘 정렬

---

Insertion Sort는 바로 옆 값을 값을 비교하고 정렬한다. Shell Sort는 멀리 있는 값을 비교하고 정렬하여 효율을 얻는다.

성능

Worst : O(n^2)

Average : O(n^1.5)

 

구현하기

void ShellSort(int arr[], int n)
{
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        cout << "         ";
        Print(arr, n);

        InsertionSort(arr, n, gap);
    }

    cout << "         ";
    Print(arr, n);
    cout << endl;
}

 

Insertion Sort

내구현

void InsertionSort(int arr[], int n, int gap) // gap 추가
{
    cout << "gap = " << gap << endl;

    for (int i = gap; i < n; i += 1)
    {
        cout << "Before : ";
        Print(arr, n, i, gap);

        if (arr[i-gap] > arr[i])
            std::swap(arr[i-gap], arr[i]);

        int j;
        for(j=i; 0 <= j-gap ; j-=gap)
            if(arr[j-gap] > arr[j])
                std::swap(arr[j - gap], arr[j]);

        cout << " After : ";
        Print(arr, n, i, gap);
    }
}

 

추천구현

void InsertionSort(int arr[], int n, int gap) // gap 추가
{
    cout << "gap = " << gap << endl;

    for (int i = gap; i < n; i += 1)
    {
        cout << "Before : ";
        Print(arr, n, i, gap);

        if (arr[i - gap] > arr[i])
            std::swap(arr[i - gap], arr[i]);

        int key = arr[i];
        int j = i;
        for (; (0 <= j - gap) && (key < arr[j-gap]); j -= gap)
            arr[j] = arr[j - gap];
        arr[j] = key;

        cout << " After : ";
        Print(arr, n, i, gap);
    }
}

 

병합 정렬(Merge Sort)

---

특징

• 낱개로 나누어 합치면서 정렬한다
• 시간복잡도 : O(n * Log n)
• 공간복잡도 : O(n)
• Merge 순서를 유지하는 Stable 정렬이다

정렬된 그룹을 합치므로 Two pointer로 구현할 수 있다(희소다항식에서 활용하였음)

void MergeSort(int arr[], int merged[], int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;

        MergeSort(arr, merged, left, mid);
        MergeSort(arr, merged, mid + 1, right);

        Merge(arr, merged, left, mid, right);
    }
}

int main()
{
    int arr[] = { 38, 27, 43, 3, 9, 82, 10 }; // https://en.wikipedia.org/wiki/Merge_sort
    int n = sizeof(arr) / sizeof(arr[0]);

    int* merged = new int[n]; // 추가 메모리 필요

    Print(arr, 0, n - 1);
    cout << endl;

    MergeSort(arr, merged, 0, n - 1);

    Print(merged, 0, n - 1);
    cout << endl;

    delete[] merged;
}

 

구현하기

Merge

void Merge(int init[], int merged[], int left, int mid, int right)
{
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    cout << "  Left : ";
    Print(init, left, mid);
    cout << " Right : ";
    Print(init, mid + 1, right);

    // 인덱스를 2개 이용해서 정렬하면서 merge
    k = left;
    while (i <= mid && j <= right)
    {
        if (init[i] > init[j])
            merged[k++] = init[j++];
        else // it also handle init[i] == init[j]
            merged[k++] = init[i++];
    }

    // 남은 내용들 복사
    for (; i <= mid; ++i)
        merged[k++] = init[i];

    for (; j <= right; ++j)
        merged[k++] = init[j];

    // merged -> init 복사
    for (l = left; l <= right; l++)
        init[l] = merged[l];

    cout << "Merged : ";
    Print(init, left, right);
    cout << endl;
}

 

퀵 정렬(Quick Sort)

---

• 시간복잡도
  • best : O(n*log n)
  • worst : O(n^2)
• 공간복잡도 O(log n)

 

구현하기

Partition

내구현

무한 Loop에 빠질 수 있다.

int Partition(int arr[], int low, int high, int n)
{
    int pivot = arr[size_t(floorf((high - low) / 2.0f)) + low];

    int i = low;
    int j = high;

    while (true)
    {
        while (arr[i] < pivot) // 1) arr[i] == pivot 그리고
            ++i;

        while (pivot < arr[j]) // 2) arr[j] == pivot일 경우 무한 loop
            --j;

        if (i >= j) break;

        std::swap(arr[i], arr[j]);


        cout << "pivot=" << pivot << ", i=" << i << ", j=" << j << endl;
        cout << "         ";
        Print(arr, low, high, n);
    }

    return (i+j)/2;
}

 

추천구현

// Hoare partition scheme
int Partition(int arr[], int low, int high, int n)
{
    int pivot = arr[size_t(floorf((high - low) / 2.0f)) + low];
    int i = low - 1;
    int j = high + 1;

    while (true)
    {
        do ++i;
        while (arr[i] < pivot);

        do --j;
        while (pivot < arr[j]);

        if (i >= j) break;

        std::swap(arr[i], arr[j]);


        cout << "pivot=" << pivot << ", i=" << i << ", j=" << j << endl;
        cout << "         ";
        Print(arr, low, high, n);
    }

    return j;
}

 

기수정렬(Radix Sort)

---

특징

• 숫자를 쉽게 정렬할 수 있다. 실수나 문자열을 정렬하기 어렵다.
• 시간복잡도 : O(n)
• 공간복잡도 : O(n + w)
  • 10진수일 때 w=10, 16진수일 때 w=16
• GPU연산에서 많이 사용한다(메모리를 아껴야할 때 Quick Sort처럼 메모리가 필요없는 정렬을 사용한다)

 

구현하기

#include <iostream>
#include "../shared/Queue.h"

using namespace std;

int main()
{
    int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
    int n = sizeof(arr) / sizeof(arr[0]);

    Print(arr, n);

    Queue<int> queues[10];

    int m = GetMax(arr, n); // 가장 큰 자리수를 찾기 위해서

    for (int exp = 1; m / exp > 0; exp *= 10)
    {
        for (int i = 0; i < n; ++i)
        {
            int rem = (arr[i] / exp) % 10;
            assert(0 <= rem); 
            assert(rem <= 10);
            queues[rem].Enqueue(arr[i]);
        }

        //for (int idx = 0; idx < 10; ++idx)
        //{
        //	cout << "i=" << idx << "\t";
        //	Queue<int> temp = Queue<int>{ queues[idx] };
        //	while (!temp.IsEmpty())
        //	{
        //		cout << temp.Front() << " ";
        //		temp.Dequeue();
        //	}
        //	cout << endl;
        //}

        int count = 0;
        for (int idx = 0; idx < 10; ++idx)
        {
            for(; !queues[idx].IsEmpty(); ++count)
            {
                arr[count] = queues[idx].Front();
                queues[idx].Dequeue();
            }
        }

        Print(arr, n);
    }

    return 0;
}