퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
• 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.

---

1. 퀵 정렬 동작 예시

[Step 0]

출처 : 이코테2021

• 현재 Pivot 값은 5이다.
• 왼쪽에서는 Pivot값 보다 큰 데이터를 선택하고 오른쪽에서는 Pivot값 보다 작은 데이터를 선택한다.
• 왼쪽은 5보다 큰 7을, 오른쪽에서는 5보다 작은 4를 선택한다.
• 이제 두 데이터의 위치를 서로 변경한다.

 

[Step 1]

• 현재 Pivot 값은 5이다.
• 왼쪽에서는 9는 Pivot보다 크므로 선택, 오른쪽에서는 2가 5보다 작으므로 2를 선택
• 9와 2의 데이터 위치를 서로 변경한다.

 

[Step 2]

• 9와 2의 위치가 바뀌었다.
• 왼쪽에서는 Pivot보다 큰 값을 다시 찾는다. 6을 발견하는데 이때 1은 작으므로 건너뛴다.
• 오른쪽에서는 5보다 작은 값을 찾는다. 1을 발견하는데 이때 6은 크므로 건너뛴다.
• 이때 위치가 엇갈리는 경우 Pivot과 작은 데이터의 위치를 서로 변경한다.
• 즉, Pivot(5)와 작은 데이터(1)의 위치를 변경

 

[분할 완료]

• Pivot이 거의 중앙으로 옮겨지고 왼쪽은 Pivot보다 작은 값, 오른쪽은 Pivot보다 큰 값이 들어간다.
• 이렇게 Pivot을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide) = (Partition)라고 한다.

 

[왼쪽 데이터 묶음 정렬]

• 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.
• 여기서 Pivot은 1이다.
• 왼쪽은 1보다 큰 수를 선택하고 오른쪽은 1보다 작은 수를 선택한다.
• 이처럼 계속 반복적으로 정렬을 수행한다.

 

[오른쪽 데이터 묶음 정렬]

• 오른쪽도 마찬가지로 Pivot이 6이되어 왼쪽은 큰 수, 오른쪽은 6보다 작은 수를 선택하여 바꾼다.

---

2. 퀵 정렬이 빠른 이유

• 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있다.

---

3. 퀵 정렬의 시간 복잡도

평균

최악 경우

---

4. 퀵 정렬 소스코드

def quick_sort(array, start, end):
    if start >= end: #원소가 1개인 경우 종료
        return
    pivot = start #피벗은 첫 번째 인덱스
    left = start + 1
    right = end
    while(left <= right):
        #피벗보다 큰 데이터를 찾을 때까지 반복
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        #피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right):#엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: #엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right -1)
    quick_sort(array, right + 1, end)

• 첫 번째 원소를 Pivot으로 설정
• 첫 번째 반복문 (left <= right)일 경우가 엇갈릴 경우다.
• 왼쪽은 1개씩 올라가면서, 오른쪽은 1개씩 내려가면서 확인한다.
• 엇갈릴 경우 if, else문을 통해 위치를 바꿔준다.
• 가운데에 Pivot값이 위치가 되면 다시 재귀함수를 이용해서 왼쪽, 오른쪽 덩어리를 진행한다.

array = [5,7,9,0,3,1,6,2,4,8]
quick_sort(array, 0, len(array) - 1)

print(array)

 

파이썬을 이용해서 더욱 간단하게 만들 수 있다.

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
    #리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array
    pivot = array[0] #피벗은 첫 번째 원소
    tail = array[1:]#피벗을 제외한 리스트
    
    left_side = [x for x in tail if x <= pivot] #반할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] #반할된 오른쪽 부분
    
    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고, 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))

---

5. 새롭게 알게 된 것

[x for x in array if x <= pivot]

array리스트에서 각각 원소를 x로 꺼내고 그 x가 pivot다 작을 때의 경우의 x만 꺼낸다.