[Algorithm] 정렬(Sort)-퀵 정렬(Quick Sort)

정렬(Sort) - 퀵 정렬(Quick Sort)Permalink

Quick Sort(퀵 정렬)Permalink

  • Divide and Conquer 알고리즘
  • 평균수행능력이 가장 뛰어남
  • 분할중심값을 pivot 또는 control key 라고 함

algorithm-quick_sort_partition_animation

연산Permalink

  1. 피벗값을 선택(맨 오른쪽, 왼쪽 또는 중앙값을 선택)
  2. 피벗 값을 사용하여 배열 분할
  3. 파티션 자료 갯수가 1이 될때까지 왼쪽 파티션을 재귀로 빠르게 정렬
  4. 파티션 자료 갯수가 1이 될때까지 오른쪽 파티션을 재귀로 빠르게 정렬

pseudo codePermalink

quickSort(arr[], low, high)
{
    if (low < high)
    {
        pi = partition(arr, low, high);

        quickSort(arr, low, pi );  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

partition (arr[], low, high)
{
    pivot = arr[(low+high)/2];  

    while(arr[left]<pivot){
        left++
    }

    while(arr[right]>pivot){
        right--
    }

    if (left <= right){
        swap(arr[left],arr[right])
        left++
        right--
    }

    return right
}

java로 퀵 정렬 구현Permalink

전체소스보기

public static void sort(int[] arr, int start, int end) {
    //int pivot = arr[end];
    int left = start;
    int right = end ;

    // pivot값을 가운데 값으로 셋팅
    int pivot = arr[(left+right)/2];
    while( left <= right) {

        //pivot 왼쪽의 값이  pivot 값 보다 작은 경우 다음 element 탐색
        while(arr[left] < pivot) {
            left++;
        }

        // pivot 오른쪽의 값이 pivot값 보다 큰 경우 다음 element 탐색
        while(arr[right] > pivot) {
            right--;
        }

        //왼쪽 값 > pivot 이면서
        //오른쪽 값 < pivot 이면서
        //왼쪽값 < 오른쪽 값 인 경우
        if( left <= right) {
            //swap
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

            //그리고 다음 element 탐색
            left++;
            right--;
        }
    }

    if (start < right ) {
        // 분할된 왼쪽 부분 순환 처리
        sort(arr, start, right);
    }

    if (left < end ) {
        // 분할된 오른쪽 부분 순환 처리
        sort(arr, left, end);
    }
}
  • output
[ * Quick Sort * ]
- before quick sort ----------
[9,5,6,4,7,2,1,8,3]
- sorting ----------
[9,5,6,4,7,2,1,8,3]
[3,5,6,4,1,2,7,8,9]
[3,5,2,4,1,6,7,8,9]
[1,2,5,4,3,6,7,8,9]
[1,2,5,4,3,6,7,8,9]
[1,2,3,4,5,6,7,8,9]

ComplexityPermalink

Complexity Best Case Average Case Worst Case
Time O(n) O(n log n) O(n2)
Space     O(log n)

referencesPermalink

https://www.javatpoint.com/quick-sort
https://www.geeksforgeeks.org/quick-sort/?ref=lbp/
https://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm
https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
https://codenuclear.com/quick-sort-algorithm/