정렬 알고리즘

Selection Sort (선택 정렬)

[예시 코드]

#include <cstdio>
#include <cstdlib>
 
using namespace std;
 
void selection_sort(int *nums, int N) {
    int min, min_idx;
    
    for(int i=0; i<N-1; i++) {
        min_idx = i;
        min = nums[i];
        for(int j=i+1; j<N; j++) {
            if(min > nums[j]) {
                min = nums[j];
                min_idx = j;
            }
        }
        nums[min_idx] = nums[i];
        nums[i] = min;
    }
}
 
int main(void) {
    int N, *nums;
    scanf("%d", &N);
 
    nums = (int*)malloc(sizeof(int)*N);
 
    for(int i=0; i<N; i++)
        scanf("%d", &nums[i]);
 
    selection_sort(nums, N);
 
    for(int i=0; i<N; i++)
        printf("%d ", nums[i]);
 
    printf("\n");
 
    free(nums);
 
    return 0;
}

[내용]

N개의 숫자를 정렬할 때, index를 0~N-2 에서부터 N-1 까지 보면서, 가장 작은 수를 선택해서 맨 앞과 바꿔주면서 정렬해 나가는 방식이다.

맨 처음부터 마지막 중 가장 작은 수를 찾아서 첫 번째와 바꿔주고,

두 번째부터 마지막 중 가장 작은 수를 찾아서 두 번째와 바꿔주는 식으로 진행한다.

[특징]

- 비교 연산이 많이 사용된다.

- 값을 실제로 교환하는 횟수는 상대적으로 적다.

Bubble Sort (버블 정렬)

[예시 코드]

#include <cstdio>
#include <cstdlib>
 
using namespace std;
 
void bubble_sort(int *nums, int N) {
    int temp;
 
    for(int i=0; i<N-1; i++) {
        for(int j=1; j<N-i; j++) {
            if(nums[j-1] > nums[j]) {
                temp = nums[j-1];
                nums[j-1] = nums[j];
                nums[j] = temp;
            }
        }
    }
}
 
int main(void) {
    int N, *nums;
    scanf("%d", &N);
 
    nums = (int*)malloc(sizeof(int)*N);
 
    for(int i=0; i<N; i++) {
        scanf("%d", &nums[i]);
    }
 
    bubble_sort(nums, N);
 
    for(int i=0; i<N; i++)
        printf("%d ", nums[i]);
 
    printf("\n");
 
    free(nums);
 
    return 0;
}

[내용]

앞쪽부터 뒷쪽까지 2개의 숫자씩을 비교해가며, 오른쪽이 더 작은 경우 값을 교환해준다.

이를 N번 진행하면 전체 숫자의 정렬이 완료된다.

[특징]

- 비교와 값의 교환이 많이 발생한다.

Insertion Sort (삽입 정렬)

[예시 코드]

#include <cstdio>
#include <cstdlib>
 
using namespace std;
 
void insertion_sort(int *nums, int N) {
    int t, idx;
 
    for(int i=1; i<N; i++) {
        t = nums[i];
        idx = i;
        while(nums[idx-1] > t && idx > 0) {
            nums[idx] = nums[idx-1];
            idx--;
        }
        nums[idx] = t;
    }
}
 
int main(void) {
    int N, *nums;
    scanf("%d", &N);
 
    nums = (int*)malloc(sizeof(int)*N);
 
    for(int i=0; i<N; i++) {
        scanf("%d", &nums[i]);
    }
 
    insertion_sort(nums, N);
 
    for(int i=0; i<N; i++)
        printf("%d ", nums[i]);
 
    printf("\n");
 
    free(nums);
 
    return 0;
}

[내용]

idx를 1부터 N-1까지 실행하며, 해당 인덱스에 있는 숫자를 그 앞쪽에서 맞는 위치에 삽입해준다.

[특징]

- 다른 정렬 알고리즘들에 비해서빠른 편이다.

- 정렬해야 할 숫자의 개수가 적은 경우에 유용하다.

Indirection을 이용한 Insertion Sort (삽입 정렬)

[예시 코드]

#include <cstdio>
#include <cstdlib>
 
using namespace std;
 
void insertion_sort(int *nums, int *idx, int N) {
    int t, tIdx;
 
    for(int i=0; i<N; i++)
        idx[i] = i;
 
    for(int i=1; i<N; i++) {
        t = idx[i];
        tIdx = i;
        
        while(nums[idx[tIdx-1]] > nums[t] && tIdx > 0) {
            idx[tIdx] = idx[tIdx-1];
            tIdx--;
        }
 
        idx[tIdx] = t;
    }
}
 
int main(void) {
    int N, *nums, *idx;
    scanf("%d", &N);
 
    nums = (int*)malloc(sizeof(int)*N);
    idx = (int*)malloc(sizeof(int)*N);
 
    for(int i=0; i<N; i++) {
        scanf("%d", &nums[i]);
    }
 
    insertion_sort(nums, idx, N);
 
    for(int i=0; i<N; i++)
        printf("%d ", nums[idx[i]]);
 
    printf("\n");
 
    free(nums);
    free(idx);
 
    return 0;
}

[내용]

- Insertion Sort에서 값을 하나씩 복사시키지 않고, 인덱스용 배열을 따로 생성하고 인덱스만 정렬한다.

[특징]

- 원래 값이 있는 배열은 자료가 변하지 않고 그대로 유지된다.

- sorting된 순서대로 접근하려면, 인덱스 배열을 순서대로 접근하며 이를 인덱스로 사용하여 숫자 배열을 사용하면 된다.

Shell Sort (쉘 정렬)

[예시 코드]

#include <cstdio>
#include <cstdlib>
 
using namespace std;
 
void shell_sort(int *nums, int N) {
    int v, k;
 
    for(int h = N/2; h>0; h/=2) {
        for(int i=0; i<h; i++) {
            for(int j=i+h; j<N; j+=h) {
                v = nums[j];
                k = j;
                while(k > h-1 && nums[k-h] > v) {
                    nums[k] = nums[k-h];
                    k -= h;
                }
                nums[k] = v;
            }
        }
    }
}
 
int main(void) {
    int N, *nums;
    scanf("%d", &N);
 
    nums = (int*)malloc(sizeof(int)*N);
 
    for(int i=0; i<N; i++)
        scanf("%d", &nums[i]);
 
    shell_sort(nums, N);
 
    for(int i=0; i<N; i++)
        printf("%d ", nums[i]);
 
    printf("\n");
 
    free(nums);
 
    return 0;
}

[내용]

- 기본적인 접근법은 insertion sort와 동일하다.

- h는 스텝 사이즈이다.

- 처음부터 2개씩 비교를 하는 것이 아니라, 스텝 사이즈만큼 떨어트려서 있는 것들끼리만 비교하여 insertion sort 방식으로 정렬을 하고, 스텝 사이즈를 줄이며 이를 반복한다.

[특징]

- 정렬하려는 숫자의 개수와 관계 없이 속도가 빠른 편이다.

- 추가적인 메모리가 필요하지 않다.

Quick Sort (퀵 정렬)

[예시 코드]

#include <cstdio>
#include <cstdlib>
 
void quick_sort(int *nums, int N) {
    int i, j, v, temp;
 
    if(N > 1) {
        v = nums[N-1];    // Pivot
        i = -1;
        j = N-1;
 
        while(true) {
            while(nums[++i] < v);
            while(nums[--j] > v);
 
            if(i >= j)
                break;
 
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
 
        temp = nums[i];
        nums[i] = nums[N-1];
        nums[N-1] = temp;
 
        quick_sort(nums, i);
        quick_sort(nums+i+1, N-i-1);
    }
}
 
int main(void) {
    int N, *nums;
    scanf("%d", &N);
 
    nums = (int*)malloc(sizeof(int)*N);
 
    for(int i=0; i<N; i++)
        scanf("%d", &nums[i]);
 
    quick_sort(nums, N);
 
    for(int i=0; i<N; i++)
        printf("%d ", nums[i]);
 
    printf("\n");
 
    free(nums);
 
    return 0;
}

[내용]

- quick sort는 나눠서 정렬하는 것이다.

- 인덱스 i는 왼쪽에서 오른쪽으로, 인덱스 j는 오른쪽에서 왼쪽으로 이동한다.

- 우선, 현재 주어진 숫자 배열의 범위에서 가장 오른쪽에 있는 값을 pivot으로 설정한다.

- 인덱스 i를 오른쪽으로 이동하며 가장 먼저 나오는 pivot보다 큰 값의 인덱스까지 이동한다.

- 인덱스 j는 왼쪽으로 이동하며 가장 먼저 나오는 pivot보다 작은 값의 인덱스까지 이동한다.

- 만약에 i가 j의 오른쪽에 있다면 (i와 j가 이동하다가 서로 지나쳤다면) 그만하고, 그렇지 않으면 계속하여 i와 j를 구해서 서로 값을 바꿔준다.

- 이렇게 하면 현재 i가 있는 곳을 기준으로 왼쪽은 pivot보다 작은 값들이, 오른쪽은 pivot보다 큰 값들이 위치하게 된다.

- recursion으로 현재 i보다 왼쪽과 오른쪽을 각각 한번씩 호출해준다.

- 다 끝나고나면 정렬이 된다.

- cf. recursion termination 조건은 if(N > 1)이다. (N이 1이 되면 종료)

[특이 사항]

- 이미 정렬된 경우에는 별로 좋지 않기 때문에 pivot을 랜덤으로 지정해주는 방법도 있다.

- 간격이 클 때는 quick sort를 사용하고, 작으면 insertion sort를 사용하여 병행하는 방법도 있다.