알고리즘-퀵정렬(Quick Sort)

퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복 방법을 통해 주어진 배열을 정렬한다. 즉, 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

Process

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 pivot이라고한다.
2. pivot 앞에는 pivot보다 값이 작은 모든 원소들이 오고, pivot 뒤에는 pivot보다 값이 큰 모든 원소들이 오도록 pivot을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 pivot은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.

• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장한다.

Code(Java) - 가장 우측 인덱스를 pivot으로 설정

public class main {


    public static void main(String[] args) {
        int a[]={4,6,1,2,10,13,55};

    quickSort(a,0,6);
    for(int i =0;i< a.length;i++)
        System.out.println(a[i]);

    }

    public static void quickSort(int a[],int p, int r){
        if(p<r){
            int q=partition(a,p,r);       //분할 ,q = pivot의 위치
            quickSort(a,p,q-1);       //왼쪽 부분배열 정렬
            quickSort(a,q+1,r);       // 오른쪽 부분배열 정렬
        }
    }
    public static int partition(int a[],int p, int r){
        /*
        배열 a[p...r]의 원소들을 a[r]을 기준으로 양쪽으로 재배치하고 a[r]이 자리한 위치를 return 한다.
         */
        int x =a[r];
        int i = p-1;
        int j =p;
        while(j<r){
            if(a[j]<x){
                i=i+1;
                swap(a,i,j);
            }
            j++;
        }
        swap(a,i+1,j);
        return i+1;
    }

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


}

시간복잡도

1. 최선의 경우 (Best Case):

   피벗이 항상 배열을 반으로 정확히 나누는 경우입니다.
   이 경우, 매 단계에서 배열을 절반으로 나누므로, 배열의 크기 N이 계속 절반으로 줄어듭니다.
   시간복잡도: O(N log N)

2. 평균 경우 (Average Case):

   대부분의 경우 피벗이 배열을 적절하게 나누는 경우입니다.
   배열이 비교적 균등하게 나누어진다면, 재귀 호출의 깊이는 log N이 되고, 각 단계마다 배열의 모든 요소를 한 번씩 비교하게 됩니다.
   시간복잡도: O(N log N)

3. 최악의 경우 (Worst Case):

   피벗이 항상 배열의 가장 큰 값이나 가장 작은 값이 되는 경우입니다.
   이 경우 배열은 한 쪽으로만 계속 분할되며, 재귀 호출의 깊이는 배열의 크기 N과 같습니다.
   시간복잡도: O(N^2)
   
   

<정리>
최선의 경우: O(N log N)
평균 경우: O(N log N)
최악의 경우: O(N^2)

퀵정렬의 최악의 경우를 피하기 위해서는, 피벗을 잘 선택하는 전략이 중요합니다. 흔히 사용하는 피벗 선택 방법으로는 랜덤 피벗 선택, 중앙값 피벗 선택 등이 있습니다. 이러한 방법들은 평균적인 성능을 최적화하여 최악의 경우 발생 확률을 줄여줍니다.