Quick Sort (퀵 정렬)

합병 정렬 (Merge Sort)와 같이, 퀵 정렬도 분할 정복 메서드를 이용하는 정렬 알고리즘이다. 다른 분할 정복 알고리즘과 같이 정렬되지 않은 한 배열을 둘로 나누다. 바로 배열을 나누기 위해 파티션 (partition)알고리즘을 추가로 구현했다.

 

 

 

합병 정렬과 다르게, 퀵 정렬은 가운데 지점 (midpoint)에서 배열을 나누지 않는다. 배열은 나눌때 한 배열은 지점 (pivot)보다 작은 정수들이 들어있고 나머지 한 배열은 지점보다 큰 정수들이 들어있다. 반복적으로 지점이 바뀌어지면서 배열은 반복적으로 나누어진다 각 배열에 1개의 정수가 남을 때 까지. 

 

 

이제, 합병 정렬과 마찬가지로, 모든 배열들을 다시 한 배열로 합치면서 동시에 정렬 시킨다. 

 

 

이해하기 쉽게 비주얼을 추가했다.

메서드: 분할 정복 (Divide and Conquer)

 

 

퀵 정렬 알고리즘의 의사코드는 다음과 같다.

 

  Quick-Sort(A, l, r)
    if l < r
        q = Partition(A, l, r)
        QuickSort(A, l, q - 1)
        QuickSort(A, q + 1, r)

 

 

퀵 정렬 내에서 사용되는 Partition의 의사코드는 다음과 같다.

 

  Partition(A, l, r)
    x = A[r]
    i = l - 1
    for j = l to r - 1
        if A[j] <= x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1

 

 

l과 r는 왼쪽 (left)과 오른쪽 (right)를 의미한다. 

 

 

시간복잡도는 O(n^2)이다, 다른 분할 정복 알고리즘들과 같이. 공간복잡도도 O(logn)이다. 

 

 

아래 레포지토리에 퀵 정렬 알고리즘을 응용하여 프로그램을 완성하였다. 응용할 때 참고하면 좋을 거 같다. 

 

yoonBot/Algorithm-Library