cs log

정렬 알고리즘 정리

· cs

정렬 알고리즘의 종류

  • 정렬 알고리즘은 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등의 알고리즘으로 구성되어 있다.
  • 퀵 정렬의 경우는 평균 nlogn의 시간복잡도를 갖지만,최악의 경우에는 n2 시간 복잡도를 갖는다.

  1. 정렬시 피벗(pivot)이라는 기준값을 사용하여 배열을 분할하는데, 피벗 선택에 따라 성능이 크게 달라진다. 만약 항상 최솟값 또는 최댓값을 피벗으로 선택하는 경우, 퀵 정렬은 최악의 성능을 보인다. 즉, 분할된 부분 배열의 크기가 매우 작아지기 때문에 분할 정복의 장점을 잃게 된다.

  2. 피벗을 기준으로 배열을 분할할 때, 피벗보다 작은 값들과 큰 값들을 나누는데, 만약 배열이 이미 정렬되어 있는 경우나 거의 정렬되어 있는 경우에는 피벗의 선택에 따라 한 쪽 부분 배열의 크기가 크게 줄어들 수 있다. 이로 인해 분할이 불균형하게 이루어져 재귀적인 호출이 깊게 이루어지는 상황이 발생할 수 있다.

[0]정렬 알고리즘 비교

버블 정렬

  • 두 인접한 데이터를 비교해 swap하는 방식으로 정렬하는 방법
  1. 비교할 루프 범위를 지정한다.
  2. 인접한 데이터를 비교한다.
  3. swap 조건에 부합하면, swap연산을 수행한다.
  4. 2~3번 과정을 루프 범위 동안 반복한다.
  5. 정렬된 영역을 제외하고 1~4번 과정을 반복한다.
private void bubbleSort(int[] input) {
    for (int i = 0; i < input.length; i++) {
        // i : 비교할 루프 범위, 즉 i번쨰 원소까지는 정렬됨을 보장한다. 
        for (int j = input.length - 1; j > i; j--) {
            if (input[j-1] > input[j]) {
                swap(input, j-1, j);
            }
        }
    }
}

private void swap(int[] input, int x, int y) {
    int tmp = input[x];
    input[x] = input[y];
    input[y] = tmp;
}
  • 구현은 간단하지만 시간 복잡도 O(n2)으로 왠만한 알고리즘 문제에서는 타임아웃 에러가 발생한다.

선택 정렬

  • 최솟값을 선택해, 정렬되지 않은 범위의 제일 앞 위치로 swap 한다.
  1. 남은 정렬 부분에서 최솟값을 찾는다.
  2. 남은 정렬 부분에서 가장 앞의 원소와 swap한다.
  3. 남은 정렬 부분의 위치를 변경한다. (한칸줄인다.)
  4. 1~3을 반복하여 남은 정렬부분이 사라지도록 한다.
private void selectionSort(int[] input) {
    for (int i = 0; i < input.length; i++) {
        int min = Integer.MAX_VALUE;
        int minIndex = 0;
        /**
         * i번쨰 이후를 남은 정렬 부분이라고 하였을때, i~마지막원소까지 최솟값을 찾고, 
         * i번쨰 원소와 swap한다.
         */
        for (int j = i; j < input.length; j++) {
            if (input[j] < min) {
                min = input[j];
                minIndex = j;
            }
        }
        swap(input, minIndex, i);
    }
}

삽입 정렬

  • 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 삽입시켜 정렬하는 방식
  1. 현재 index에 있는 데이터 값을 선택한다.
  2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.
  3. 삽입 위치부터 index까지 shift연산을 수행한다.
  4. index를 증가시킨다.
  5. 전체 데이터 크기만큼 index가 커질떄까지 반복한다.
private void insertionSort(int[] input) {
    for (int i = 1; i < input.length; i++) {
        int current = input[i];
        for (int j = i; j - 1 >= 0; j--) {
            // 작거나 같다면 shift 연산을 수행하지 않아도됨.
            if (input[j-1] <= current){
                break;
            }
            // shift연산 수행
            input[j] = input[j - 1];
            // 삽입위치를 찾았다면 값을 넣어준다.
            if (input[j - 1] > current || j - 1 == 0) {
                input[j - 1] = current;
            }
        }
    }
}

상기 3개의 알고리즘은 모두 O(n2))의 시간복잡도를 가지고 있다. 말그대로 “빠른” 정렬 알고리즘인 퀵 정렬은 평균 시간복잡도 O(nlogn)을 가진다.

퀵 정렬

  • pivot(기준값)을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 분할-정복 알고리즘이다.

퀵 정렬은 앞선 n2 알고리즘들보다 상대적으로 직관적으로 이해하기는 어렵다.

[1]퀵 정렬 알고리즘

  1. 데이터를 분할하는 pivot을 설정한다.

  2. pivot을 기준으로 다음 과정을 거쳐 데이터를 2개의 집합으로 분리한다.

  3. start 포인터가 가르키는 데이터가 pivot이 가르키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다.

  4. end 포인터가 가르키는 데이터가 pivot이 가르키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다.

  5. start가 가르키는 데이터가 pivot이 가르키는 데이터보다 크고, end가 가르키는 데이터가 pivot보다 작으면 start,end 가 각각 가르키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다.

  6. start와 end가 만날떄까지 3~5과정을 반복한다.

  7. start와 end가 만나면 만난 지점에서 가르키는 데이터와 pivot이 가르키는 데이터를 비교하여 pivot이 가르키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가르키는 데이터를 삽입한다.

  8. pivot을 기준으로 왼/오른쪽 집합을 나누고, 분리 집합에서 다시끔 pivot을 선정한다. 1~7번 과정을 반복한다.

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

public int partition(int[] arr, int low, int high) {
    int pivot = arr[low]; // 피벗을 가장 왼쪽 값으로 선택
    int start = low;
    int end = high;

    while (start < end) {
        while (arr[start] <= pivot && start < high) {
            start++;
        }
        while (arr[end] > pivot) {
            end--;
        }
        if (start < end) {
            swap(arr, start, end);
        }
    }

    // 피벗과 end 지점의 값을 교환
    swap(arr, low, end);

    // 피벗이 위치한 인덱스 반환
    return end;
}

Reference

[1] https://upload.wikimedia.org/wikipedia/commons/9/9c/Quicksort-example.gif