[Java+Python]퀵 정렬(Quick Sort)

<Java + Python>으로 구현한 다른 정렬:

 

[Java+Python]삽입 정렬(Insert Sort)

[Java+Python]버블 정렬(Bubble Sort)

[Java+Python]선택 정렬(Selection Sort)

[Java+Python]병합 정렬(Merge Sort)

[Java+Python]힙 정렬(Heap Sort)

[Java+Python]카운팅 정렬(Counting Sort)

 

퀵 정렬은 1959년 영국에서 태어난 정렬 방식이다.

 

직관적인 이름대로 일반적으로 비슷한 속도의 병합 정렬, 힙 정렬보다 빠른 성능을 나타내며

 

힙 정렬과 추가적인 메모리를 요구하지 않기 때문에 자원 이용에 이점이 있다.

 

 다만 안정 정렬이 아니라는 단점이 있어 파이썬에서는 도입하지 않고 있다고 한다.

 

추가로 데이터 접근 시간이 오래 걸리는 Secondary Memory에서의 성능은 병합 정렬에 밀리기 때문에

 

최근에는 데이터를 블럭 단위로 읽어와 퀵 정렬을 수행한 뒤 블록 간에 병합정렬을 실시한다고 한다.

 

계속해서 알고리즘과 구현을 살펴보자.

 

Algorithm

 

퀵 정렬은 일반적으로 아래와 같이 분할 정복(Divide and Conquer)으로 동작한다.

 

1. 정해진 기준에 따라 Pivot(기준점)을 잡는다.
2. Pivot보다 작은 값을 앞으로, 큰 값을 뒤로 보낸다(이를 Partition Step이라 한다).
   
   
   1. 가장 왼쪽과 오른쪽을 각각 lo, hi로 라벨링한다.
   2. Pivot보다 작은 값을 만날 때까지 hi의 인덱스를 하나씩 줄인다.
   3. hi <Pivot이 되면 lo> Pivot이 될 때까지 lo의 인덱스를 하나씩 늘린다.
   4. 2, 3번 조건을 만족하면 두 숫자를 교환한다.
   5. 2번으로 돌아간다.
   6. hi와 lo의 인덱스가 같아지면 해당 원소를 Pivot과 교환한다. 이때 Pivot은 제 자리를 찾는다.
3. 과정이 모두 끝나면 Pivot을 중심으로 리스트를 둘로 쪼갠다(Divide).
   
   
   • 이 경우에 병합 정렬과 다르게 리스트가 비대칭으로 쪼개질 가능성이 있다.
4. 1 ~ 3의 과정을 반복한다.
5. 쪼개진 리스트의 크기가 0 또는 1이 되면 인접한 리스트부터 순서대로 합친다(Conquer).
6. 정렬 끝

단순한 로직이고 그만큼 실행 속도도 빠르지만, 1번에서 강조된 Pivot을 잡는 기준에 따라 정렬의 성능이 달라진다.

 

때문에 Pivot을 정하는 여러 기준이 나와 있으며, 몇 가지만 언급하면 아래와 같다.

 

• 가장 왼쪽/ 오른쪽/ 중간의 값으로 정하기
• 랜덤으로 정하기
• 3, 9개의 원소를 골라 그 중앙값으로 정하기

하지만 위와 같은 방법도 최악의 경우를 모두 피하는 것은 불가능하기 때문에,

 

특정 깊이 이상의 재귀 호출이 발생하면 힙 정렬을 사용하는 하이브리드 정렬(인트로 정렬)을 사용하기도 한다.

 

아래에 나올 그림과 구현 방법은 그중 가장 간단한, 가장 왼쪽의 값을 Pivot으로 정하는 방식이다.

 

처음 볼 땐 잘 이해가 안 되지만 직접 그림을 그리고 구현해보니 조금 알 것 같다.

 

Implementation

 

위 그림을 그대로 코드로 옮겨 보자.

 

재귀는 아무리 생각해도 어렵지만 이렇게 저렇게 자꾸 쓰게 되는 걸 보니 역시 알아야 하는 건가 보다.

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {

        int[] arr = {4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0};

        quickSortImpl(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }

    public static void quickSortImpl(int[] arr, int lo, int hi) {

        if (lo >= hi) return; // 대상 배열의 크기가 1 이하일 경우 탈출

        int pivot = partitionStep(arr, lo, hi); // Partition Step 진행

        quickSortImpl(arr, lo, pivot - 1); // 정렬이 끝난 pivot 기준으로 배열 쪼개서 재귀호출(왼쪽)
        quickSortImpl(arr, pivot + 1, hi); // 오른쪽
    }

    public static int partitionStep(int[] arr, int lo, int hi) {

        int left = lo; // 주어진 배열의 lo, hi, pivot 설정
        int right = hi;
        int pivot = arr[lo];

        while (left < right) {

            while (arr[right] >= pivot && left < right) { // pivot 보다 작은 값을 만날 때까지 right--;
                right--;
            }

            while (arr[left] <= pivot && left < right) { // pivot 보다 큰 값을 만날 때까지 left++
                left++;
            }

            swap(arr, left, right); // 값을 찾으면 스왑. 못 찾으면 left = right 인 곳에서 자체 스왑
        }

        swap(arr, lo, left); // left = right 인 원소와 pivot 교환

        return left; // pivot 이 옯겨간, 즉 정렬된 곳의 인덱스 반환
    }

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

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]

다음은 파이썬 구현이다.

target = [4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0]


def swap(lst, i, j):
    temp = lst[i]
    lst[i] = lst[j]
    lst[j] = temp


def partition_step(lst, lo, hi):
    left = lo
    right = hi
    pivot = lst[lo]

    while left < right:
        # pivot 보다 작은 값을 만날 때까지 right -= 1;
        while lst[right] >= pivot and left < right:
            right -= 1
        # pivot 보다 큰 값을 만날 때까지 left += 1;
        while lst[left] <= pivot and left < right:
            left += 1
        # 값을 찾으면 스왑. 못 찾으면 left = right 인 곳에서 자체 스왑
        swap(lst, left, right)

    # left = right 인 원소와 pivot 교환
    swap(lst, lo, left)
    # pivot 이 옯겨간, 즉 정렬된 곳의 인덱스 반환
    return left


def quick_sort(lst, lo, hi):
    # 대상 배열의 크기가 1 이하일 경우 탈출
    if lo >= hi:
        return

    # Partition Step 진행
    pivot = partition_step(lst, lo, hi)

    # 정렬이 끝난 pivot 기준으로 배열 쪼개서 재귀호출(왼쪽)
    quick_sort(lst, lo, pivot - 1)
    # 정렬이 끝난 pivot 기준으로 배열 쪼개서 재귀호출(오른쪽)
    quick_sort(lst, pivot + 1, hi)


quick_sort(target, 0, len(target) - 1)

print(target)

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]