정렬 알고리즘 직접 구현

in Algorithm


정렬 알고리즘

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하기 때문에 확실히 알아둬야 한다.

정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬,

퀵 정렬, 계수 정렬을 공부해보려고 한다.


오늘 프로그래머스의 K번째 수 라는 문제를 풀고 상황에 따라 적절한 정렬 알고리즘을

사용하지 않으면 굉장히 시간도 오래걸리고 비효율적이라는 것을 느꼈다.

해당 문제를 풀때 자바 Collections에서 제공해주는 sort()메서드를 사용했는데,

다른 풀이를 보니 퀵 정렬을 직접 구현해서 푼 사람도 있었다. 당연히 이 사람들의 코드가

속도와 성능면에서 훨씬 우위에 있었고 이를 보면서 정렬 알고리즘을 한 번쯤은 직접

구현해보고 싶었다.


선택(Selection) 정렬

선택 정렬이란?

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고,

그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬 방법.


코드 구현

💡 Swap란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 의미한다.

public class Selection {

    public static void main(String[] args) {

        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        for (int i = 0; i < arr.length - 1; i++) {
            
            int minIndex = i;
            
            for (int k = i + 1; k < arr.length; k ++) {
                if (arr[i] > arr[k]) {
                    minIndex = k;
                }
            }
            // Swap
            int temp = arr[i]
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
            
            // 출력
            System.out.println(Arrays.toString(arr));
        }
    }
}


출력 결과
[0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
[0, 1, 9, 7, 3, 5, 6, 2, 4, 8]
[0, 1, 2, 7, 3, 5, 6, 9, 4, 8]
[0, 1, 2, 3, 7, 5, 6, 9, 4, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


시간복잡도

선택정렬은 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은

수를 찾기 위해서 비교 연산이 필요하다. 간단하게 보면 두 번의 for문을 돈다. 하나의 for문은

시간 복잡도 O(N)을 갖는다. 따라서 선택정렬은 O(N^2) 만큼의 시간복잡도를 갖는다.


정리

선택 정렬은 기본 정렬 라이브러리를 포함해 뒤에서 다룰 알고리즘과 비교했을 때 매우

비효율적이다. 하지만, 특정한 리슽에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서

잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요가 있다.


삽입(Insertion) 정렬

삽입 정렬이란?

삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다.

사입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간

측면에서 더 효율적인 알고리즘이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로

“데이터가 거의 정렬되어 있을 때” 훨씨 효율적이다. 선택 정렬은 현재 데이터의 상태와

상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬을 그렇지 않다.

참고로 삽입정렬은 두 번째 데이터부터 시작한다.


코드 구현1

public class Insertion {
    public static void main(String[] args) {

        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        for (int i = 1; i < arr.length; i++) {
            for (int k = i; k >= 1; k--) {
                
                // 한 칸씩 왼쪽으로 이동
                if (arr[k] < arr[k-1]) {
                    int temp = arr[k];
                    arr[k] = arr[k-1];
                    arr[k-1] = arr[k];
                } else break; // 작은 값이 없다면.
            }
        System.out.println(Arrays.toString(arr));
        }
    }
}


코드 구현2

public class Insertion {

    public static void main(String[] args) {

        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        for (int i = 1; i < arr.length; i++) {

            int temp = arr[i];

            int beforeIdx = i - 1;

            while (beforeIdx >= 0 && arr[beforeIdx] > temp) {
                arr[beforeIdx + 1] = arr[beforeIdx];
                beforeIdx --;
            }
            arr[beforeIdx + 1] = temp;

            System.out.println(Arrays.toString(arr));
        }
    }
}


출력 결과
[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
[0, 5, 7, 9, 3, 1, 6, 2, 4, 8]
[0, 3, 5, 7, 9, 1, 6, 2, 4, 8]
[0, 1, 3, 5, 7, 9, 6, 2, 4, 8]
[0, 1, 3, 5, 6, 7, 9, 2, 4, 8]
[0, 1, 2, 3, 5, 6, 7, 9, 4, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2) 인데, 선택 정렬과 마찬가지로 반복문이 2번

중첩되어 사용되었다. 여기서 꼭 기억해야 할 내용은 삽입 정렬은 현재 리스트의 데이터가

거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다. 최선의 경우에 O(N) 의

시간 복잡도를 가진다.


정리

거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 다른 정렬 알고리즘을 이용하는 것보다

삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.


퀵(Quick) 정렬

퀵 정렬이란?

퀵 정렬은 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다.

퀵 정렬과 비교할 만큼 빠른 알고리즘으로 “병합 정렬” 알고리즘이 있다.이 두 알고리즘은

대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다.

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는

방식으로 동작한다. 퀵 정렬은 피벗(Pivot)이 사용된다.

피벗 : 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 ‘기준’

퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을

설정하고 리스트를 분할 하는 방법에 따라서 여러 가지 방식으로 퀴 정렬을 구분하는데,

이번에는 가장 대표적인 분할 방식인 호어분할(Hoare Partition) 방식을 기준으로

퀵 정렬을 구현해 보겠다.


분할 방식

특징Hoare PartitionLomuto Partition
피벗 데이터 선정첫 번째 데이터맨 오른쪽 데이터
동작피벗보다 큰 값은 왼쪽에서, 작은 값은 오른쪽에서 찾고 두 위치를 바꾼다.피벗보다 작은 값을 left값으로 옮긴다.


코드 구현

public class Quick {

    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        quickSort(arr, 0, arr.length - 1);
    }
    
    public static void quickSort(int[] arr, int first, int last) {
        if (first >= last) return;      // 첫 번째 인덱스가 마지막 인덱스를 넘을 때?

        int pivot = first;
        int i = first + 1;
        int j = last;

        while (i <= j) {
            while(i <= last && arr[i] <= arr[pivot]) i++;
            while (j > first && arr[j] >= arr[pivot]) j--;
                if (i > j) swap(arr, pivot, j);
                else swap(arr, i, j);
        }

        System.out.println(Arrays.toString(arr));
        quickSort(arr, first, j - 1);
        quickSort(arr, j + 1, last);
    }


    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}


출력 결과
[2, 5, 4, 0, 3, 1, 6, 7, 9, 8]
[0, 1, 2, 4, 3, 5, 6, 7, 9, 8]
[0, 1, 2, 4, 3, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(NlogN) 이다. 위에서 공부했던 선택정렬과 삽입정렬에

비하면 매우 빠른 편이다. 데이터의 갯수가 많을수록 차이는 매우 극명하게 드러난다.

다만, 퀵 정렬의 시간 복잡도에 대하여 한 가지 기억해 둘 점이 있다. 바로 평균적으로

시간복잡도가 O(NlogN)이지만 최악의 경우 시간 복잡도가 O(N^2) 라는 것이다.


정리

데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 리스트의

가장 왼쪽 데이터를 피벗으로 삼을 때, ‘이미 데이터가 정렬되어 있는 경우’에는 매우

느리게 동작한다.


병합 정렬