[Python] 퀵 정렬 (Quick Sort)

선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지기 때문에 데이터가 커지면 사용하기가 어려운 알고리즘이다. 그래서 더욱 빠른 정렬알고리즘이 사용될 필요가 있다.

 

퀵 정렬 알고리즘은 대표적인 '분할 정렬' 알고리즘으로 평균속도가 O(N * logN)이다.

퀵 정렬은 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 빠르게 정렬한다. 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

 

 

 

특정한 값을 기준으로 큰 숫자와 작은 숫자를 나눈다.

일반적으로 퀵정렬에서는 기준값이 있다. 이를 피벗(Pivot)이라 한다. 보통 가장 앞에 있는 값을 피벗값으로 사용한다.

 

3 7 8 1 5 9 6 10 2 4 -> 3 2 8 1 5 9 6 10 7 4

왼쪽에서 오른쪽으로 이동할 때는 피벗보다 큰 값을 선택 => 7

오른쪽에서 왼쪽으로 이동할 때는 피벗보다 작은 값을 선택 => 2

선택된 두 값의 위치를 교체한다.

 

3 2 8 1 5 9 6 10 7 4 -> 3 2 1 8 5 9 6 10 7 4

왼쪽에서 오른쪽 피벗보다 큰 값을 선택 => 8

오른쪽에서 왼쪽 피벗보다 작은 값을 선택 => 1

선택된 두 값의 위치를 교체한다.

 

3 2 1 8 5 9 6 10 7 4 -> 1 2 3 8 5 9 6 10 7 4

왼쪽에서 오른쪽 피벗보다 큰 값을 선택 => 8

오른쪽에서 왼쪽 피벗보다 작은 값을 선택 => 1

8과 1은 서로 엇갈린 상황(작은값의 인덱스가 큰값의 인덱스보다 더 작은 상황)

작은값과 피벗의 위치를 바꿔준다.

 

1 2 3 8 5 9 6 10 7 4

3은 정렬이 이루어진 상태 (3을 기준으로 왼쪽은 3보다 작은 수, 오른쪽은 3보다 큰 수)

이 상태에서 3을 기준으로 왼쪽에서 다시 정렬 오른쪽에서 다시 정렬한다.

 

1 2 3 8 5 9 6 10 7 4 -> 1 2 3 8 5 9 6 10 7 4

피벗값 1

왼쪽에서 오른쪽 피벗보다 큰 값 => 2

오른쪽에서 왼쪽 피벗보다 작은 값 => 없음 이 경우에는 자기 자신을 고름 => 1

엇갈린 상황 -> 피벗값과 작은 값의 위치를 바꿔준다.

 

1 2 3 8 5 9 6 10 7 4

1은 정렬이 이루어진 상태

피벗값 2

값이 없기 때문에 정렬할 것이 없음

 

1 2 3 8 5 9 6 10 7 4 -> 1 2 3 8 5 4 6 10 7 9

피벗값 8

왼쪽에서 오른쪽 피벗보다 큰 값 => 9

오른쪽에서 왼쪽 피벗보다 작은 값 => 4

선택된 두 값의 위치를 바꾼다.

 

1 2 3 8 5 4 6 10 7 9 -> 1 2 3 8 5 4 6 7 10 9

왼쪽에서 오른쪽 피벗보다 큰 값 => 10

오른쪽에서 왼쪽 피벗보다 작은 값 => 7

선택된 두 값의 위치를 바꾼다.

 

1 2 3 8 5 4 6 7 10 9 -> 1 2 3 7 5 4 6 8 10 9

왼쪽에서 오른쪽 피벗보다 큰 값 => 10

오른쪽에서 왼쪽 피벗보다 작은 값 => 7

엇갈린 상황 -> 피벗값과 작은 값의 위치를 바꿔준다.

 

1 2 3 7 5 4 6 8 10 9 -> 1 2 3 6 5 4 7 8 10 9

피벗값 7

왼쪽에서 오른쪽 피벗보다 큰 값 => 없음 -> 피벗값으로 설정 7

오른쪽에서 왼쪽 피벗보다 작은 값 => 6

엇갈린 상황 -> 피벗값과 작은 값의 위치를 바꾼다.

 

1 2 3 6 5 4 7 8 10 9

이런식으로 반복을 한다.

그럼 결과적으로 다음과 같이 정렬이 된다.

1 2 3 4 5 6 7 8 9 10

 

 

퀵 정렬이 강력한 이유를 직관적으로 설명을 해보자면 기존 선택, 버블, 삽입 정렬 같은 경우 10개의 데이터를 정렬한다고 했을 때 100번의 연산이 필요하다.

1 2 3 4 5 6 7 8 9 10

N ^ 2 = 10 * 10 = 100

 

퀵 정렬은 분할로 정렬 연산을 하기 때문에 기존의 정렬 알고리즘보다 더 작은 연산이 필요하다. 이러한 원리로 퀵 정렬이 빠르게 연산을 할 수 있다.

1 2 3 4 5 / 6 7 8 9 10

5 * 5 + 5 * 5 = 50

 

 

 

파이썬 코드

# 퀵 정렬 (Quick Sort)
# 특정한 피벗값을 이용해서 피벗값보다 큰값과 작은값을 반복적으로 바꾸어주는 연산
# 결과적으로 피벗값보다 작은 값은 왼쪽, 큰값은 오른쪽으로 분할이 된다
# 실제로 소스코드상에서는 재귀함수를 사용하는 경우가 많다.

def quick_sort(data, start, end):

    # start는 정렬을 수행하는 부분집합의 첫번째 값 end는 마지막 값
    if start >= end: # 원소가 한개인 경우
        return
    
    # key는 피봇값으로 첫번째 원소값으로 잡아준다
    key = start     
    
    # 탐색하기위한 변수들
    i = start + 1   # 왼쪽 출발 지점
    j = end         # 오른쪽 출발 지점
    
    
    while i <= j: # 엇갈릴 때까지 반복    
        # 왼쪽에서 오른쪽으로 이동
        while i <= end and data[i] <= data[key]: # 키값보다 큰 값을 만날 때까지 오른쪽으로 이동시킨다.
            i = i + 1
        # 오른쪽에서 왼쪽으로 이동
        while data[j] >= data[key] and j > start: # 키값보다 작은 값을 만날 때까지 왼쪽으로 이동시킨다.
            j = j - 1
            
        # 교체하는 로직
        if i > j: # 엇갈린 상태면 키값과 작은 값을 교체
            temp = data[j]
            data[j] = data[key]
            data[key] = temp
        else: # 엇갈리지 않았다면 큰 값과 작은 값을 교체
            temp = data[i]
            data[i] = data[j]
            data[j] = temp
    
    # 정렬이 끝나면 각각 왼쪽과 오른쪽 정렬을 실행해준다.
    quick_sort(data, start, j - 1)
    quick_sort(data, j + 1, end)

    return data


test = [3, 7, 8, 1, 5, 9, 6, 10, 2, 4]
print("정렬된 데이터 : {}".format(quick_sort(test, 0, len(test)-1)))

 

 

 

 

퀵 정렬의 단점

퀵 정렬의 평균 시간 복잡도는 O(N * logN)이다. 하지만 피벗값을 무엇으로 설정하는지에 따라서 최악 시간 복잡도가 O(N^2) 가 나온다는 단점이 있다.

이미 정렬이 되어있는 경우를 생각해보자.

1 2 3 4 5 6 7 8 9 10 -> 1 2 3 4 5 6 7 8 9 10

왼쪽에서 오른쪽으로 갈 때 피벗값보다 큰 값 -> 2

오른쪽에서 왼쪽으로 갈 때 피벗값보다 작은 값 -> 없음 -> 1

오른쪽에서 왼쪽으로 갈 때 피벗값보다 작은 값을 찾지 못해서 1까지 오게 된다. 연산이 10번 발생하는데 정렬은 고작 1하나만 완료하게 된다. 다음 연산을 할 때에도 9번, 8번 ... 발생하고 분할 정렬의 이점을 사용하지 못해서 시간 복잡도가 O(N * N)이 된다.

이 경우에는 삽입 정렬이 더 빠르다.

 

 

정렬할 데이터의 특성에 따라서 적절한 정렬 알고리즘을 사용하는 것이 중요하다.

 

 

퀵 정렬 소스코드에서 단 두 부분만 바꾸어서 내림차순으로 바꾸어 보자.

        while i <= end and data[i] >= data[key]: 
            i = i + 1

        while data[j] <= data[key] and j > start: 
            j = j - 1