[Java]Quick Sort

merge sort와 마찬가지로 분할 정복 알고리즘(divide and conquer)을 이용한 정렬 방식

 

divide and conquer
문제를 나눌 수 있을 때까지 나누고 , 서브 문제들을 동일하게 재귀적인 방식으로 해결한다.
만약 더이상 나눌 수 없다면 직접 해결한다.

 

💡퀵정렬 원리

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.(피봇을 선정하는 기준에 따라 다양한 퀵소트 구현 방법이 나올 수 있다.)
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗의 위치는 확정되므로 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

 

-범위 -기준 -비교 -swap 이 4가지만 기억하면 된다.

 

 

 

[2,1,3,7,5,4] 이들어있는 배열을 젤 오른쪽 수를 피봇으로 선정하여 퀵 소트로 정렬하는 과정을 그림으로 나타내보면 다음과 같다.

 

젤 오른쪽 수인 4를 피봇으로 선정하였고, 정렬하면 피봇의 위치는 arr[3] , arr[3]의 왼쪽 인덱스에는 피봇보다 작은 수, 오른쪽 인덱스에는 피봇보다 큰 수들이 오게 된다.

 

다시 피봇을 기준으로 나뉘어진 두 배열의 각 오른쪽을 피봇으로 설정하고,element가 1이 될 때까지 재귀적으로 정렬을 반복 해준다. 

먼저 피봇을 기준으로 왼쪽 배열을 정렬해주면 다음과 같다.  

다음으로 피봇을 기준으로 오른쪽 부분도 정렬해준다.

다음과 같은 과정을 거치고 나면 정렬이 된 것을 볼 수 있다.

전체 그림으로 보면 다음과 같다

 

 

😃퀵정렬 코드

가장 오른쪽 수 arr[r] 을 피벗으로 설정하여 구현해 보았다.

  static void quickSort(int[] arr, int l, int r){
        if(l<r){ //종료 조건 : element가 하나 남았을 때
            int p = paritition(arr,l,r);
            System.out.println("quick arr : " + Arrays.toString(arr));

            quickSort(arr,l,p-1); //피봇을 기준으로 왼쪽 정렬
            quickSort(arr,p+1,r); //피봇을 기준으로 오른쪽 정렬

        }
    }

    static int paritition(int[]arr, int l, int r){
        int pivot = arr[r]; //제일 오른쪽 수를 피봇으로 삼는 퀵정렬
        int idx = l-1; //자리를 바꿀 인덱스 = 피봇을 기준으로 더 작은 수가 들어있는 인덱스

        //피봇의 전 위치까지 돌면서 피봇보다 작은 수를 앞 인덱스에 차례로 담아줌
        for(int j=l; j<= r-1; j++){
            if(arr[j]<=pivot){
                idx++;
                swap(arr,idx,j);
            }
        }swap(arr,idx+1,r); //피봇 보다 작은 수가 들어있는 idx 보다 한칸 뒤는 피봇의 위치가 됨
        return idx+1 ; //피봇의 위치 리턴
    }
    static void swap(int[]arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

코드에 의하면 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다.

 

 

 

이제 길이가 8인 배열을 다음 퀵 정렬 메소드로 정렬해보자

 

    public static void main(String[] args){
        int[] arr= {8,2,4,5,1,7,3,6};
        quickSort(arr,0,7);

    }

 

 

⏱️시간 복잡도

best/average : nlogn

worst : n^2 

 

최악의 경우는 이미 정렬이 된 상태에서 피봇을 맨 왼족이나 오른쪽으로 잡는 경우 재귀의 깊이가 깊어지기 떄문에 시간 복잡도가 n^2까지 나올 수 있으나, 평균적 상황에서는 일반적 nlogn보다 빠르며, 굉장히 빠른 정렬 방법에 속하기 때문에 많이 사용된다.

 

 

 

 

🔎Merge sort와의 비교

 

같은 배열에 대하여 분할 정복 알고리즘인 merge sort의 정렬 과정과 비교해보면 재귀의 깊이가 더 짧은 것을 볼 수 있다.

퀵정렬                                                                                                                              머지정렬

 

참고자료

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

https://youtu.be/cWH49IKDIiI