[알고리즘] 정렬 | [3] 퀵 정렬 (Quick Sort) - Python

[알고리즘] 정렬 | [1] 정렬, 선택 정렬 (Selection Sort) - Python

[알고리즘] 정렬 | [1] 정렬, 선택 정렬 (Selection Sort) - Python

[알고리즘] 정렬 | [2] 삽입 정렬 (Insertion Sort) - Python

[알고리즘] 정렬 | [2] 삽입 정렬 (Insertion Sort) - Python

 

 

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

 

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

 

^ 다른 정렬들이 궁금하다면 ^

---

1. 퀵 정렬(Quick Sort)이란?

- 알고리즘 중 가장 많이 사용되는 정렬 중 하나

- 퀵 정렬(Quick sort)는 영국의 컴퓨터 과학자  찰스 앤터니 리처드 호어가 1959년에 개발한 정렬 알고리즘이다.

- 피벗을 기준으로하여 좌우를 나눠서 파티션 교환 정렬(Partition Exchange Sort)라고도 불린다.

- 피벗(Pivot)은 기을 의미하는 개념으로

  피벗보다 작으면 왼쪽 // 크면 오른쪽과 같은 방식으로 파티셔닝을 하면서 쪼개 나간다.

- 퀵 정렬은 여러가지 변형(variation)이 존재하지만, 이 글에서는 대표 퀵 정렬 알고리즘만 알아볼 것이다.

 

1) 퀵 정렬의 원리

- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.

- 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.

- 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.

 

2) 퀵 정렬 동작 예시 1

출처: [이것이 코딩테스트다 with python] 23강 퀵 정렬

https://www.youtube.com/watch?v=EuJSDghD4z8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=23

[Step 0] 

현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

 

 

[Step 1]

현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '2'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

 

 

[Step 2]

현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '6'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '1'이 선택된다. 단, 이처럼 위치가 엇갈리는 경우 '피벗'과 '작은 데이터'의 위치를 서로 변경한다.

 

 

[분할 완료]

이제 '5'의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는 특징이 있다. 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)이라고 한다.

 

 

[왼쪽 데이터 묶음 정렬]

왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.

 

 

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

오른쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.

 

...

 

이러한 과정을 반복하면 전체 데이터에 대해서 정렬이 수행된다.

 

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

# 5가 start 지점이고, 8이 end 지점

def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start #첫 번째 요소는 피벗의 초기값
    left = start+1
    right = end
    
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left+=1
        # 왼쪽 파티션에서 피벗보다 큰 데이터 찾기 전까지 +1 한다.
            
            
        #피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right-=1
        # 오른쪽 파티션에서 피벗보다 작은 데이터를 찾기 전까지 -1 한다.
            
            
        if left>right: # 엇갈리면 작은 right -=1 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        # left > right 이면, array[right]와 array[pivot]의 위치를 바꾼다.
        
            
        else: # 엇갈리지 않으면 작은 데이터와 큰 데이터를 교체 
            array[left], array[right] = array[right], array[left]
        # left < right 이면, array[left]와 array[right]의 위치를 교체한다.
            
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1) # 왼쪽으로
    quick_sort(array, right+1, end) # 오른쪽으로
    
quick_sort(array, 0, len(array)-1)
print(array)

 

 

2) 퀵 정렬 동작 예시 2 - 파이썬의 장점 살리기

- 장점: 코드가 깔끔하고 직관적이다.

- 단점: 위에서 본 전통적인 퀵 정렬보다는 조금 더 비효율적이다.

 

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

def quick_sort(array): # 매개 변수가 array 1개뿐
    
    #리스트가 하나 이하의 원소만 담고 있다면 종료 >> 종료되는 조건
    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))
   
#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도가 궁금하다면?

 

 

 

 

글마침