이 글은 나동빈님의 "이것이 코딩테스트다 with 파이썬"책과 유튜브 강의를
교재로 삼아 공부한 후 나의 이해한 내용을 정리한 글입니다

퀵 정렬

핵심 아이디어

특정 값(피벗 값)을 기준으로 큰 숫자, 작은 숫자를 찾아 정렬한다.

정렬 진행 방식

1 ) 피벗 값을 설정 한다.
2 ) 왼쪽에서 오른쪽, 오른쪽에서 왼쪽을 탐색하는 두 가지 탐색방법으로 나눈다.
3 ) 피벗 값 기준 큰 값을 왼 -> 오에서 찾고, 작은 값을 오 -> 왼에서 찾는다.
4 ) 두 값을 찾았다면 두 값의 위치를 바꿔준다.
5 ) 만약 값을 찾았는데 큰 값의 인덱스가 작은 값의 인덱스보다 크다면 작은 값과 피벗 값의 위치를 바꿔준다.
6 ) 5)의 과정을 시행했다면, 바꾼 피벗값의 위치 기준 왼쪽 그룹, 오른쪽 그룹으로 나누어 1) ~ 5)의 과정을 시행한다.
7 ) 1) ~ 6)의 과정을 반복하여 시행한다.
8 ) 정렬 완료

• 정렬 진행 방식은 매우 간략하게 설명하여 나눈 것이므로 밑의 코드 설명 부분에서 자세히 다루도록 한다.

기본 코드 구조

def f_quick(arr, start, end):
    if start >= end:
        return
        
    pivot = start
    i = start + 1
    j = end

    while i <= j:
        while i <= end and arr[i] <= arr[pivot]:
            i += 1
        while j > start and arr[j] >= arr[pivot]:
            j -= 1
            
        if i > j:
            temp = arr[j]
            arr[j] = arr[pivot]
            arr[pivot] = temp
        else:
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
    f_quick(arr, start, j - 1)
    f_quick(arr, j + 1, end)

    return arr

코드 설명

우선 앞서 정리한 선택, 버블, 삽입 정렬과 달리 코드 자체도 매우 길고 뭔가 이런게 진짜 알고리즘이다 라고 처음 느꼈던 정렬 알고리즘이었다.
설명 부분에서 최대한 디테일 하게 설명 하도록 하겠다.

퀵 정렬에서 가장 중요한 개념은 바로 피벗 값 (기준 값)이다.
이 피벗 값을 기준으로 왼 -> 오 탐색 시에는 큰 값, 오 -> 왼 탐색 시에는 작은 값을 찾는다.

바로 코드를 보자

코드 1

def f_quick(arr, start, end):
    if start >= end:
        return
        
    pivot = start
    i = start + 1
    j = end

가장 먼저 써있는 조건문은 가장 마지막에 설명 하도록 하겠다.
f_quick이라는 함수는 총 3가지의 매개변수를 받는다.
정렬하려는 배열, 시작 점 (start), 끝 점(end)

여기서 start, end는 배열의 첫번째 인덱스 start, 오 -> 왼 탐색의 시작점 인덱스 end를 뜻한다.

가장 먼저 피벗 값을 start로 시작한다.
( 배열의 첫번째 값으로 설정하는것이 편하다 )

자, 피벗 값을 기준으로 배열의 값들의 대소를 찾는것이 퀵 정렬이다.

따라서 배열을 탐색할때는 피벗값은 제외하고 탐색을 시행한다.

즉 왼 -> 오의 시작점은 start + 1 ( === i ) 이 된다. (피벗값을 범위에서 제외)
오 -> 왼의 시작점은 end ( === j)로 정해 두었지만 종료 지점을 신경써야 한다.

코드 2

while i <= j:
   while i <= end and arr[i] <= arr[pivot]:
       i += 1
   while j > start and arr[j] >= arr[pivot]:
       j -= 1

자 코드 1에서 피벗 값, i ( 왼->오 시작점 ), j ( 오->왼 시작점 )를 설정하였으니 이제 코드 2에서 반복문을 통해 탐색을 시작한다.

정렬 진행 방식의 5)를 보면 i 값이 j 값보다 커지면 찾는 과정을 중지 한 후, 피벗 값과 j값을 바꾼다. 바꾼 피벗 값 위치 기준 왼/오에 생긴 두 그룹에서 다시 피벗값을 정하여 탐색을 실시해야 하기 때문에 상위 while문의 탈출조건을 i <= j로 설정하였다.

i 값은 배열의 마지막까지 시행하므로 end까지 탐색하고, 피벗 값보다 큰 값을 찾으면 그 즉시 반복문을 탈출해야 하므로 arr [ i ] <= arr[ pivot ]의 탈출 조건을 가진다.

j값은 배열의 start + 1까지 탐색하고( 피벗 값은 탐색하지 않으므로 ), 피벗 값보다 작은 값을 찾으면 그 즉시 반복문을 탈출해야 하므로 arr[ i ] >= arr[ pivot ]의 탈출조건을 가진다.

즉, 위 두개의 while문을 탈출 했다는 것은 작은 값, 큰 값을 모두 찾았다는 뜻이다.

코드 3

if i > j:
  temp = arr[j]
  arr[j] = arr[pivot]
  arr[pivot] = temp
else:
  temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp

코드 3에서는 찾은 작은 값, 큰 값의 인덱스를 비교하여 연산을 다르게 실시한다.
정렬 진행 과정 4 )에 해당 하는 부분이 else구문이고, 5 )에 해당하는 부분이 if 구문이다.

temp변수를 선언/할당하여 i,j의 인덱스 대소에 따라 위치를 바꿔준다

만약 if구문으로 연산이 시행되었다면, i가 j값보다 커졌다는 걸 의미한다.
즉, 상위 while문의 탈출조건을 충족하므로 더이상 while문을 시행하지 않고 구문을 탈출하여 하위 코드를 실행한다.

반대로, else구문이 시행되었다면 상위 while문의 탈출 조건을 충족하지 않았으므로 다시 while을 실행 하게 된다.

코드 4

f_quick(arr, start, j - 1)
f_quick(arr, j + 1, end)

만약 if문의 코드가 실행되어 상위 while문을 탈출 했다면 피벗 값과 j의 값이 바뀌었다는 것을 의미한다.

즉, 피벗값 기준 왼쪽은 피벗값보다 작은 요소, 오른쪽은 큰 요소들이 위치하고 있다는 의미가 된다.

이렇게 생성된 두 개의 그룹에서 다시 피벗값을 설정하여 코드 1 ~ 3의 과정을 반복하여 시행하여 정렬해야 한다.
그래서 코드 4에서 현재 생성한 함수를 호출하여 새로운 매개변수 값을 넣어 실행 시킨다.

여기서 주의해야 할 점은 생성한 함수의 매개변수 start, end이다.

피벗 기준 왼쪽 그룹의 경우, start부분은 같지만, end부분은 현재 피벗 값위치 - 1까지 시행해야 한다.
피벗 기준 오른쪽 그룹의 경우, end부분은 같지만, start부분은 현재 피벗 값 위치 + 1 부터 시작해야 한다.

자 여기서 맨 처음 스킵했던 코드를 다시 한번 살펴보자

extra

def f_quick(arr, start, end):
    if start >= end:
        return

자 만약 위의 재귀함수를 계속하여 실행 하다 보니 원소가 1개밖에 남지 않았다고 가정하자
그렇다면 start값이 end값보다 커지는 경우가 발생한다.

• 만약 원소가 1개라면 피벗 값 +- 1이 start, end에 할당 된다.
  따라서 start가 end값보다 커지거나 같게 된다.

• 또한 정렬이 모두 완료 된 경우도 같다

• 이 부분은 직접 코드를 작성하여 print를 직접 찍어서 확인 해보면 훨씬 더 빠르고 쉽게 이해할 수 있다.

이 경우 정렬을 시행하지 않아도 되므로 바로 return 한다.

최종 코드 // 입 출력 결과

arr = [2, 10, 5, 9, 8, 7, 4, 6, 3, 11]

def f_quick(arr, start, end):
    if start >= end:
        return
        
    pivot = start
    i = start + 1
    j = end

    while i <= j:
        while i <= end and arr[i] <= arr[pivot]:
            i += 1
        while j > start and arr[j] >= arr[pivot]:
            j -= 1
            
        if i > j:
            temp = arr[j]
            arr[j] = arr[pivot]
            arr[pivot] = temp
        else:
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
    f_quick(arr, start, j - 1)
    f_quick(arr, j + 1, end)

    return arr
    
 print(f_quick(arr, 0, len(arr) - 1))
 
 ==> [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

처음 퀵 정렬을 공부 할 때는 지금껏 이런식으로 생각해 본적이 없기에 이해하는데 꽤나 시간이 걸렸던 것 같다.
그래서 손으로 직접 배열의 실행과정을 써가며 작성한 코드와 하나하나 비교하며 공부를 했었다.
사실 피벗이라는 개념과, 재귀 함수라는 개념을 잘 이해하고 사용할 줄 알아야 이해가 쉽고 빨랐던 것 같다.
이 알고리즘을 통하여 재귀 함수도 다시 한번 공부하게 되어 아주 좋았던 것 같다.