TIL

190424_TIL(quick sort)

컴퓨터공학기초

quick sort(퀵 정렬)

quick sort(퀵 정렬) 이란?

  • 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다.
  • 최악의 경우의 시간 복잡도는 선택 정렬이나 삽입 정렬처럼 O(n^2)로 좋지 않다. 하지만 퀵 정렬의 평균 수행 시간복잡도는 O(n log n)이다. 그런데 일반적인 경우 퀵 정렬은 다른 O(n log n) 정렬보다 빠른데 그 이유 중 하나는 빅오 표기법 속에 숨겨진 퀵 정렬의 상수항이 작기 때문이다.
  • 분할 정복 기법(divide & conquer) 기법을 통해 리스트를 정렬한다.
    1. 리스트에서 하나의 요소를 고른다. 고른 원소를 pivot(피벗)이라고 한다.
    2. 리스트의 안에 있는 요소들을 재배열하여 pivot 보다 작은 요소는 pivot 기준 왼쪽으로, pivot 보다 큰 요소들은 pivot기준 오른쪽으로 보낸다. 이 과정은 요소들을 오름차순으로 정렬하는 것이 목적이 아니라 pivot을 기준으로 왼쪽과 오른쪽으로 분할 하는 것이 목적이다.
    3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복하여 정렬한다.
    4. 재귀의 base case는 리스트의 크기가 0 또는 1이 될 때이다.




quick sort(퀵 정렬) 코드 with python

  • 이해하기 위해서 많은 주석을 달면서 진행하였다. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def get_middle_idx(li, start, mid, end):
    """
    리스트 인덱스를 기준으로 처음 값과 중간 값, 마지막 값 중에서
    크기가 가운데 값인 인덱스를 반환한다.
    """
    idx_li=[start, mid, end]
    
    # to do
    if li[idx_li[0]] > li[idx_li[1]]:
        idx_li[0], idx_li[1]=idx_li[1], idx_li[0]
    if li[idx_li[1]] > li[idx_li[2]]:
        idx_li[1], idx_li[2]=idx_li[2], idx_li[1]
    if li[idx_li[0]] > li[idx_li[1]]:
        idx_li[0], idx_li[1]=idx_li[1], idx_li[0]
        
    return idx_li[1]


def quick_sort(li, start, end):
    # base case : 재귀 함수가 끝나는 조건을 정의
    # to do
    if start >= end:
        return
    
    left=start
    right=end
    
    # random pivot
    # pivot 값의 크기를 리스트의 중간 크기 값과 가깝거나 같게 만들어서 시간 복잡도가 O(n log 		n)인 average case로 만들기 위한 코드
    # 리스트의 인덱스 기준으로 첫번째 , 중간, 마지막 값을 가져와서 그 셋 중 값의 크기가 가운데인 	  값을 리스트의 인덱스 기준으로 중간인 값과 교환한다.
    mid=(left+right)//2
    mid_idx=get_middle_idx(li, start, mid, end)
    li[mid_idx], li[mid]=li[mid], li[mid_idx]
    
    pivot=li[(left+right)//2]
    
    # left와 right가 교차하기 "전"까지
    while left <= right:
        # li[left] > pivot 일 때,  while문을 빠져나온다. --> 값을 교환해야 할 때
        # li[left] < pivot 이면 값을 교환하지 않고 left를 +1로 위치 이동
        # left++
        while li[left] < pivot:
                left+=1
            
        # li[right]가 pivot보다 작을 때 while문을 빠져나온다. --> 값을 교환해야 할 때
        # li[right]가 피벗보다 크면 값을 교환하지 않고 right를 -1로 위치 이동
        # right--
        while pivot < li[right]:
                right-=1
        # 교차하기 위해서 '=' 을 넣어줘야 한다.  
        if left <= right:
            # 값을 교환
            li[left], li[right]=li[right], li[left]
            # left, right index 이동
            left+=1
            right-=1
    # 재귀함수 호출
    # 재귀함수를 호출하면 맨위 def로 정의한 메인함수의 매개변수 값을 변화시키고 스택을 쌓는다.
    # pivot 보다 작은 수 들을 정렬
    # end 값이 right가 된다.
    quick_sort(li, start, right)
    # pivot 보다 큰 수 들을 정렬
    # start 값이 left가 된다.
    quick_sort(li, left, end)

test 코드

1
2
3
4
5
6
7
8
9
10
import random

while True:
        num_data=int(input('데이터 개수(종료:0):'))
        if not num_data:
            break
        data=[random.randint(1, 100) for _ in range(num_data)]
        print(data)
        quick_sort(data, 0, len(data)-1)
        print(data)




python tutor를 이용하여 퀵정렬 이해하기

  • pythontutor 의 기능을 이용하여 알고리즘의 실행순서를 파악해보았다.
  • 위 예제 코드의 테스트 코드를 변경하여 임의의 값이 정해진 리스트를 사용하였다.
  • 재귀함수 호출 전 분할상태

  • 분할된 두 작은 리스트 중 pivot 보다 작은 수의 리스트를 재귀적으로 반복하여 정렬

  • 분할된 두 작은 리스트 중 pivot 보다 큰 수의 리스트를 재귀적으로 반복하여 정렬

참고자료

Share