Quick Sort

Quick Sort

Quick Sort

  • Divide and Conquer Algorithm

  • Use Recursion

Initialize

  1. 정렬해야할 list, 시작점 start와 끝점 end를 넘겨 받는다. left = start, right = end로 정한다.

  2. 양방향의 left와 right를 pivot 방향으로 움직이며 pivot 값과 left, right index의 element 값을 비교한다.

  3. left의 element 값이 pivot 보다 크고, right의 element 값이 pivot보다 작을 때 둘을 교환하고 각 index를 하나씩 이동한다.(left면 +1, right면 -1)

  4. left와 right가 교차되기 전까지 반복하면서 sorting한다.

  5. 한 번 교차되면 while문을 빠져나오는데, 이 때 pivot을 기준으로 왼쪽은 pivot보다 작은 값들로, 오른쪽은 pivot보다 큰 값들로만 이루어져있다.

  6. Recursion으로 pivot을 포함하지 않고 왼쪽과 오른쪽을 각각 다시 돌려준다. 이 때 base case는 start가 end와 같아지거나 교차하면 return하는 것이다.

  • 코드를 보는 게 더 이해가 쉬울 것 같다. 그림으로 그려보며 진행하는 게 가장 도움이 된다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def quickSort(li, start, end):
    if start >= end:
    return
    left = start
    right = end
    pivot = li[(left+right)//2]

    while left <= right:
    while li[left] < pivot:
    left += 1
    while li[right] > pivot:
    right -= 1
    if left <= right:
    li[left], li[right] = li[right], li[left]
    left += 1
    right -= 1

    quickSort(li, start, right-1)
    quickSort(li, left, end)
    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)
    quickSort(data, 0, len(data)-1)
    print(data)
  • [Quick sort에 관련된 TED edu 영상] What’s the fastest way to alphabetize your bookshelf?

    What's the fastest way to alphabetize your bookshelf

  • 문제는 pivot을 어떻게 결정할 것이냐이다. Pivot이 정렬해야할 list의 모든 값들의 평균치일 때는 n/2번을 비교하는 것으로 가장 좋지만, 예를 들어 최솟값이나 최댓값을 기준으로 pivot이 선택될 경우 n번을 계산해야한다.

  • pivot을 정렬된 list의 가운데 값으로 결정하는 것이 Best case지만, 정렬을 하기 위해서 pivot을 사용하는 것이므로 실현될 수 없는 이야기이다.

  • Quick Sort의 Time Complexity는 O(nlogn)으로, average case일 때를 기준으로 한다. Pivot을 random pivot으로 둘 경우 확률적으로 avarage case를 만족한다.

  • li의 start와 end와 mid를 정렬한 결과의 중간 값을 return한다. Random Pivot을 이용하기 위해 코드를 수정했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def getMiddleIndex(li, start, mid, end):
"""
list의 맨 처음 값, 끝 값, 중간 값 정렬시 가운데 값의 index 반환
"""
indices = [start, mid, end]

if li[indices[0]] > li[indices[1]]:
indices[0], indices[1] = indices[1], indices[0]
if li[indices[1] > li[indices[2]]]:
indices[1], indices[2] = indices[2], indices[1]
if li[indices[0]] > li[indices[1]]:
indices[0], indices[1] = indices[1], indices[0]

return indices[1]

전체 반영한 결과

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

def getMiddleIndex(li, start, mid, end):
"""
list의 맨 처음 값, 끝 값, 중간 값 정렬시 가운데 값의 index 반환
"""
indices = [start, mid, end]

if li[indices[0]] > li[indices[1]]:
indices[0], indices[1] = indices[1], indices[0]
if li[indices[1] > li[indices[2]]]:
indices[1], indices[2] = indices[2], indices[1]
if li[indices[0]] > li[indices[1]]:
indices[0], indices[1] = indices[1], indices[0]

return indices[1]


def quickSort(li, start, end):
if start >= end:
return
left = start
right = end
mid = (left+right)//2

#추가된 코드
mid_index = getMiddleIndex(li, start, mid, end)
li[mid_index], li[mid] = li[mid], li[mid_index]

pivot = li[mid]

while left <= right:
while li[left] < pivot:
left += 1
while li[right] > pivot:
right -= 1
if left <= right:
li[left], li[right] = li[right], li[left]
left += 1
right -= 1

quickSort(li, start, right-1)
quickSort(li, left, end)
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×