퀵 정렬 (Quick Sort) - Java

알고리즘

퀵 정렬은 기준값(pivot)을 선정해 해당 값도가 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 

평균적인 시간 복잡도는 O(nlogn)으로 다른 O(nlogn)의 알고리즘 중 가장 빠르다고 평가 된다.

퀵 정렬 과정 (출처 : https://www.enjoyalgorithms.com/blog/quick-sort-algorithm)

 

 

구체적인 내용

1. 기준점을 정하고 기준점을 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 이동 시키며 정렬을 진행 한다.
2.  이때 기준점이 되는 레코드는 한 번 정렬이 완료되면 더 이상 자리가 바뀌지 않는다.
3.  partition 함수를 통해 피봇을 기준으로 왼쪽, 오른쪽을 나누게 된다. 최종적으로 피봇의 위치는 low가 higt보다 커지는 순간으로 결정된다. 
4. 이렇게 피봇을 기준으로 한 번 정렬된 리스트는 다시 왼쪽, 오르쪽 리스트로 쪼개져 partition 함수를 호출하며 리스트가 1개가 될 때까지를 계속 쪼개지면 정렬을 한다.

 

 

시간 복잡도

 최선

리스트 분할이 항상 중앙에서 이루어진다고 가정 했을 때 n/2. n/4 ... n/2^k의 크기로 나누어 진다. 이때 패스의 횟수를 나타내는 k 는 logn개가 된다. 그리고 패스에 따라 평균 n 번 정도의 비교가 이루어지므로 비교 연산은 총 nlogn 만큼 실행된다.

최악

오히려 최악의 경우는 정렬이 대부분이 완료되었을 때다. 리스트의 분할이 불균형이 이루어져 패스의 개수는 n이 되고, 한 번의 패스에서 평균 n번 정도의 비교 연산이 수행되어 총 n^2의 시간 복잡도가 된다.

 

 

특징

• 다른 O(nlogn)의 시간 복잡도를 가지는 다른 정렬 알고리즘과 비교하였을 때 가장 빠르다.
  • 불필요한 데이터의 이동을 줄인다.
  • 한 번 결정된 피벗들이 추후 연산에서 제외된다.
• 추가 메모리 공간이 필요하지 않는다

 

코드

 public static void quick_sort(int left, int right, int [] list, int k){
        if(left < right){
            int p = partition(left, right, list);
            if(p == k) return;
            quick_sort(left, p-1, list, k);
            quick_sort(p+1, right, list, k);
        }
    }

    public static int partition(int left, int right, int [] list){
        // pivot이 첫번 째 요소일 때
        int low = left;
        int high = right +1;
        int pivot = list[low];
        do{
            do{
                low++;
            }while (list[low] < pivot && low <= right);

            do{
                high--;
            }while (list[high] > pivot && high >= left);

            if(low < high){
                int temp = list[low];
                list[low] = list[high];
                list[high] = temp;
            }
        } while(low < high);
        // pivot을 적절한 위치에 삽입
        int temp = list[high];
        list[high] = list[left] ;
        list[left] = temp;

        return high;
    }