퀵 정렬

• 평균 성능이 가장 좋은 정렬 방법

입력 리스트 : (5, 3, 8, 4, 9, 1, 6, 2, 7)

1) 정렬할 레코드 중 피벗(pivot) 레코드를 선택
2) 정렬할 레코드들을 다시 정돈
- 피벗의 왼쪽 : 피벗의 키보다 작거나 같은 레코드들을 위치
- 피벗의 오른쪽 : 피벗의 키보다 크거나 같은 레코드들을 위치
3) 퀵 정렬을 순환적으로 사용
- 피벗의 왼쪽과 오른쪽의 레코드들은 서로 독립적으로 정렬

quickSort 분석

• 최악의 경우 복잡도 : O(n2)

- 한 레코드의 위치가 정확히 정해질 때마다 그 레코드의 왼쪽과 오른쪽의 서브리스트 크기가 같을 경우 - 크기가 n/2인 두 개의 서브리스트를 정렬하는 작업과 동일 - 크기가 n인 리스트에서 한 레코드를 위치시키는데 필요한 시간 : O(n)

• 평균 연산 시간 : O(nlogn)
• 평균 성능이 가장 좋음 / 최악의 경우 : O(n2)

구현

public class Main {

    public static void main(String[] args) {

        int[] data = {5, 3, 8, 4, 9, 1, 6, 2, 7};

        sort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }

    public static void sort(int[] data, int l, int r){
        int left = l;
        int right = r;
        int pivot = data[(l+r)/2];

        do{
            while(data[left] < pivot) left++;
            while(data[right] > pivot) right--;
            if(left <= right){
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        }while (left <= right);

        if(l < right) sort(data, l, right);
        if(r > left) sort(data, left, r);
    }
}

---

reference

• 고려대학교 김상곤 교수님 강의 중
• Algorithm | Sort : 퀵 정렬
• Algorithm | Sort : 퀵 정렬