[알고리즘, Python] 정렬 2 - 퀵 정렬(Quick Sort)

https://jwdevv.tistory.com/3

[알고리즘, Python] 정렬(sorting) - 병합 정렬(Merge Sort)

이전 글과 동일한 '배열을 정렬'하는 문제를 퀵정렬로 구현해보자.

---

퀵정렬은 랜덤한 요소를 피봇(pivot)으로 정해서 피봇값보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 정렬하는 방법이다.

 

평균 시간복잡도는 O(n log(n)) 이지만 피봇값을 어떻게 정하냐에 따라 최악의 경우에는 시간복잡도가 O(n^2)가 될 수도 있다.

 

따라서 피봇은 최대한 가운데 값으로 정하는 게 좋다.

 

 

퀵정렬 Python 코드

class Solution:
    def sortArray(self, nums):
        self.quicksort(nums, 0, len(nums) - 1)
        return nums

    def quicksort(self, nums, left, right):
        index = self.partition(nums, left, right)
        if left < index - 1:
            self.quicksort(nums, left, index - 1)
        if index < right:
            self.quicksort(nums, index, right)

    def partition(self, nums, left, right):
        pivot = nums[int((left + right) / 2)] # 배열의 가운데 값을 피봇으로

        while left <= right:
            while nums[left] < pivot: # 왼쪽 배열에서 피봇보다 큰 값이 나올 때까지 탐색한다
                left += 1
            while nums[right] > pivot: # 오른쪽 배열에서 피봇보다 작은 값이 나올 때까지 탐색한다
                right -= 1

            if left <= right: # 왼쪽 배열에서 탐색을 멈춘 인덱스가 오른쪽 배열에서 탐색을 멈춘 인덱스보다 작을 때 swap한다.
                (nums[left], nums[right]) = (nums[right], nums[left])
                # swap 후에는 left는 오른쪽으로, right는 왼쪽으로 이동한다.
                left += 1
                right -= 1

        return left

 

실행 결과

 

병합 정렬을 사용했을 때보다 런타임이나 메모리 사용 측면에서 큰 변화는 없었다.

 

퀵정렬의 공간복잡도는 O(log(n))이다.

 

---

+ Python에서 성능 좋은 swap 구현하기

 

Python에서 swap을 구현할 때

 

이렇게 구현하는 것보다

def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp

이 방법으로 구현하는게 런타임, 메모리 측면에서 더 낫다.

(arr[i], arr[j]) = (arr[j], arr[i])

---

출처

- Cracking the Coding Interview - Chapter 10. Sorting and Searching