퀵 정렬

📌퀵 정렬

가장 많이 사용되는 정렬 알고리즘

기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작

 

피벗: 큰 수와 작은 수를 교환할 때 교환하기 위한 기준

퀵 정렬을 수행하기 전 피벗을 어떻게 설정할 것인지 미리 명시

 

피벗을 설정하고 리스트를 분할하는 가장 대표적인 방식: 호어 분할 방식

1. 리스트에서 첫 번째 데이터를 피벗으로 정한다.

2. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.

3. 큰 데이터와 작은 데이터의 위치를 서로 교환하는 것을 반복한다.

4. 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 경우, 작은 데이터와 피벗의 위치를 교환한다.

5. 분할 완료: 피벗을 기준으로 피벗 왼쪽에는 피벗보다 작은 데이터, 피벗 오른쪽에는 피벗보다 큰 데이터가 위치한다.

6. 피벗 왼쪽 리스트, 피벗 오른쪽 리스트를 똑같은 방식으로 각각 피벗을 설정하여 정렬한다.

 

재귀 함수 형태로 작성하면 구현 간결해짐

 

퀵 정렬이 끝나는 조건: 현재 리스트의 데이터 개수가 1개인 경우

 

📌퀵 정렬의 시간 복잡도

퀵 정렬: 평균적으로 O(NlogN)

 

선택 정렬: O(N²)

삽입 정렬: O(N²)

 

퀵 정렬은 평균적으로 시간 복잡도가 O(NlogN)이지만 최악의 경우 O(N²)

데이터가 무작위로 입력되는 경우 빠르게 동작

이미 데이터가 정렬되어 있는 경우에는 느리게 동작(반면, 삽입 정렬은 이미 데이터가 정렬되어 있는 경우 매우 빠르게 동작)

 

📌코드

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


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)


quick_sort(array, 0, len(array) - 1)
print(array)

 

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬