[정렬] 기초 정렬 알고리즘 :: 늦깎이 IT

1. 선택정렬

선택정렬은 현재 위치에 들어갈 값을 찾아서 정렬하는 방법이다.

1) 정렬되지 않은 인덱스의 맨 앞부터, 가장 작은 값을 찾는다.

2) 가장 작은 값을 찾았다면, 그 값을 현재 위치(인덱스)의 원소와 위치를 바꿔준다.

3) 반복한다.

[의사 코드]

select-sort(A[], N)
    for first ← 1 to N-1
        find smallest A[K]
        swap(A[first], A[K])

2)번 라인의 반복문은 N-1번 반복한다.

3)번 라인의 가장 작은 값을 찾기 위한 비교 횟수는 N-1, N-2, ....., 2, 1번 수행한다.

4)번 라인의 교환은 상수시간만큼 걸린다.

즉, 시간복잡도는 T(N) = (N-1) + (N-2) + ..... + 2 + 1 = O(N^2)이다.

[불안정한(Unstable) 정렬]

불안정한 정렬이란, 같은 우선선위를 가진 원소들의 순서가 정렬 이후에 뒤바뀌는 것을 말한다.

우선 Stable 정렬의 예를 들어보자. 

1) 정렬 전의 원소들의 순서는 7, 5, 2, 5 순서로 되어있다.

2) 여기서 5(하트)와 5(스페이스)는 서로 "키" 값이 같지만, 서로 다른 원소이다.

3) Stable한 정렬은 정렬이 끝난 후에도, 같은 키 값들의 순서가 바뀌지 않음을 의미한다.

다음으로 Unstable 정렬의 예를 들어보자.

[이미지 출처]

1) 정렬 전의 원소들의 순서는 7, 5, 2, 5 순서로 되어있다.

2) 여기서 5(하트)와 5(스페이스)는 서로 "키" 값이 같지만, 서로 다른 원소이다.

3) Unstable한 정렬은 정렬이 끝난 후, 같은 "키" 값을 가진 원소들의 순서가 바뀔 수 있다.

선택 정렬은 현재 위치에 저장될 원소를 찾는 정렬 방식으로써, 불안정한 정렬 방식 중의 하나이다.

[JAVA 코드]

public static void selectSort(int[] arr, int length) {
 
        for (int i = 0; i < length - 1; i++) {
 
            int val = i;
 
            for (int j = i + 1; j < length; j++) {
                if (arr[val] > arr[j])
                    val = j;
            }
            swap(arr, i, val);
        }
    }

2. 버블정렬

버블정렬은 두 개의 인접한 원소들을 비교하며 큰 값을 뒤로 이동시키면서 정렬하는 방식이다.

한 번의 루프가 돌면, 배열에서 가장 큰 원소가 배열의 맨 뒤로 이동된다.

1) 맨 앞부터 last - 1번째까지 현재 원소와 다음 원소의 값을 비교한다.

2) 현재 원소가 다음 원소보다 더 크다면, 자리를 바꾼다.

3) 반복한다.

[의사 코드]

bubble-sort(A[], N)
    for last ← N down to 2
        for i ← 1 to last -1
            if(A[i] > A[i+1])
                swap(A[i], A[i+1])

2)번 라인의 반복문은 N-1번 반복한다.

3)번 라인의 반복문은 N-1, N-2, ......, 2, 1번 반복 수행한다.

4)번 라인의 교환은 상수시간만큼 걸린다.

즉, 시간복잡도는 T(N) = (N-1) + (N-2) + ..... + 2 + 1 = O(N^2)이다.

[JAVA 코드]

public static void bubbleSort(int[] arr, int length) {
 
    for (int i = length-1; i > 0; i--) {
 
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1])
                swap(arr, j, j + 1);
        }
    }
}

3. 삽입 정렬

모든 요소에 대해 앞에서부터 차례대로 이미 정렬된 배열과 비교하여, 현재 원소가 삽입될 위치를 찾아 정렬하는 방식이다.

1) 배열의 첫 번째 요소는 이미 정렬되어 있다고 가정한다.

2) 두 번째 요소(K)부터 0부터 (K-1)번째의 요소들 중 삽입될 위치를 찾는다.

3) 만약 K번째 요소가 K-1번째 요소보다 크다면 더 이상 탐색하지 않는다.

[의사 코드]

insert-sort(A[], N)
    for i ← 2 to N
        find index where element will be inserted
        insert A[i] to A[index]

2)번 라인의 반복문은 N-1번 반복한다.

3)번 라인에서 현재 원소가 삽입될 위치를 찾는 연산은 최악의 경우에 1, 2, 3, ..... (N-1)번 반복한다.

배열이 정렬 기준과 반대로 정렬되어 있는 경우에는 최악의 경우에 해당하며, 이미 정렬기준과 같은 기준으로 정렬된 경우에는 최선의 경우이다.

최악의 경우의 시간 복잡도는 T(N) = 1 + 2 + ... + (N-2) + (N-1) = O(N^2)이다.

최선의 경우의 시간 복잡도는 T(N) = 1 + 1 + ... + 1 + 1 = O(N)이다.

[JAVA 코드]

public static void insertSort(int[] arr, int length) {
 
        for (int i = 1; i < length; i++) {
 
            int temp = arr[i];
            int j = i;
 
            for (; j > 0; j--) {
                if (temp < arr[j - 1])
                    arr[j] = arr[j - 1];
                else
                    break;
            }
            arr[j] = temp;
        }
 
    }