[do it 알고리즘] 퀵 정렬

원리

• 리스트 안에 한 요소(피벗)를 선택
• 피벗을 기준으로 피벗보다 작은 요소는 모두 왼쪽, 큰 요소는 오른쪽으로
• 피벗을 제외한 왼쪽 리스트, 오른쪽 리스트를 다시 정리

코드

public class QuickSort{
    public static void main(String[] args) {
        int [] arr = {1,5,33,6,7,12,23};
        QuickSort(arr,0,arr.length-1);
        for(int data : arr){
            System.out.println(data);
        }
    }
    public static void QuickSort(int[] arr,int first,int last){
        int pivot = first;
        int left = pivot+1;
        int right = last;

        if(first>=last) return;
        while(left<=right){ // 엇갈릴때 까지
            while(left<=last && arr[left] <= arr[pivot]){left++;} // pivot 보다 큰값 나올때까지
            while(right>first && arr[right] >= arr[pivot]){right--;} // pivot 보다 작은값 나올때까지
            if (left <= right) { // 안 엇갈린 상태면 left,right 교환
                swap(arr,left,right);
            }else{ // 엇갈린 상태면 end와 pivot 교환
                swap(arr,right,pivot);
            }
        }
        QuickSort(arr,first,right-1); // 앞에서 부터 pivot 앞까지
        QuickSort(arr,right+1,last); // pivot 뒤부터 end까지
    }
    public static void swap(int[] arr,int a,int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

코드 해석

• 배열 가장 앞을 피벗으로 결정
• 투 포인터로 right= 피벗+1, left = 배열 마지막 원소
• 배열 길이가 1이면 정렬할 것이 없으니 return
• 엇갈릴 때까지 반복하여 피벗보다 큰 수 찾을 때까지 left++
• 피벗보다 작은 수 찾을 때까지 right--
• 찾았는데 안 엇갈린 상태면 left와 right 서로 위치 바꾸기
• 찾았는데 엇갈린 상태면 right와 피벗 서로 위치 바꾸기
• 다시 분할하여 피벗을 제외한 first ~ right-1 , right+1 ~ last까지 재귀 반복

특징

• 분할 정복 알고리즘의 하나로 평균적으로 빠른 수행 속도 O(NlogN)
• 비균등하게 분할
• 정렬된 리스트에서는 불균형 분할에 의해 수행시간이 O(N^2)만큼 걸림

---

중간값 피벗 정렬

• 중간값을 피벗으로 결정하여 최악의 시간 복잡도 O(N^2)을 피할 가능성을 높여준다

코드

public class QuickSort2 {
    public static void QuickSort(int[] arr){
        QuickSort(arr,0,arr.length-1);
    }
    public static void QuickSort(int[] arr,int first,int last){
        int part2 = partition(arr,first,last);
        if(first < part2-1){
            QuickSort(arr,first,part2-1);
        }
        if(part2 < last){
            QuickSort(arr,part2,last);
        }
    }
    public static int partition(int[] arr,int first,int last){
        int pivot = (first+last)/2;
        while(first <= last){
            while(arr[first] < arr[pivot]){
                first++;
            }while( arr[last] > arr[pivot]){
                last--;
            }
            if(first <= last){
                swap(arr,first,last);
                first++;
                last--;
            }
        }
        return first;
    }
    public static void swap(int[] arr,int start,int end){
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }
    public static void main(String[] args) {
        int[] arr = {30,1,4,5,2,6,8,11,20};

        QuickSort(arr);

        for(int data : arr){
            System.out.println(data);
        }
    }
}

코테에서도 종종 쓰이니 확실하게 하자