[ 알고리즘 ] 퀵 정렬 (Quick Sort)

퀵 정렬이란?

피벗(pivot)을 사용한 정렬 알고리즘이며 피벗에 따라 시간복잡도가 달라질 수 있다. 병합 정렬과 같은 분할 정복 알고리즘.

많은 양의 데이터를 정렬하는데 유용.

 

 

 

시간복잡도

평균	O(nlogn)
최악	O(n^2)

 

 

 

동작방식

1.  배열에서 하나의 요소를 기준으로 잡고 이를 피벗(Pivot) 이라고 한다.
   기준점은 아무기준이나 상관없으나, 보통 중앙값을 잡음.
   

   

2. start는 pivot보다 크거나 같은 값을 찾을 때까지 움직이고, end는 pivot보다 작거나 같은 값을 찾을 때까지 움직인다.
   

   

   
   
3. start와 end가 모두 충족 될 경우 swap해준다.
   

   

   

4. 2번의 과정을 반복한다.
   

   

   

   

5. start와 end의 순서가 역전되면 반복문을 종료하고, start값을 기준으로 배열을 파티셔닝한다.
   

   

   end와 start의 순서가 역전됨

   
   

   

6. 나눠진 파티션 별로 다시 위의 과정을 재귀적으로 반복하면 결국 정렬된다.
   1파티션 : [3, 2, 4, 1, 0]
   2파티션 : [5, 7, 6, 8, 9]
   위 두개의 파티션별로 1~6번과정을 반복수행.
   

   

   

 

 

 

 

자바로 구현

public class Sort{
	public static void main(String[] args){
    	int[] arr = {6,2,5,3,8,1,4,20,78};
        int length = arr.length();
        quickSort(arr, 0, length-1);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void quickSort(int[] arr, int start, int end) {
        int part2 = partition(arr, start, end); //part2 : 오른쪽 파티션의 시작점

        //만약 start가 part2-1과 같으면 정렬할 필요가 없기때문에 if문에서 설정
        if(start < part2 - 1){
            quickSort(arr, start, part2-1);//end는 오른쪽 파티션의 시작점에서 왼쪽으로 한칸
        }
        //만약 part2의 시작점이 end와 같으면 정렬할 필요가 없기 때문에 if문에서 설정
        if(part2 < end){
            quickSort(arr, part2, end);
        }
    }
    
    public static int partition(int[] arr, int start, int end){
        int m = (start + end)/2;
        int pivot = arr[m]; // 해당 파티션의 중간에 있는 값

        //start와 end가 엇갈릴때까지 반복
        while(start <= end){

            // start가 피봇보다 작으면 start++ (피봇보다 큰 값이 나올때까지 반복)
            while(arr[start] < pivot)start++;

            //end가 피봇보다 크면 end-- (피봇보다 작은 값이 나올때까지 반복)
            while(arr[end] > pivot)end--;

            //start와 end가 서로 엇갈리지 않았으면 swap
            if(start <= end){
                swap(arr,start,end);
                start++;
                end--;
            }
        }

        return start; //새로 나뉠 파티션의 첫번째 인덱스를 반환 (part2)
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

 

 

참고

https://innovation123.tistory.com/84

[JAVA] 퀵 정렬 (Quick Sort)