정렬 알고리즘 [선택정렬, 버블정렬, 삽입정렬]

선택 정렬 (Selection Sort) : O(N^2)

선택정렬은 선택이라는 이름에서 그 의미가 잘 들어납니다.

 

오름 차순으로 정렬한다고 가정해보면, 배열 전체를 탐색해 가장 큰 수를 찾아 가장 오른쪽 요소와 Swap합니다.

 

요소가 10개인 [5,2,3,13,24,1,6,23,52,12] 이러한 배열이 있을 때

 

0번째 요소부터 순차적으로 가장 큰 값(52)이 위치한 인덱스(8)를 찾은 뒤 12와 52를 Swap합니다.

 

[5,2,3,13,24,1,6,23,12,52] 이제 맨 마지막 요소는 이미 정렬됐으니 다음으로 큰 수(24)를 찾아 12와 Swap하면 됩니다.([5,2,3,13,12,1,6,23,24,52])

 

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {5,2,3,13,24,1,6,23,52,12};

        for(int i=arr.length-1; i>0; i--){ // 첫 번째 Loop
            int idx = i;
            for (int j = 0; j <=i; j++) { // 두 번째 Loop
                if(arr[j]>arr[idx]){
                    idx = j;
                }
            }
            int tmp = arr[idx];
            arr[idx] = arr[i];
            arr[i] = tmp;
        }

        for (final int j : arr) {
            System.out.print(j + " ");
        }
    }
}

 

선택 정렬의 시간복잡도는 첫 번째 Loop은 n-1 순회하고 두 번째 Loop은 차례대로 n번 순회, n-1번 순회, n-2번 ~ 1번 순회 하기 때문에 n(n-1)/2 로 O(N^2)이 됩니다.

 

버블 정렬 (Bubble Sort) : Worst Case O(N^2), Best Case O(N)

버블 정렬도 선택 정렬과 마찬가지로 오름 차순 정렬 시 가장 큰 값을 오른쪽 끝으로 밀어내는 것은 똑같습니다.

 

하지만 오른쪽 끝으로 밀어내는 방식이 조금 독특하다. 선택 정렬은 단순하게 배열을 처음부터 끝까지 탐색해서 가장 큰 요소의 인덱스를 찾아 Swap했다면 버블 정렬은 배열을 처음부터 끝까지 탐색하며 오름차순이 아니라면 즉시 Swap합니다.

 

[5,2,3,13,24,1,6,23,52,12] // 주어진 배열

 

[5,2,3,13,24,1,6,23,52,12] // 빨간색 두 요소는 오름 차순이 아니므로 5,2 Swap

 

[2,5,3,13,24,1,6,23,52,12] // 빨간색 두 요소는 오름 차순이 아니므로 5,3 Swap

 

// 생략

 

[2,3,5,13,1,6,23,24,52,12] // 빨간색 두 요소는 오름 차순이 아니므로 52,12 Swap

 

[2,3,5,13,1,6,23,24,12,52]

 

이렇게 첫 번째 루프가 끝이 난다. 이제 다음 루프도 똑같이 정렬하면 됩니다.

 

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5,2,3,13,24,1,6,23,52,12};

        for (int i = arr.length-1; i >0; i--) { // 첫 번째 Loop
            for (int j = 0; j < i; j++) { // 두 번째 Loop
                if(arr[j]>arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }

        for (final int j : arr) {
            System.out.println(j);
        }
    }
}

 

단순히 알고리즘만 봐도 선택정렬보다 하는 일이 많습니다. 매번 Swap해주는 비용이 존재하기 때문입니다.

 

버블 소트도 선택정렬과 마찬가지로 첫 번째 Loop은 n-1 순회하고 그에 따라서 두 번째 Loop이 n,n-1,n-2 ... 2 까지 순회합니다.

 

즉 마찬가지로 O(N^2)이 됩니다.

 

하지만 버블 소트는 정렬된 배열(Best Case)에선 O(N)을 만들 수 있는데, 스왑 Flag를 두어 Swap이 한 번도 되지 않았다면(모두 정렬돼 있다면) 첫 번째 루프만에 끝이 납니다.

 

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5,2,3,13,24,1,6,23,52,12};

        boolean swapped;
        for (int i = arr.length-1; i >0; i--) {
            swapped = false;
            for (int j = 0; j < i; j++) {
                if(arr[j]>arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    swapped = true;
                }
            }
            if(!swapped){
                break;
            }
        }

        for (final int j : arr) {
            System.out.println(j);
        }
    }
}

 

정렬 알고리즘인데 이미 정렬된 배열을 정렬하면 무슨의미가 있느냐 라는 의문이 들 수도 있겠지만 선택 정렬의 경우 이러한 개선의 여지 조차 없습니다. 정렬된 배열도 무조건 n^2의 복잡도를 가지게됩니다.

 

삽입 정렬 (Insertion Sort) : Worst Case O(N^2), Best Case O(N)

생각해보면 정렬 알고리즘들의 이름을 참 잘 지은 것 같습니다. 그 이름에서 특성이 아주 잘 들어납니다.

 

삽입 정렬도 말 그대로 들어갈 자리에 삽입해 정렬합니다. 지금까지 위에 두 정렬 방식은 가장 큰 값을 찾아 오른쪽으로 밀어내는 방식이었다면 삽입 정렬은 배열의 중간에 끼워 넣는 방식입니다.

 

[5,2,3,13,24,1,6,23,52,12] // 주어진 배열

 

// 반 까지 정렬을 진행했다고 가정

 

[1,2,3,5,6,24,13,23,52,12] 

 

이제 13을 정렬할 차례입니다. 좌측까진 모두 정렬이 된 상태고 13이 들어갈 자리는 6과 24 사이입니다.

 

[1,2,3,5,6,13,24,23,52,12] 

 

이렇게 배열을 하나씩 제자리에 끼워 넣는 방식입니다.

 

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {5,2,3,13,24,1,6,23,52,12};

        for (int i = 1; i < arr.length; i++) {
            int idx = i - 1; 
            int newItem = arr[i];
            while (idx >= 0 && newItem < arr[idx]) {
                arr[idx + 1] = arr[idx];
                idx--;
            }
            arr[idx + 1] = newItem;
        }
    }
}

 

초기에 i의 의미는 정렬되지 않은 새로운 요소의 인덱스를 의미합니다. newItem이란 변수에 저장해두고 idx의 의미는 이미 정렬된 배열의 마지막 인덱스가 됩니다.

 

[1,2,3,5,6,13,24,23,52,12]  // i는 23을 가리키고 idx는 24를 가리킵니다.

 

이제 while loop에서 비교를 시작합니다. 24가 23보다 크기 때문에 배열을 한 칸씩 당겨옵니다.

 

[1,2,3,5,6,13,23,24,52,12]

 

23은 13보다 크기 때문에 while loop을 탈출하고 다음 loop을 돕니다.

 

삽입 정렬도 일반적인 경우 O(N^2)의 복잡도를 가지지만 정렬된 상태라면 O(N) 복잡도를 가지게됩니다.

 

+ 이진 삽입 정렬

삽입 정렬은 새로운 요소를 중간에 끼워 넣을 인덱스를 찾아야합니다. 위 코드는 이 위치를 찾는 과정을 선형적으로 진행하지만 이진 탐색을 이용하면 위치를 찾는 과정을 logN 수준으로 복잡도를 낮출 수 있습니다.