[자료구조] 정렬

Definition

• 리스트의 요소들을 특정 순서로 배열하는 것

Sorting Algorithms - 1

• Internal Sorting
  • 리스트가 메인 메모리 안에서 정렬되는 것
  • 정렬 속도는 빠르지만, 데이터의 양이 제한적
• External Sorting
  • 부가적인 공간에서 리스트가 정렬되는 것
  • 정렬 속도는 느리지만, 보조 공간을 이용하여 큰 데이터도 정렬할 수 있음

Insertion sort

• 새로운 key를 삽입하기 위해서 리스트에서 맞는 위치를 찾고 그 위치에 삽입
• 성능
  • O(n²)
    • n = 키의 개수
  • 짧은 리스트에서 간단하고 좋음
  • 부분적으로 이미 정렬된 리스트일 때 좋음

Example

// GeeksforGeeks
void insertionSort(int arr[], int n)
{
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Selection sort

• n개의 key에 대해서 n-1번 리스트를 탐색
• 1번째 탐색에서
  • 첫번째 n-i 키 중에서 가장 큰 key를 선택
  • n-i+1번째 키와 교환
• 성능
  • O(n²)
    • n = 키의 개수
  • 일반적으로 insertion sort(삽입정렬)보다 비효율적

Example

// GeeksforGeeks
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;
        // Swap the found minimum element with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}

Duplex selection sort

• n개의 키를 가진 리스트를 (n-1)/2번 탐색
  • 가장 큰 key와 가장 작은 key를 선택하고 가장 큰 key를 마지막 key와, 가장 작은 key를 첫번째 key와 교환
• O(n2)
  • n = 키의 개수

Merge sort

• Divide and Conquer(분할 & 정복)
• Split and Merge
  • Split: 리스트를 2개의 하위 리스트로 분할
    • 이때 정렬하는 것이 아니고 분할만 하는 것
  • Merge: 2개의 하위 리스트를 하나의 정렬된 리스트로 합병
• 성능
  • O(n log₂n)
    • n: 키의 개수
  • 공간 복잡도: O(n)
  • Stable sort(안정 정렬)

Example

// GeeksforGeeks
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    /* create temp arrays */
    int L[n1], R[n2];

    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy the remaining elements of L[], if there
    are any */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there
    are any */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

Quick sort

• 가장 많이 쓰이는 정렬 알고리즘 중 하나
• 분할 & 정복
• Quick sort의 종류
  • Plain quick sort(새로운 리스트 생성)
  • In-place quick sort(기존 리스트 사용)

Example (In-place quick sort)

void printArray(int arr[], int size)
{
    int i;
    printf("\n");
    for (i = 0; i < size; i++)
        printf("arr[%d]: %d\n", i, arr[i]);
    printf("\n");
}
void quick_sort(int *data, int start, int end)
{
    if (start >= end)
    {
        return;
    }
    int pivot = start;
    int i = pivot + 1;
    int j = end;
    int temp;
    while (i <= j)
    {
        while (i <= end && data[i] <= data[pivot])
        {
            i++;
        }
        while (j > start && data[j] >= data[pivot])
        {
            j--;
        }
        if (i > j)
        {
            temp = data[j];
            data[j] = data[pivot];
            data[pivot] = temp;
        }
        else
        {
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
        printArray(data, 8);
    }
    quick_sort(data, start, j - 1);
    quick_sort(data, j + 1, end);
}
int main(void)
{
    int data[8] = {17, 90, 2, 80, 14, 13, 75, 16};
    quick_sort(data, 0, 7);
    return 0;
}

Sorting-Related Concepts

• Stable sort(안정 정렬)
• Indirect sort(간접 정렬)

Stable sort

• 리스트를 정렬할 때, 중복된 값들의 순서가 유지될 때 안정 정렬이라고 함
• 예를 들어, 2, 6, 4, 1, 5, 2, 7 리스트가 있고, 첫번째 2를 2-1, 두번째 2를 2-2라고 할 때 이 순서가 그대로 유지될 때, 안정 정렬되었다고 함
• Example
  • Insertion sort
  • Merge sort
  • Bubble sort
  • Counting sort
• Unstable sort example
  • Selection sort
  • Heap sort
  • Shell sort
  • Quick sort

Indirect sort

• 인덱스 정렬로도 알려짐
• 인덱스 배열을 만들고 정렬하는 방법

Sorting Algorithms - 2

Bubble sort

• Selection sort와 유사
• i번의 탐색
  • j번째 key를 j+1번째 키와 비교하고 j번째 key가 j+1번째 key보다 크면 교환
• 성능
  • 최악 또는 평균: O(n²)
    • n: key의 개수
  • Best case: O(n)
  • 공간 복잡도: O(1)
  • Stable Sorting

Example

void swap(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
void bubbleSort(int arr[], int n)
{
    int i, j;
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if(arr[j] > arr[j+1])
                swap(arr[j], arr[j+1])
        }
    }
}

Heap Sort

• Max Heap 또는 Min Heap 사용
• Max Heap: 완전 이진 트리 + Max 트리
  • Max 트리
    • 각 노드의 key들은 왼쪽 또는 오른쪽 하위 트리의 모든 key보다 값이 크거나 같다
    • 이진 탐색 트리가 아님
• 오름차순
  • 삽입
    • 모든 key를 Min Heap에 삽입
  • 삭제
    1. root key 삭제
    2. 삭제 후 Min Heap 유지하기 위해 재구성
• 내림차순
  • 삽입
    • 모든 key를 Max Heap에 삽입
  • 삭제
    1. root key 삭제
    2. 삭제 후 Max Heap 유지하기 위해 재구성
• 성능
  • O(n log2n)
    • n: key의 개수
    • 완전 이진 트리의 높이는 항상 log n
  • 공간복잡도: O(1)
  • Unstable sort(불안정 정렬)

Counting Sort

// GeeksforGeeks
void countSort(char arr[])
{
    // The output character array that will have sorted arr
    char output[strlen(arr)];

    // Create a count array to store count of individual
    // characters and initialize count array as 0
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));

    // Store count of each character
    for (i = 0; arr[i]; ++i)
        ++count[arr[i]];

    // Change count[i] so that count[i] now contains actual
    // position of this character in output array
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i - 1];

    // Build the output character array
    for (i = 0; arr[i]; ++i) {
        output[count[arr[i]] - 1] = arr[i];
        --count[arr[i]];
    }

    /*
     For Stable algorithm
     for (i = sizeof(arr)-1; i>=0; --i)
    {
        output[count[arr[i]]-1] = arr[i];
        --count[arr[i]];
    }

    For Logic : See implementation
    */

    // Copy the output array to arr, so that arr now
    // contains sorted characters
    for (i = 0; arr[i]; ++i)
        arr[i] = output[i];
}

Radix Sort

// GeeksforGeeks
int sorted_array_length = 0;

struct node {
    int arr[100];
    int arr_length;
    struct node* nxt[10];
};

// Function to create a new node of
// the Linked List
struct node* new_node(void)
{
    struct node* tempNode
        = (struct node*)malloc(sizeof(struct node));

    tempNode->arr_length = 0;

    for (int i = 0; i < 10; i++) {
        tempNode->nxt[i] = NULL;
    }

    // Return the created node
    return tempNode;
}

// Function to sort the given array
// using MSD Radix Sort recursively
void msd_sort(struct node* root, int exp, int* sorted_arr)
{
    if (exp <= 0) {
        return;
    }

    int j;

    // Stores the numbers in different
    // buckets according their MSD
    for (int i = 0; i < root->arr_length; i++) {

        // Get the MSD in j
        j = (root->arr[i] / exp) % 10;

        // If j-th index in the node
        // array is empty create and
        // link a new node in index
        if (root->nxt[j] == NULL) {
            root->nxt[j] = new_node();
        }

        // Store the number in j-th node
        root->nxt[j]->arr[root->nxt[j]->arr_length++]
            = root->arr[i];
    }

    // Sort again every child node that
    // has more than one number
    for (int i = 0; i < 10; i++) {

        // If root->next is NULL
        if (root->nxt[i] != NULL) {

            if (root->nxt[i]->arr_length > 1) {

                // Sort recursively
                msd_sort(root->nxt[i], exp / 10,
                         sorted_arr);
            }

            // If any node have only
            // one number then it means
            // the number is sorted
            else {
                sorted_arr[sorted_array_length++]
                    = root->nxt[i]->arr[0];
            }
        }
    }
}

// Function to calculate the MSD of the
// maximum value in the array
int get_max_exp(int* arr, int n)
{
    // Stores the maximum element
    int mx = arr[0];

    // Traverse the given array
    for (int i = 1; i < n; i++) {

        // Update the value of maximum
        if (arr[i] > mx) {
            mx = arr[i];
        }
    }

    int exp = 1;

    while (mx > 10) {
        mx /= 10;
        exp *= 10;
    }

    // Return the resultant value
    return exp;
}

// Function to print an array
void print(int* arr, int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    printf("\n");
}

// Driver Code
int main()
{
    // Unsorted array
    int array[] = { 9330, 9950, 718, 8977, 6790,
                    95,   9807, 741, 8586, 5710 };

    // Input array length
    int n = sizeof(array) / sizeof(array[0]);

    // create the root node
    struct node* root = new_node();

    // Stores the unsorted array
    // in the root node and
    // set arr_length
    memcpy(root->arr, array, sizeof(array));
    root->arr_length = n;

    printf("Unsorted array : ");

    // Print the unsorted array
    print(root->arr, n);

    // Find the optimal longest exponent
    int exp = get_max_exp(root->arr, root->arr_length);

    // Stores the sorted numbers
    int output[n];
    int* sorted_arr = &output[0];

    // Function Call
    msd_sort(root, exp, sorted_arr);

    printf("Sorted array : ");

    // Print the sorted array
    print(sorted_arr, n);

    return 0;
}