퀵(Quick) 정렬

퀵(Quick) 정렬

- O(N logN)

- pivot을 기준으로 하여 큰 값과 작은 값을 찾아 바꿔가며 정렬하는 것입니다.

▶ [예제] 퀵 정렬 구현  

[예제] 퀵 정렬 구현

시뮬레이션

① 기준 Pivot을 첫번째 원소로 설정합니다.

 

② 좌측에서 pivot 값보다 큰 값을 찾습니다.

    우측에서 pivot 값보다 작은 값을 찾습니다.

    arr[left] = 8 / arr[right] = 2

 

③ 찾은 두 값의 위치를 바꿔 줍니다.

 

④ 이러한 작업을 좌측에서 찾은 값이 우측에서 찾은 값보다 우측에 위치할 때까지 반복

    arr[left] = 9 / arr[right] = 1

 

⑤ 위치 swap

 

⑥ arr[left] = 1 / arr[right] = 6

    위치: left  < right

 

⑦ right와 pivot의 위치 swap

 

⑧ 위치가 바뀐 pivot을 중심으로 이분해서 재귀 수행

    새로운 구간: [첫번째 원소, right-1], [right+1, 마지막 원소]

* 퀵 정렬은 O(N logN)으로 다른 정렬 알고리즘보다 상대적으로 빠르지만,

주어진 원소의 순서가 너무 평향적인 경우 연산의 양이 늘어나 O(N2)이 발생할 수 있습니다.

 

구현

C / C++

void quickSort(int start, int end) {
    if (start >= end) return;
    int pivot = start, left = start + 1, right = end;
    while (1) {
        while (left <= end && arr[left] <= arr[pivot]) left++;
        while (right > start && arr[right] >= arr[pivot]) right--;
        if (left > right) {
            swap(&arr[pivot], &arr[right]);
            break;
        }
        else swap(&arr[left], &arr[right]);
    }
    quickSort(start, right - 1);
    quickSort(right + 1, end);
}

 

Java

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class boj_2751 {
    
    public static void Swap(int[] arr,int first,int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
    public static void QuickSort(int[] arr,int left,int right) {
        if(left >= right) return;
        int pivot = arr[right];
        int l = left;
        int r = right-1;
        
        while(l <= r) {    // 교차하기 전까지 진행
            while(l<=r && arr[l]<=pivot) l++;
            while(l<=r && arr[r]>=pivot) r--;
            if(l<r) Swap(arr,l,r);
        }
        Swap(arr,l,right);
        QuickSort(arr,left,l-1);
        QuickSort(arr,l+1,right);
    }
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine().trim());
        int arr[] = new int[N];
        
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(br.readLine().trim());
        
        QuickSort(arr,0,N-1);
        
        for(int i=0;i<N;i++)
            sb.append(arr[i]+"\n");
        
        System.out.println(sb);
    }
}