정렬 알고리즘 정리

Sorting Algorithm

sorting 알고리즘은 크게 Comparisons 방식과 non-Comparisons 방식으로 나눌 수 있다. 본 포스팅에서는 일단 non-comparisons sorting 알고리즘은 생략하도록 하겠다.

• Comparisons Sorting Algorithm(비교 방식 알고리즘)
  • Bubble sort, Selection Sort, Insertions Sort, Merge Sort, Heap Sort, Quick Sort
• non-Comparisons Sorting Algorithm
  • Counting Sort, Radix Sort

 

Comparisons Sorting Algorithm

Bubble Sort

n개의 원소를 가진 배열을 정렬할 때, In-place sort로 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 가장 큰 값을 배열의 맨 끝에다 이동 시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다.

• 공간 복잡도 = O(1)
• 시간 복잡도 = O(n^2)

#include <iostream>
#include <algorithm>
#define MAX 5005
using namespace std;

int d[MAX];

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (d[j] > d[j + 1]) {
                swap(d[j], d[j + 1]);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << d[i] << " ";
    }

    return 0;
}

 

Selection Sort

n개의 원소를 가진 배열을 정렬할 때, 계속해서 바꾸는 것이 아니라 비교하고 있는 값의 index를 저장해둔다. 그리고 최종적으로 한 번만 바꿔준다. 하지만 여러번 비교를 하기 때문에 비효율적.

• 공간 복잡도 = O(1)
• 시간 복잡도 = O(n^2)

#include <iostream>
using namespace std;
#define MAX 5005

int arr[MAX];
int N;

void Swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void selection_sort(int *arr, int size) {
    for(int i = 0; i < size; i++) {
        int minidx = i;
        for(int j = i + 1; j < size; j++) {
            if(arr[minidx] > arr[j]) {
                minidx = j;
            }
        }
        Swap(arr[minidx], arr[i]);
    }
}

 

Insertion Sort

n개의 원소를 가진 배열을 정렬할 때, i번째를 정렬할 순서라고 가정하면, 0부터 i-1까지의 원소들은 정렬되어 있다는 가정하에, i번째 원소와 i-1번째 원소부터 0번째 원소까지 비교하면서 i번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서의 원소와 비교하면서 정렬해준다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복해준다.

• 공간 복잡도 = O(1)
• 시간 복잡도 = O(n^2)

#include <iostream>
#define MAX 5005
using namespace std;

int d[MAX], n;

int main() {
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> d[i];

    for(int i = 0; i < n; i++) {
        int temp = d[i];
        int j = i - 1;
        for(; j >= 0; j--) {
            if(d[j] < temp) break;
            d[j+1] = d[j];
        }
        d[j+1] = temp;
    }
}

 

Merge Sort

n개의 원소를 가진 배열을 정렬할 떄, 정렬하고자 하는 배열의 크기를 작은 단위로 나누어 정렬하고자 하는 배열의 크기를 줄이는 원리를 사용한다. => Divide and Conquer

더이상 나누어지지 않을 때 까지 반 씩 분할하다가 더 이상 나누어지지 않은 경우(원소가 하나인 배열일 때)에는 자기 자신, 즉 원소 하나를 반환한다. 원소가 하나인 경우에는 정렬할 필요가 없기 때문이다. 이 때 반환한 값끼리 결합될때 비교가 이뤄지며, 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다. 그리고 이 임시 배열에 저장된 순서를 합쳐진 값으로 반환한다. 실제 정렬은 나눈 것을 병합하는 과정에서 이뤄지는 것이다.

• 공간 복잡도 : O(n)
• 시간 복잡도 : O(nlogn)

#include <stdio.h>
#define MAX_SIZE 8
using namespace std;
int sorted[MAX_SIZE]; //추가적인 공간이 필요
// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int list[], int left, int mid, int right) {
    int i, j, k, l;
    i = left;
    j = mid+1;
    k = left;
    /*분할 정복된 list의 합병*/
    while(i<=mid && j<=right) {
        if(list[i]<=list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
        }


    //남아있는 값들을 일괄 복사
    if(i > mid) {
        for(l=j; l<=right; l++)
            sorted[k++] = list[l];
    }
    //남아있는 값들을 일괄 복사
    else {
        for(l=i; l<=mid; l++)
            sorted[k++] = list[l];
    }
    //배열 sorted[](임시배열)의 리스트를 배열 list[]로 재복사
    for(l=left; l<=right; l++) {
        list[l] = sorted[l];
    }
}

//합병 정렬
void merge_sort(int list[], int left, int right) {
    int mid;
    if(left < right) {
        //중간 위치를 계산하여 리스트를 균등 분할(divide)
        mid = (left+right)/2;
        //앞쪽 부분 리스트 정렬(conquer)
        merge_sort(list, left, mid);
        //뒤쪽 부분 리스트 정렬(conquer)
        merge_sort(list, mid+1, right);
        //정렬된 2개의 부분 배열을 합병하는 과정(combine)
        merge(list, left, mid, right);
    }
}

int main() {
    int i;
    int n = MAX_SIZE;
    int list[MAX_SIZE] = {21, 10, 12, 20, 25, 13, 15, 22};
    //합병 정렬 수행(left: 배열의 시작=0, right: 배열의 끝=7)
    merge_sort(list, 0, n-1);
    //정렬 결과 출력
    for(i = 0; i < n; i++) {
        printf("%d\n", list[i]);
    }
}

 

Heap Sort

binary heap 자료구조를 활용할 sorting 방법에는 두 가지 방법이 존재한다. 하나는 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 원리로 정렬을 하게 되는 방법이고, 나머지 하나는 기존의 배열을 hepify(heap으로 만들어주는 과정)을 거쳐 꺼내는 원리로 정렬하는 방법이다. heap에 데이터를 저장하는 시간 복잡도는 O(logn)이고, 삭제 시간 복잡도 또한 O(logn)이 된다. 때문에 힙 자료구조를 사용하여 정렬을 하는데 시간 복잡도는 O(logn)이 된다. 이 정렬을 하려는 대상이 n개라면 시간 복잡도는 O(nlogn)이 된다.

• 공간 복잡도 : O(1)
• 시간 복잡도 : O(nlogn)

 

Quick Sort

정렬 기법중에서 가장 빠르다고 해서 quick임. 하지만 worst case에서는 시간 복잡도가 O(n^2)가 나올수도 있다. 하지만 constant factor가 작아서 속도가 빠르다.

Divide and Conquer 전략을 사용하여 정렬이 이루어진다. 분할 과정에서 pivot이라는 개념이 사용된다. 입력된 배열에 대해 오름차순으로 정렬한다고하면 이 pivot을 기준으로 좌측은 pivot으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 partition된다. 이렇게 나뉜 좌, 우측 각각의 배열을 다시 재귀적으로 퀵정렬을 시키면 또 partition 과정이 적용된다. 이 때 한가지 주의할 점은 partition 과정에서 pivot으로 설정된 값은 다음 재귀과정에 포함시키지 않아야 한다. 이미 partition 과정에서 정렬된 자신의 위치를 찾았기 때문이다.

Worst Case는 pivot의 값이 항상 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정되었을 때이다. 이 때의 시간 복잡도는 O(n^2)이 된다.

분할 => 입력 배열을 피봇을 기준으로 비균등하게 2개의 부분 배열(피봇을 중심으로 왼쪽: 피봇보다 작은 요소, 오른쪽: 피봇보다 큰 요소)로 분할한다.

정복 => 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분활 정복 방법을 적용한다.

결합 => 정렬된 부분 배열들을 하나의 배열에 합병한다.

순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피봇)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수가 있다.

• 공간 복잡도 : O(log(n))
• 시간 복잡도 : O(nlog(n))

#include <iostream>
#include <algorithm>
using namespace std;

void quickSort(int *arr,int left,int right) {
    int pivot, left_temp, right_temp;
    left_temp = left;
    right_temp = right;
    pivot = arr[left];
    while (left < right) {
        while (arr[right] >= pivot && (left < right)) {
            right--;
        }
        if (left != right) {
            arr[left] = arr[right];
        }
        while (arr[left] <= pivot && (left < right)) {
            left++;
        }
        if (left != right) {
            arr[right] = arr[left];
            right--;
        }
    }
    arr[left] = pivot;
    pivot = left;
    left = left_temp;
    right = right_temp;
    if (left < pivot) quickSort(arr, left, pivot - 1);
    if (right > pivot) quickSort(arr, pivot + 1, right);
}
int N;
int arr[100010];
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    quickSort(arr, 0, N - 1);
    for (int i = 0; i < N; i++) {
        cout << arr[i]<<' ';
    }
}