퀵소트란?

퀵소트?

• 배열을 피벗을 기준으로 나눠서 정렬하는 방식

• 피벗을 어떻게 선택함에 따라, 성능 차이가 존재

• 최악의 경우 O(n^2)까지 발생할 수 있음

• 베스트 케이스의 경우 O(nlogn)의 시간 복잡도를 가짐

• 공간복잡도는 O(logn), 퀵소트의 재귀적 호출때문에 호출 스택 공간이 필요

• 최악의 경우 O(n^2)이지만, Java의 팀소트에 퀵소트를 쓰는 이유는 참조 지역성의 원리때문

두 포인터를 이용한 구현방법?

• 피벗을 선택하고, 피벗과의 값 비교를 통해서 왼쪽과 오른쪽 포인터가 가르키는 값을 스왑

• 두 포인터가 겹치게 되면, 종료

• 베이스 케이스 처리가 중요(원소가 1개 혹은 2개인 경우)

하나의 포인터를 이용한 구현방법?

• 첫번째 원소를 피벗으로 선택하고, 첫번째 원소를 제외한 배열의 값들을 비교

• 포인터가 지난 값들은 모두, 피벗보다 작은 값이 된다.

• 포인터가 멈춰있는 경우에는, 피벗보다 큰 값이 된다.

• 모든 배열의 값이 탐색되면, 포인터의 뒤에는 피벗보다 작은 값들만 존재한다.

코드?

class Solution {
    void quickSort(int[] nums, int start, int end){
    	// 하나의 포인터를 이용한 구현방법
        if(start >= end)
            return;
        
        int pivot = nums[start];
        int p = start + 1;
        
        for(int i = start + 1; i <= end; i++){
            if(nums[i] <= pivot){
                swap(nums, p, i);
                p++;
            }    
        }
        swap(nums, start, p - 1);

        quickSort(nums, start, p - 2);
        quickSort(nums, p, end);
    }
    
    void quickSort2(int[] nums, int start, int end){
    	// 두 포인터를 이용한 구현방법
        if(start >= end)
            return;
        
        int s = start;
        int e = end;
        int pivot = nums[start];
        
        while(s < e){
            while(s <= e && nums[s] <= pivot) s++;
            while(e >= s && nums[e] > pivot) e--;
            
            if(s <= e){
                swap(nums, s, e);
            }
        }
        swap(nums, start, e);

        quickSort2(nums, start, e - 1);
        quickSort2(nums, e + 1, end);
    }
    
    void swap(int[] nums, int idx1, int idx2){
        int tmp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = tmp;
    }
    
    public int[] sortArray(int[] nums) {
        quickSort2(nums, 0, nums.length - 1);
        return nums;
    }
}