[알고리즘] 정렬(퀵 소트) 알고리즘 (2)

잘쓰면 정말 효율적인 퀵 소트

 

퀵소트의 시간 복잡도는 O(nlogn)이다.

또한 퀵 소트에 대해 제대로 이해만 한다면, 더욱더 빠르게 답을 구하는 것도 가능하다.

 

 

퀵 소트의 전반적인 과정에 대해 이해해보자.

 

1. 피벗을 하나 선택한다.
이 때, 피벗의 부분 배열의 가장 왼쪽을 선택하냐, 중간을 선택하냐, 제일 오른쪽을 선택하냐에 따라서 효율이 다를 수 있다.

2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값과 작은 값을 찾는다.
헷갈린다면, 정렬이라고 생각해보자. 왼쪽에는 작은 값들부터 오른쪽에는 큰 값까지 있어야 한다.
그럴려면, 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾아 바꾸어 줄 필요가 있다.

3. 양쪽에서 찾은 값을 서로 바꾸어 준다.

4. 왼쪽과 오른쪽에서 탐색하는 위치가 서로 엇갈리지 않을 때(즉, 같은 경우도 포함)까지 2의 과정을 계속해서 반복해준다.

5. 엇갈린 기점을 기준으로 두 개의 부분 리스트로 나누어, 길이가 1이 아닐 때까지 1의 과정부터 반복해준다.

6. 인접한 부분리스트끼리 합친다.

 

 

만약 이 과정을 이해할 수 있다면, 쉽게 퀵소트를 구현할 수 있을 것이다.

 

퀵 소트의 기본적인 모양

 

일반적으로 퀵소트를 사용할 때, 다음과 같이 코드를 작성한다.

 

public class QuickSorter {
    public static void quickSort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int low, int high) {
        if (low >= high) return;

        int mid = partition(arr, low, high);
        sort(arr, low, mid - 1);
        sort(arr, mid, high);
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[(low + high) / 2];
        while (low <= high) {
            while (arr[low] < pivot) low++;
            while (arr[high] > pivot) high--;
            if (low <= high) {
                swap(arr, low, high);
                low++;
                high--;
            }
        }
        return low;
    }

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

 

제일 기본적인 모양이며, 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽에 치중하는 파티셔닝 과정이 포함되어 있다.

 

 

 

퀵 소트의 응용

 

예시 문제로 백준 11004번 문제를 참고해보자.

 

11004번: K번째 수

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] A = new int[n];

        st = new StringTokenizer(bf.readLine());
        for(int i=0; i<n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }


        quick_sort(A, 0, n-1, k-1);
        System.out.println(A[k-1]);
    }
    public static void quick_sort(int[] A, int S, int E, int K) {
        if(S < E) {
          int pivot = partition(A, S, E);
          if (pivot == K) {
              return;
          } else if (K < pivot) {
              quick_sort(A, S ,pivot-1, K);
          } else {
              quick_sort(A, pivot+1, E, K);
          }
        }
    }
    public static int partition(int[] A, int S, int E) {
        if (S + 1 == E) {
            if(A[S] > A[E]) swap(A, S, E);
            return E;
        }
        int M = (S+E) / 2;
        swap(A, S, M);
        int pivot = A[S];
        int i = S+1, j = E;
        while(i <= j) {
            while(pivot < A[j] && j > 0) {
                j--;
            }
            while(pivot > A[i] && i < A.length -1) {
                i++;
            }
            if (i <= j) {
                swap(A, i++, j--);
            }
        }
        A[S] = A[j];
        A[j] = pivot;
        return j;
    }


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

 

해당 문제는 k번째 값을 찾기 위해서 파티셔닝 과정에서 반환되는 피벗 값을 검사한다.

이 과정을 통해 k번째 값을 찾으면, 그 즉시 프로그램을 중지시켜 비효율적인 연산을 방지한다.

 

또한 똑같이 중간 값을 피벗으로 사용하나, 연산의 편리성을 위해서 제일 처음에 pivot을 맨 앞으로 이동시킨다.

이후, 두 집합을 나누어 주는 위치와 pivot을 swap할 수 있다.(사실 pivot 위치를 중간으로 했다면 이 과정이 필요 없긴하다. 더 효율적인지는 모르겠다.)

 

A[S] = A[j];
A[j] = pivot

여기서 A[S]는 코드 상에서 pivot 값과 같다고 선언해주었기에 사실 상 같다.

 

파티셔닝 결과로 반환되고, 두 집합을 나누어주는 위치를 반환해주는 피벗 값의 위치는 고정적이다.

이는 이 문제 뿐만 아니라, 일반적인 퀵 소트의 경우에도 그러하다.

 

즉, 이 위치 자체가 몇 번째 위치인지를 나타내준다는 것이다.

 

이 값을 기준으로 이제 정답을 도출할 수 있다.

 

 

Reference

- Do it! 코딩 테스트 - 기초 편

자바 [JAVA] - 퀵 정렬 (Quick Sort)

[알고리즘] 퀵 정렬 - Quick Sort (Python, Java)