algorithm/이론

정렬 알고리즘

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

정렬 알고리즘은 다양한 알고리즘이 존재하는데, 그 중 대표적인 정렬 알고리즘인 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해서 정리하고자 한다.

선택 정렬

선택 정렬 알고리즘은 리스트에서 매번 가장 작은 데이터를 선택하여 차근차근 정렬하는 방식의 알고리즘이다.
가장 작은 데이터를 선택하여 앞으로 보내는 과정을 반복하면 전체 데이터의 정렬이 이루어진다.

선택 정렬의 과정은 다음과 같다.

리스트의 길이(N)-1 만큼 다음 내용을 반복한다.
1. 반복 횟수를 K라고 한다(0 <= K < N-1).
2. 리스트에서 가장 작은 데이터를 선택한다. 이를 M이라고 한다.
3. 리스트의 K번째 데이터와 M을 맞바꾼다.
리스트의 끝까지 반복하면 오름차순 정렬이 완료된다.

이를 자바 코드로 나타내면 다음과 같다.

private static int[] selectSort(int[] target) {
    int[] arr = target.clone();
    int size = arr.length;
    for (int i = 0; i < size; i++) {
        // 배열에서 최소값이 위치한 인덱스 값을 찾는다.
        int minIdx = getMinIdx(arr, i);
        // i번째 요소와 스왑한다.
        swap(arr, i, minIdx);
    }
    return arr;
}

private static int getMinIdx(int[] target, int startIdx) {
    int size = target.length;
    int idx = startIdx;
    int min = target[idx];
    // 선형 탐색을 통해 배열에서 최소값을 찾는다.
    for (int i = startIdx + 1; i < size; i++) {
        if (target[i] < min) {
            min = target[i];
            idx = i;
        }
    }
    return idx;
}

private static void swap(int[] arr, int srcIdx, int desIdx) {
    int tmp = arr[srcIdx];
    arr[srcIdx] = arr[desIdx];
    arr[desIdx] = tmp;
}

선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다.
하지만 이 과정에서 매번 가장 작은 데이터를 찾기 위해 리스트를 선형 탐색 해야한다.
따라서 선택 정렬의 시간 복잡도는 O(N^2)이다.

삽입 정렬

삽입 정렬은 데이터를 하나씩 확인해가며 각 데이터를 적절한 위치에 삽입하는 정렬 알고리즘이다.
선택 정렬에 비해 구현 난이도가 높으나 실행 시간 측면에서 선택 정렬에 비해 더 효율적으로 동작한다.

삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미를 가진다.
특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정하며, 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입된다는 점이 특징이다.

위와 같은 이유에서, 삽입 정렬은 필요할 때에만 데이터의 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 효율적이다.

삽입 정렬의 동작 과정은 다음과 같다.

조건
- 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하여, 리스트의 두 번째 위치부터 시작한다.
- 2개의 포인터 A, B를 둔다.
  - A 포인터는 이미 정렬된 데이터 리스트에 데이터를 삽입 할 위치를 찾는 포인터이다.
  - B 포인터는 미정렬된 데이터 리스트에서 현재 확인중인 데이터 위치를 가리키는 포인터이다.
- A 포인터는 리스트의 첫 번째 위치를, B 포인터는 리스트의 두 번째 위치를 가리킨다.
A 포인터와 B 포인터를 확인하여 아래 과정을 수행한다.
- B 포인터 값이 A 포인터 값보다 크면 (A 포인터 위치+1)의 위치에 데이터를 삽입한다.
  - B 포인터를 한 칸 다음으로 옮기고, A 포인터를 B 포인터 한 칸 이전으로 위치시킨 후, 1번 과정을 재수행한다.
- B 포인터 값이 A 포인터 값보다 작으면, A 포인터의 값을 A+1 위치로 밀고 A 포인터를 한 칸 이전으로 당긴 후 1번 과정을 재수행한다.

이를 자바 코드로 나타내면 다음과 같다.

private static int[] insertSort(int[] target) {
    int[] arr = target.clone();
    int size = arr.length;

    for (int b = 1; b < size; b++) {
        int tmp = arr[b]; // 현재 위치 원소값 저장
        int a = b - 1;

        // b 포인터의 값이 a 포인터의 값보다 클 때까지 수행
        while (a >= 0 && arr[a] > tmp) {
            // a 포인터의 값을 한 칸 다음으로 민다.
            arr[a + 1] = arr[a];
            a--;
        } // b 포인터의 값이 a 포인트 값 보다 크면 반복 종료.
        // a 포인터 값 < b 포인터 값 상태가 된다.
        // 따라서 b 포인터 값을 (a 포인터 + 1)의 위치에 삽입한다.
        arr[a + 1] = tmp;
    }
    return arr;
}

삽입 정렬은 최악의 경우 O(N^2), 최선의 경우 O(N)의 시간복잡도를 가진다.
일반적으로는 선택 정렬과 마찬가지로 반복문이 2번 중첩되었기 때문에 비효율적이지만, 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

퀵 정렬

퀵 정렬은 가장 많이 사용되는 정렬 알고리즘으로, 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.

퀵 정렬은 피벗이라는 기준 데이터를 설정하고, 피벗보다 큰 데이터와 작은 데이터의 위치를 바꾸는 과정을 반복한다.
해당 리스트에서 더 이상 데이터의 위치를 바꿀 수 없으면, 리스트를 반으로 나누고, 각각의 나누어진 리스트에서 알고리즘을 재수행하며 데이터를 정렬한다.

여기서 피벗은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준을 말한다.
퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다.
피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방식으로 퀵 정렬을 구분하는데, 여기서는 대표적인 방식인 호어 분할 방식을 기준으로 설명한다.

호어 분할 방식에서는 데이터 리스트에서 첫 번째 데이터를 피벗으로 정한다.

피벗을 설정한 뒤에는 왼쪽부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
그 후, 큰 데이터와 작은 데이터의 위치를 서로 교환한다.
이러한 과정을 반복하면, 피벗에 대해서 정렬이 수행된다.

퀵 정렬의 동작 과정은 다음과 같다.

정해진 방식으로 리스트에서 피벗을 설정한다.
피벗을 제외한 리스트에서 리스트의 시작 인덱스와 끝 인덱스를 각각 포인터로 둔다(i = 시작 인덱스, j = 끝 인덱스).
i 인덱스를 증가시켜가며 피벗보다 큰 데이터를 찾는다. 찾은 데이터를 A라고 한다.
j 인덱스를 감소시켜가며 피벗보다 작은 데이터를 찾는다. 찾은 데이터를 B라고 한다.
A, B를 선택했다면 조건에 따라 아래 내용을 수행한다.
- i < j 라면, A와 B를 서로 맞바꾼다. 3번 과정으로 돌아가서 차례로 재수행한다.
- i > j 라면, 피벗과 B를 서로 맞바꾼다. 피벗을 기준으로 좌, 우 리스트를 분할하고, 각각의 리스트에 1번 과정부터 재수행한다.

퀵 정렬에서는 위와 같이 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다.
이는 재귀 함수 원리와 같으며, 퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다.
이 때, 재귀 함수의 종료 조건은 현재 리스트의 데이터 개수가 1개인 경우이다.

퀵 정렬을 자바 코드로 구현하자면 다음과 같다.

private static int[] quickSort(int[] target) {
    int[] arr = target.clone();
    int endIdx = arr.length - 1;
    int startIdx = 0;
    quickSortAlgorithm(arr, startIdx, endIdx);
    return arr;
}

private static void quickSortAlgorithm(int[] arr, int startIdx, int endIdx) {
    // 종료 조건
    if (startIdx >= endIdx) {
        return;
    }

    // 피벗 설정
    int pivot = startIdx;
    // 탐색 포인터 설정
    int i = startIdx + 1;
    int j = endIdx;

    while (i <= j) {
        // 피벗보다 큰 데이터를 찾을 때 까지 i 포인터를 증가시킨다.
        while (i <= endIdx && arr[i] <= arr[pivot]) {
            i++;
        }
        // 피벗보다 작은 데이터를 찾을 때 까지 j 포인터를 감소시킨다.
        // 작은 수를 찾지 못한다면 j = pivot 을 가리킨다.
        while (j > startIdx && arr[j] >= arr[pivot]) {
            j--;
        }

        // i, j가 엇갈렸다면 피벗과 작은 데이터(arr[j]) 교체
        if (i > j) {
            int tmp = arr[pivot];
            arr[pivot] = arr[j];
            arr[j] = tmp;

        } else {
            // 엇갈리지 않았다면 큰 데이터와 작은 데이터 교체
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    // 반복문 탈출하면 i > j, j = 피벗
    quickSortAlgorithm(arr, startIdx, j - 1);
    quickSortAlgorithm(arr, j + 1, endIdx);
}

퀵 정렬은 평균적으로 O(NlogN)의 시간복잡도를 가진다.
하지만 최악의 경우 O(N^2)의 시간복잡도를 가진다.
데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다.
하지만 위 예시와 같이 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, 이미 데이터가 정렬되어 있다면 매우 느리게 동작한다.

퀵 정렬을 기반으로 작성된 정렬 라이브러리를 제공하는 프로그래밍 언어는 최악의 경우에도 시간 복잡도가 O(NlogN)이 되는 것을 보장할 수 있도록 피벗값을 설정할 때 추가적인 로직을 더해준다.

계수 정렬

계수 정렬 알고리즘은 특정한 조건이 부합할 때에만 사용할 수 있지만, 매우 빠른 정렬 알고리즘이다.
특정한 조건이란, 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때이다.
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.

계수 정렬이 이러한 특징을 가지는 이유는, 계수 정렬을 이용할 때에 모든 범위를 담을 수 있는 크기의 리스트를 선언하기 때문이다.
이렇게 선언한 범위 리스트에 정렬에 대한 정보를 담아 사용하는 방법이 계수 정렬 알고리즘이다.

계수 정렬의 동작 과정은 다음과 같다.

(데이터의 최대값 - 데이터의 최소값 + 1) 크기의 리스트 C를 선언한다.
정렬할 리스트(A)를 순회하면서 C에 그 정보를 기록한다.
- A 리스트의 i번째 데이터 값인 v를 이용하여 C[v] 값을 하나씩 증가시킨다.
- C[v] 값은 v 값이 등장한 횟수에 대한 정보를 나타낸다.
A 리스트 순회를 마치면 C의 처음부터 순회하면서 정보를 출력한다.

이를 자바 코드로 나타내면 다음과 같다.

// 계수 정렬
private static int[] coefficientSort(int[] target) {
    int min = Arrays.stream(target).min().orElseThrow();
    int max = Arrays.stream(target).max().orElseThrow();
    // 기존 배열의 각 데이터가 몇번 등장했는지 기록할 배열 선언
    int[] arr = new int[max - min + 1];
    // 정렬 결과를 담을 배열 선언
    int[] result = new int[target.length];

    // 데이터 등장 횟수 기록
    for (int i = 0; i < target.length; i++) {
        arr[target[i] - min]++;
    }

    // 기록한 결과를 이용하여 result 배열에 정렬 결과 기록
    int arrPointer = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != 0) {
            for (int j = 0; j < arr[i]; j++) {
                result[arrPointer++] = i + min;
            }
        }
    }

    return result;
}

계수 정렬은 모든 데이터가 양의 정수인 상황에서 데이터의 개수가 N, 데이터 중 최댓값이 K 일 때, 최악의 경우에도 O(N + K)의 시간복잡도를 보장한다.