퀵정렬(Quick Sort)

[아이디어]

정렬할 데이터의 가장 좌측 인덱스를 left, 가장 우측 인덱스를 right라고하고 정렬기준이 될 데이터를 pivot이라 합시다. left를 1씩 증가하고 right를 1씩 감소시켜가며 pivot을 기준으로 pivot이하인 경우는 pivot보다 왼편으로 pivot을 초과하는 경우 pivot보다 오른쪽으로 데이터를 이동하여 일부 정렬된 형태의 데이터로 만들어줍니다. 이렇게 만들어진 일부 정렬 형태의 데이터를 pivot 기준으로 분할하여 다시 퀵정렬 함수의 재귀 호출을 통해 정렬해 갑니다. 정렬과정에서 정렬에 필요한 데이터를 반씩 줄여가는 형태가 됩니다. left >= right이 되면 더이상 정렬할 요소가 없다는 것이니 별도의 로직 실행없이 return 합니다.

1. 정렬할 데이터 가운데 pivot으로 사용될 원소를 하나 무작위로 선택합니다.
   
   • 일반적으로 왼쪽, 오른쪽 끝 혹은 중간 값을 사용합니다.
     
2. 정렬할 데이터의 왼쪽 끝에 데이터 교환을 위한 인덱스인 left marker 지정합니다. 마찬가지로 오른쪽 끝에도 right marker를 지정합니다.
   
3. 본 항목 하위 순서대로 반복 수행하여 데이터를 교환합니다.
   
   1. left marker가 data 끝 index 이하일 동안 +1 해가면서 pivot 이상인 값을 찾으면 left marker를 증가시키지 않고 탈출합니다.
      
   2. left marker가 right marker 이상이거나 rigth marker가 data의 시작 index 이상일 동안 -1 해가면서 pivot 미만의 값을 찾은 경우 right marker를 감소시키지 않고 탈출합니다.
      
   3. left marker < right marker인 경우 data[left marker]와 data[right marker]를 교환하고 데이터 교환 루프를 계속합니다.
      
   4. left marker == right marker인 경우 data[left marker]와 pivot을 교환하고 데이터 교환 루프를 빠져나갑니다.
      
   5. left marker > right marker인 경우 데이터 교환 루프를 빠져나갑니다.
      
4. 이제 현재 left marker에는 처음 pivot으로 지정한 값이 들어가 있습니다. left marker를 partition으로써 반환합니다.
   
5. partition에 해당하는 index는 정렬된 것이므로 그것을 기준으로 좌(left ~ partition-1),우측(partition+1 ~ right)의 정렬되지 않은 데이터들에 대해 각각 퀵소트 함수를 재귀호출하여 데이터를 정렬해 나갑니다.

 

[특징]

1. 평균 시간복잡도는 O(nlogn)입니다. 최악의 경우 O(n²)까지 걸릴 수 있습니다.
2. 정렬할 데이터에 동일한 값의 원소가 두 개 이상 있는 경우 그 순서를 보장할 수 없습니다. (불안정 정렬)

 

[구현]

 

1. 본인 작성 코드 - 리스트의 오른쪽 끝을 pivot으로 잡아 구현.

def quick_sort(data, left, right, reverse_order):
    pivot = data[right]
    left_marker = left
    right_marker = right - 1
    if left >= right:
        return
    else:
        while True:
            if reverse_order:
                for i in range(left_marker, right + 1, 1):
                    left_marker = i
                    if data[i] < pivot:
                        break
                for i in range(right_marker, left - 1, -1):
                    right_marker = i
                    if left_marker >= right_marker or data[i] >= pivot:
                        break
            else:
                for i in range(left_marker, right + 1, 1):
                    left_marker = i
                    if data[i] >= pivot:
                        break
                for i in range(right_marker, left - 1, -1):
                    right_marker = i
                    if left_marker >= right_marker or data[i] < pivot:
                        break
            if left_marker < right_marker:
                data[left_marker], data[right_marker] = data[right_marker], data[left_marker]
            elif left_marker == right_marker:
                data[left_marker], data[right] = data[right], data[left_marker]
                break
            elif left_marker > right_marker:
                break
        partition = left_marker
        quick_sort(data, left, partition - 1, reverse_order)
        quick_sort(data, partition + 1, right, reverse_order)


data = [3, 5, 8, 1, 2, 9, 4, 7, 6]
print('not sorted: ', ', '.join(map(str, data)))
quick_sort(data, 0, len(data) - 1, True)
print('sorted: ', ', '.join(map(str, data)))

 

2. 이코테 코드 1 - 리스트의 왼쪽 끝을 pivot으로 사용

def quick_sort(data, start, end, reverse_order):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        if reverse_order:
            while left <= end and data[left] >= data[pivot]:
                left += 1
            while right > start and data[right] <= data[pivot]:
                right -= 1
        else:
            while left <= end and data[left] <= data[pivot]:
                left += 1
            while right > start and data[right] >= data[pivot]:
                right -= 1
        if left > right:
            data[right], data[pivot] = data[pivot], data[right]
        else:
            data[left], data[right] = data[right], data[left]
    quick_sort(data, start, right - 1, reverse_order)
    quick_sort(data, right + 1, end, reverse_order)


data = [3, 5, 8, 1, 2, 9, 4, 7, 6]
print('not sorted: ', ', '.join(map(str, data)))
quick_sort(data, 0, len(data) - 1, False)
print('not sorted: ', ', '.join(map(str, data)))

 

3. 이코테 코드2 - 파이썬 문법을 활용한 간단한 코드

def quick_sort(data, reverse_order):
    if len(data) <= 1:
        return data

    pivot = data[0]
    tail = data[1:]

    if reverse_order:
        left_side = [x for x in tail if x >= pivot]
        right_side = [x for x in tail if x < pivot]
    else:
        left_side = [x for x in tail if x <= pivot]
        right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side, reverse_order) + [pivot] + quick_sort(right_side, reverse_order)


data = [3, 5, 8, 1, 2, 9, 4, 7, 6]
print('not sorted:', ', '.join(map(str, data)))
data = quick_sort(data, False)
print('sorted:', ', '.join(map(str, data)))

 

4. java로 구현 ( 2번 python code를 java로)

public class Main {

    public static void main(String[] args) {
        int[] data = new int[]{3, 5, 8, 1, 2, 9, 4, 7, 6};
        printArray(data);
        quickSort(data, 0, data.length - 1, false);
        printArray(data);
    }
    public static void quickSort(int[] data, int startIdx, int endIdx, boolean reverseOrder){
        if(startIdx >= endIdx) {
            return;
        }
        // startIdx is pivot index
        int left = startIdx + 1;
        int right = endIdx;
        int temp;
        while(left <= right){
            if(reverseOrder) {
                while (left <= endIdx && data[left] >= data[startIdx]) {
                    left += 1;
                }
                while (right > startIdx && data[right] <= data[startIdx]) {
                    right -= 1;
                }
            }
            else {
                while (left <= endIdx && data[left] <= data[startIdx]) {
                    left += 1;
                }
                while (right > startIdx && data[right] >= data[startIdx]) {
                    right -= 1;
                }
            }
            if(left > right) {
                temp = data[right];
                data[right] = data[startIdx];
                data[startIdx] = temp;
            }
            else {
                temp = data[left];
                data[left] = data[right];
                data[right] = temp;
            }
        }
        quickSort(data, startIdx, right - 1, reverseOrder);
        quickSort(data, right + 1, endIdx, reverseOrder);
    }
    public static void printArray(int[] data) {
        int len = data.length;
        System.out.print("not-sorted: ");
        for(int i = 0; i < len; i++) {
            if(i < len - 1) {
                System.out.print(data[i] + ", ");
            }
            else {
                System.out.println(data[i]);
            }
        }
    }
}