들어가면서

가장 빠른 정렬 알고리즘인 퀵 정렬에 대해서 알아보자.

퀵 정렬

퀵 정렬은 pivot을 사용해, pivot을 기준으로 분할하며 정렬해나간다.
각 단계의 목표는 pivot 앞에는 모두 pivot 보다 작도록,pivot 뒤에는 모두 pivot 보다 크도록 만들어준다.
분류가 끝난 후에는 pivot을 기준으로 앞,뒤로 분할해 다시 진행한다.

>>즉, 분류를 해나가는 방법이 핵심이다.

분류 방법

이건 딱 잘 설명할 수 있는 알고리즘이 사실 떠오르지 않는다.

1. 왼쪽에서 오른쪽 방향으로 pivot보다 큰이 있는지 검사한다.
   ➔ 있을 경우, left = pivot보다 큰 값
   ➔ 없을 경우, left = 마지막 직전 요소

2. 오른쪽에서 왼쪽 방향으로 pivot보다 작은 값이 있는지 검사한다.
   ➔ 있을 경우, right = pivot보다 작은 값
   ➔ 없을 경우, left = pivot 직후 요소

3. left와 right가 같아지거나 left가 더 커진 경우
   ➔ 교차되거나 만난 지점까지, pivot을 거스르는 경우는 없다.
   따라서 pivot보다 작은 파트 중 마지막 인덱스와 piovt의 값을 변경하면된다.
   pivot에는 값을 변경한 right 인덱스를 넣으면 된다.

4. 3을 통과 한 경우, right값이 left값보다 작은 경우 서로 교환해준다.

⭐ 그 인덱스는 left가 아닌 right 값이다.
왜 그럴까?? 위에서 각 인덱스가 뜻하는 값을 생각해보면 간단하다.

위의 과정을 모두 거치면, pivot을 기준으로 앞에는 작은 값, 뒤에는 큰 값이 정렬된다.
앞의 리스트와 뒤의 리스트로 분할해서 1번~4번의 과정을 반복하면된다.

a_list = [4,3,6,2]

=====퀵정렬 시작====
pivot = 0 //중간으로도 사용할 수 있는데 여기서는 맨 처음을 pivot으로 고정하겠다.

left = 1 
right = len(a_list) - 1

1번째 반복 :
	left값이 pivot 보다 크거나 같은 값이 있는지 검사
    -> left = 2(6)
    right값이 pivot 보다 작거나 같은 값이 있는지 검사 
    -> right = 3(2)
	
    left >= right ? -> 노, 통과
    
    left값 > right 값? 
    -> 네: 서로 교환한다
    [4,3,2,6]

2번째 반복: left= 2(3) right = 3(6)
	left값이 pivot 보다 크거나 같은 값이 있는지 검사
    -> left = 3(6)
    right값이 pivot 보다 작거나 같은 값이 있는지 검사 
    -> right = 2(2)
	
    left >= right ? 
    -> 네!
    pivot과 right 교환, pivot <= 2
    [2,3,(4),6]
    break

재귀문으로 [2,3]과 [6]으로 나눠서 실행....

퀵정렬의 시간 복잡도

가장 빠른 알고리즘으로 O(n log n)을 가진다.
그러나 최악의 경우, 2개로 분할되지 않는 경우에 O(n^2)의 시간 복잡도를 가진다.

파이썬 실제 구현 코드

# 24-1 퀵 정렬

def quick_sort(a_list):
    if len(a_list) <= 1:
        return a_list

    pivot = 0
    left = 1
    right = len(a_list) - 1

    while True:
        while a_list[left] <= a_list[pivot] and left < len(a_list) - 1:
            left += 1

        while a_list[right] >= a_list[pivot] and right > 0:
            right -= 1

        if left >= right:
            a_list[pivot], a_list[right] = a_list[right], a_list[pivot]
            pivot = right
            break

        if a_list[right] < a_list[left]:
            a_list[left], a_list[right] = a_list[right], a_list[left]


    left_sorted = quick_sort(a_list[:pivot])
    right_sorted = quick_sort(a_list[pivot + 1:])
    return left_sorted + [a_list[pivot]] + right_sorted

a_lsit = [7,3,1,-99,-99,233]
a_lsit = quick_sort(a_lsit)

print(a_lsit)

큰수가 앞에오는 퀵 정렬

def quick_sort(a_list):
    if len(a_list) <= 1:
        return a_list

    left = 1
    right = len(a_list) - 1
    pivot = 0
    while True:
        while a_list[pivot] <= a_list[left] and left < len(a_list) - 1:
            left += 1

        while a_list[pivot] >= a_list[right] and right > 0:
            right -= 1

        if left >= right:
            a_list[pivot],a_list[right] = a_list[right],a_list[pivot]
            pivot = right
            break

        if a_list[right] > a_list[left]:
            a_list[left], a_list[right] = a_list[right], a_list[left]

    left_sorted = quick_sort(a_list[:pivot])
    right_sorted = quick_sort(a_list[pivot+1:])

    return left_sorted + [a_list[pivot]] + right_sorted

a_list = quick_sort(a_list)
print(a_list)

📌 기억하자

퀵정렬의 left와 right을 찾는 두 개의 while문의 조건은 등호를 포함하고 있어야한다!!