퀵 정렬(quick sort)

📔 퀵 정렬(quick sort) 이란

• 분할정복을 활용하여 구현하기 때문에 시간복잡도는 O(nlogn) 퀵이란 이름에 맞게 빠르다.

• 분할정복: 문제를 작은 2개의 문제로 분리하고 각각 해결한 후, 다시 모아 원래의 문제를 해결하는 방법.
  보통 재귀함수 호출을 이용하여 구한다.

• 기준 값(pivot)을 기준으로 그 값보다 큰 값과 작은 값을 서로 교환한 뒤 기준 값을 기준으로 두개의 리스트로 나눈다. (기준 값의 왼쪽에는 작은 값, 오른쪽에는 큰 값)
• 대부분의 경우에는 퀵정렬이 가장 빠르다. (c언어의 정렬 알고리즘도 퀵정렬 기반)
• 비교 정렬 ( 다른 원소와의 비교 )

 

📔 퀵 정렬(quick sort) 예제

• 맨앞의 값 3을 pivot 값으로 설정했다 ( 보통 가장 앞의 값을 pivot으로 설정)
• pivot값의 바로 오른쪽부터 끝으로 pivot값보다 큰 값을 탐색 ( 8을 찾음 )
• 오른쪽 맽 끝에서부터 왼쪽으로 pivot값보다 작은 값을 탐색 ( 2 찾음 )
• 둘을 서로 교환해준다.

• 큰 값 (7), 작은 값 (2)
• 하지만 서로 엇갈렸다. ( 작은 값의 인덱스가 큰 값의 인덱스보다 작은 경우)
• 이 경우 pivot값과 작은 값을 바꿔준다.
• 그리고 pivot값은 이제 고정이며, pivot값을 기준으로 두개의 리스트로 나눌 수 있다. 재귀 호출을 통해 위의 과정을 반복한다. 재귀는 리스트의 크기가 1보다 작거나 같을 때까지 반복.
• 재귀 호출 한번에 최소한 하나의 원소는 위치가 정해지므로, 알고리즘이 반드시 끝나는 것을 보장할 수 있다.

• 왼쪽의 리스트부터 살펴보면 pivot (2), 작은값(1) 큰 값은 없다. ( 큰 값이 없는 경우 큰 값의 인덱스는 작은 값을 넘어갔을 것이다. - 엇갈림)
• pivot값과 작은값을 바꿔준다. pivot(2)는 고정

• pivot(1), 작은값(0), 큰값 없음
• pivot과 작은값을 바꿔준다. 둘 다 고정

• 이제 오른쪽을 보면 pivot(7), 큰 값(8), 작은 값(6) 이다. 큰 값과 작은 값 교환

• 다시 pivot(7), 작은 값(4), 큰 값(9) 하지만 엇갈림
• pivot과 4를 교환. pivot fix!

 

 

 

📔 퀵 정렬(quick sort) 구현

def quick_sort(numbers, start, end):
    if start >= end:  # 원소가 1개인 경우
        return

    pivot = start  # pivot 가장 왼쪽의 원소
    i = start + 1
    j = end
    while i <= j:  # 엇갈릴 때 까지 반복
        while i <= j:
            if numbers[i] >= numbers[pivot]:  # pivot 보다 큰 값을 만날 때
                break
            else:
                i += 1
        while j >= i:
            if numbers[j] <= numbers[pivot]:  # pivot 보다 작은 값을 만날 때
                break
            else:
                j -= 1

        if j < i:  # 엇갈리면 pivot 과 작은값을 교체
            numbers[pivot], numbers[j] = numbers[j], numbers[pivot]
        else:  # 엇갈리지 않았다면 큰값(i)와 작은값(j)를 교체
            numbers[i], numbers[j] = numbers[j], numbers[i]
        print(f'정렬 중: {numbers}')

    # 교체한 작은값(j)는 fix!! fix 된 값을 기준으로 양쪽으로 나눠서 분할정복
    quick_sort(numbers, start, j - 1)
    quick_sort(numbers, j + 1, end)


numbers = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
print(f'정렬 전: {numbers}')
print()

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

print()
print(f'정렬 후: {numbers}')

더 간편한 방법

def quick_sort(numbers):
    # 피봇을 정한다. 맨 뒤 값을 정했다.
    length = len(numbers)
    if length <= 1:
        return numbers
    else:
        pivot = numbers.pop()
        low_numbers = []
        high_numbers = []
        for i in range(length - 1):
            if numbers[i] > pivot:
                high_numbers.append(numbers[i])
            else:
                low_numbers.append(numbers[i])

        return quick_sort(low_numbers) + [pivot] + quick_sort(high_numbers)


nn = [9, 5, 1, 6, 8, 4, 2, 3, 7, 0]
print(f'정렬 전: {nn}')
print(f'정렬 후: {quick_sort(nn)}')

📔 퀵 정렬(quick sort) 특징

• 장점
  • 대부분의 경우 속도가 매우 빠르다. O(nlogn) 분할정복을 사용하여 매 단계에서 적어도 1개의 원소가 자리를 정하기 때문에 정렬할 개수가 줄어들기 때문.
• 단점
  
  • 불안정 정렬 - 동일한 값에 대해서 기존의 순서가 유지되지 않는다.
    만약(A1, A3, A2, B, C)일 경우 순서가 A의 순서가 바뀔 수 있다.
  • 최악의 경우 O(n^2)의 시간복잡도가 나온다.
    • 대부분 정렬된 상태라면 분할정복의 이점을 사용하지 못하기 때문 - 이럴 때는 삽입정렬을 사용해보자!!!
    • 또 pivot값을 잘못 설정할 경우(운이 나쁘면) - 크기가 적당한 pivot값을 찾아서 사용.

 

📔 퀵 정렬(quick sort) 참교자료