[그림으로 개념을 이해하는 알고리즘] Quick Sort (퀵 정렬)

퀵정렬

분할 정복

1. 가장 간단한 경우로 기본 단계를 찾는다.
2. 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 방법을 찾는다.

예 (덧셈 함수)

---

• [1,2,3,4]

 
xxxxxxxxxx
def sum(arr):
    total = 0 
    for x in arr:
        total += x
    return total
  
print(sum([1,2,3,4]))

• 1단계 : 기본 단계를 찾는다. 가장 간단한 경우는 배열의 원소 개수가 0개 또는 1개인 배열을 받으면 합계를 구하는 것.

• 2단계 : 재귀 함수 호출을 할 때마다 호출 대상이 되는 배열의 크기가 점점 감소시켜야 한다.

• 결론

  • 리스트를 받으면 크기를 구해 비어있으면 0을 반환 그렇지 않으면 총합은 리스트의 첫 번째 숫자와 나머지 리스트의 총합을 더한 값이 된다.

퀵 정렬 (Quick Sort)

• 선택 정렬보다 훨씬 빠르고 실제로도 많이 사용되는 정렬 알고리즘.

• C언어 표준 라이브러리 qsort() 가 이에 해당한다.

• 분할 정복 전략 중 하나.

• 정렬하는데 가장 간단한 배열은 무엇일까?

  • 원소가 0 또는 1개인 배열

 
xxxxxxxxxx
def quicksort(arr):
    if len(arr) < 2:
        return arr

• 원소가 2개인 배열

  • 첫 번째 원소가 두번째 원소보다 작은지 살핀 후 그렇지 않다면 두 원소를 교환

• 원소가 3개인 배열

  • 분할 정복 전략을 사용하고 있다는 것을 기억

  • 기본 단께가 될 때까지 나눠야 한다.

    • 우선 배열에서 원소 하나를 고른다. 그것을 기준 원소 () 라 한다.
    • [33,15,10] => Pivot(33)
    • 기준 원소보다 작은 원소와 큰 원소로 분류.
    • [15,10], [33], [] => 분할 ()
    • [기준 원소보다 작은 숫자들], [기준 원소], [기준 원소보다 큰 숫자들]
    • 두 개 하위 배열은 정렬되어 있지 않지만, 이것들이 정렬되어있다면 전체 배열을 정렬하는 일은 아주 쉽다. [10,15], [33], [] => [10,15,33] 으로 병합.
    • 분할 정복을 기억하기바라며 하위 배열 또한 퀵 정렬을 호출.

• 원소가 4개인 배열

 
xxxxxxxxxx
def quicksort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0] #재귀단계
        less = [i for i in arr[1:] if i <= pivolt]
        greater = [i for i in arr[1:] if i > pivolt]
        return quicksort(lee) + [pivolt] + quicksort(greater)
​
print(quicksort([10,5,2,3]))

빅오 표기법 복습

이진탐색	단순탐색	퀵정렬	선택정렬	외판원문제

병합 정렬과 퀵 정렬 비교

---

• 정렬 알고리즘 중 병합 정렬(Merge sort)가 존재하는데 해당 알고리즘은 의 속도를 가지는데 퀵 정렬은 최악의 경우 이 될 수도있다.
• 여기서 말하는 최악의 경우와 일반적인 경우는?
• 그렇다면 병렬 정렬은 항상 시간인가요? 그렇다면 병합 정렬을 왜 사용하지 않는 건가요? 라는 질문을 받을 수 있다.

 
xxxxxxxxxx
from time import sleep
def print_items(list):
    for item in list:
        sleep(1) # 매 수행마다 1초씩 Sleep
        print(item)

• 여기서 의 수행과 상관없이 빅오표기법에서는 순서대로 전체를 확인해야 하므로 시간이 걸린다.
• 즉, 표기법이 동일한 속도를 가지는 함수일지라도 실제적으로 수행되는 시간을 다를 수 있다.

최악의 경우와 일반적인 경우

---

• 퀵 정렬을 예를 든다면 퀵정렬의 을 첫번째 요소로만 선택하여 정렬을 하게 된다면 모든 수를 다 선택하여 의 경우가 될 것이다. 하지만 어떠한 요소를 선택하느냐에 따라 소요대는 시간이 많이 달라지므로 최악의 경우와 일반적인 경우를 나누어 설명한다.

문제

• sum 함수를 작성

 
xxxxxxxxxx
def sum(list):
    if len(list) < 2:
        return 0
    return list[0] + sum(list[1:])

• 원소의 수를 세는 재귀함수를 작성

 
xxxxxxxxxx
def count(list):
    if len(list) < 1:
        return 0
    return 1 + count(list[1:])

• 리스트에서 가장 큰 수를 찾으시오.

 
xxxxxxxxxx
def max(list):
    if len(list) <2:
        return list[0] if list[0] > list[1] else list[1]
    sub_max = max(list[1:])
    return list[0] if list[0] > sub_max else sub_max