[알고리즘] 정렬 - 퀵소트

1. 개념

배열에서 피봇을 하나 정한다. 맨 왼쪽에서 시작해서 배열을 살피는 화살표가 하나 있고, 맨 오른쪽에서 시작해서 배열을 살피는 화살표가 하나 있다. 왼쪽 시작 화살표를 옮겨가며 피봇보다 크거나 같은 원소를 찾는다. 오른쪽 시작 화살표를 옮겨가며 피봇보다 작은 원소를 찾는다. - a

만약 왼쪽 시작 화살표가 원소를 하나 찾고, 오른쪽 시작 화살표가 원소를 하나 찾으면 둘을 교환한다. 교환 후 왼쪽 시작 화살표는 아까 찾은 거 이후 부터 다시 피봇보다 크거나 같은 원소를 찾고, 오른쪽 시작 화살표는 아까 찾은 거 이후 부터 다시 피봇보다 작은 원소를 찾는다. -  b-1

만약 왼쪽 시작 화살표와 오른쪽 시작 화살표가 만나면 만난 위치에 있는 원소와 피봇을 교환한다. 교환된 피봇은 확정된다. - b-2

확정된 피봇 왼쪽과 오른쪽에 a, b-1, b-2의 과정을 반복한다.

 

2. 특징

• 구현 방법이 다양하다. 
• 분할 정복 방법이 적용된다. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 각각을 해결할 때는 재귀적으로 함수 호출을 진행하여 해결한다.
• 제자리 정렬이다. 정렬 대상이 되는 데이터 말고 다른 데이터는 필요하지 않다. 
• 불안정 정렬이다. 위치는 다르고 값은 같은 원소가 여러개 있을 때, 해당 원소의 상대적 위치가 정렬 후 바뀔 수 있다. 즉 1번에 있던 원소 2와 4번에 있던 원소 2가 있다고 할 때, 정렬 후에는 4번에 있던 게 더 앞에 있을 수도 있다는 것이다. 
• 특정 상태가 아닌 이상 평균 시간복잡도가 O(nlogn)으로 굉장히 빠르다. 하지만 최악의 경우에는 O(n2)의 시간복잡도를 가질 수도 있다.
  • 최악의 경우란 이미 정렬되어 있으면서 맨 왼쪽 피봇 선정 혹은 맨 오른쪽 피봇 선정 방식을 이용하는 경우다. 이 경우에는 3에서 언급하겠지만 분할이 불균형 하게 되어 한 쪽으로 치우친 트리를 갖게 된다. 따라서 시간복잡도가 O(n2)이 된다. 
  • 하지만 가운데를 피봇으로 선정하는 방식을 사용하면 이미 정렬되어 있는 경우에라도 분할이 균등하게 되어 약간은 더 효율적인 정렬이 가능해진다.

 

3. 시간복잡도

1) 비교 횟수

원소의 개수를 n이라고 했을 때, 맨 처음 피봇을 정하고 비교하는 횟수는 n

위의 단계를 거치고 난 이후 고정된 피봇 왼쪽에서 피봇 정하고 비교하는 횟수와 고정된 피봇 오른쪽에서 피봇 정하고 비교하는 횟수의 합은 n. 어차피 비교횟수는 총 원소의 개수의 합과 같아질 수밖에 없기 때문에.

따라서, 배열을 계속 분할해나가도 비교 횟수는 n으로 고정된다.

총 비교 횟수는 분할 횟수 * n

2) 분할 횟수

왼쪽 오른쪽 배열의 개수가 거의 같게 분할된다고 가정한 경우

원소의 개수가 n개라고 하자.

맨 처음 피봇을 정하고 비교를 진행한다. 이를 거치고 고정된 피봇을 기준으로 왼쪽과 오른쪽으로 분할이 된다. 분할이 1회 일어났다.

이 상태에서 비교를 진행한다. 이를 거치고 고정된 피봇을 기준으로 왼쪽과 오른쪽으로 분할이 된다. 분할이 2회 일어났다.

이 상태에서 비교를 진행한다. 이를 거치고 고정된 피봇을 기준으로 왼쪽과 오른쪽으로 분할이 된다. 분할이 3회 일어났다.

여기까지 하면 정렬이 완료된다. 분할은 log2n만큼 일어난다.

 

즉 n회씩 비교를 log2n 만큼 하면 된다. 여기서 2는 아래 작은 2를 의미한다.

1과 2를 보면 결국 시간복잡도는 O(nlogn)이라고 할 수 있다.

 

왼쪽 오른쪽 배열의 개수가 1개 : 나머지로 분할된다고 가정한 경우

위의 경우처럼 구해보면 분할 횟수가 n-1번이다.

 

즉, n회씩 비교를 n-1번 하게 되고 시간 복잡도는 O(n2)이 된다.

+)비교 횟수와 시간복잡도와의 연관성

비교를 n번 한다고 하면 그 만큼 배열을 돌면서 살펴야 하기 때문에 loop의 시간복잡도를 구할 수 있다. 

 

4. 코드

import java.io.*;
// 맨 왼쪽을 피봇으로 선택하는 방법
public class Main {
    public static void main(String[] args) throws IOException{
            int[] nums = {3, 5, 1, 8, 6};
            quickSort(nums, 0, nums.length-1);
            for(int num : nums){
                System.out.println(num);
            }


    }

    private static void quickSort(int[] nums, int l, int r){
        if(l >= r){
            return;
        }
        int pivot = partition(nums, l, r);
        quickSort(nums, l, pivot-1);
        quickSort(nums, pivot+1, r);
    }

    private static int partition(int[] nums, int l, int r){
        int left = l;
        int right = r;
        int pivot = nums[l];

        while(left < right){

            while(nums[right] > pivot && left < right){
                right--;
            }

            while(nums[left] <= pivot && left < right){
                left++;
            }


            swap(nums, left, right);
        }
        swap(nums, l, left);

        return left;
    }

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

import java.io.*;
// 가운데를 피봇으로 선택하는 방법

public class Main {
    public static void main(String[] args) throws IOException{
        int[] nums = {5, 1, 2, 6, 9};
        quickSort(nums, 0, nums.length-1);
        for(int num : nums){
            System.out.println(num);
        }

    }
    private static void quickSort(int[] nums, int l, int r){
        if(l >= r){
            return;
        }
        int pivot = partition(nums, l, r);
        quickSort(nums, l, pivot);
        quickSort(nums, pivot + 1, r);
    }

    private static int partition(int[] nums, int l, int r){
        int left = l-1;
        int right = r+1;
        int pivot = nums[(l+r)/2];

        while(true){
            do{
                left++;
            }while(nums[left] < pivot);

            do{
                right--;
            }while(nums[right] > pivot && left <= right);

            if(left >= right){
                return right;
            }

            swap(nums, left, right);
        }
    }

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

}

 

 

5. 관련 문제

백준 11004

GitHub - Lee-Min-Jung/coding_test_practice