퀵정렬

분할 정복

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

예 (덧셈 함수)

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

print(sum([1,2,3,4]))
  • 1단계 : 기본 단계를 찾는다. 가장 간단한 경우는 배열의 원소 개수가 0개 또는 1개인 배열을 받으면 합계를 구하는 것.
  • 2단계 : 재귀 함수 호출을 할 때마다 호출 대상이 되는 배열의 크기가 점점 감소시켜야 한다.
    • $sum([2,3,4]) = 12$
    • $2 + sum([3,4]) = 2 + 10 = 12$
  • 결론
    • 리스트를 받으면 크기를 구해 비어있으면 0을 반환 그렇지 않으면 총합은 리스트의 첫 번째 숫자와 나머지 리스트의 총합을 더한 값이 된다.

퀵 정렬 (Quick Sort)

  • 선택 정렬보다 훨씬 빠르고 실제로도 많이 사용되는 정렬 알고리즘.
  • C언어 표준 라이브러리 qsort() 가 이에 해당한다.
  • 분할 정복 전략 중 하나.
  • 정렬하는데 가장 간단한 배열은 무엇일까?
    • 원소가 0 또는 1개인 배열
def quicksort(arr):
  	if len(arr) < 2:
      	return arr
  • 원소가 2개인 배열
    • 첫 번째 원소가 두번째 원소보다 작은지 살핀 후 그렇지 않다면 두 원소를 교환
  • 원소가 3개인 배열 $ [33,15,10]$
    • 분할 정복 전략을 사용하고 있다는 것을 기억
    • 기본 단께가 될 때까지 나눠야 한다.
      • 우선 배열에서 원소 하나를 고른다. 그것을 기준 원소 ($pivot$) 라 한다.
      • [33,15,10] => Pivot(33)
      • 기준 원소보다 작은 원소와 큰 원소로 분류.
      • [15,10], [33], [] => 분할 ($partitioning$)
      • [기준 원소보다 작은 숫자들], [기준 원소], [기준 원소보다 큰 숫자들]
      • 두 개 하위 배열은 정렬되어 있지 않지만, 이것들이 정렬되어있다면 전체 배열을 정렬하는 일은 아주 쉽다. [10,15], [33], [] => [10,15,33] 으로 병합.
      • 분할 정복을 기억하기바라며 하위 배열 또한 퀵 정렬을 호출.
      • $quicksort([15,10]) + [33] + quicksort([]) => [10,15,33]$
  • 원소가 4개인 배열 $[33,10,15,7]$
    • $Pivot(33)$
    • $[10,15,7], [33], []$
    • $quicksort([10,15,7]),[33],quicksort([])$
    • $[7,10,15],[33],[] =>[7,10,15,33]$
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]))

빅오 표기법 복습

이진탐색 단순탐색 퀵정렬 선택정렬 외판원문제
$O(log_n)$ $O(n)$ $O(nlog_n)$ $O(n^2)$ $O(n!)$

병합 정렬과 퀵 정렬 비교

  • 정렬 알고리즘 중 병합 정렬(Merge sort)가 존재하는데 해당 알고리즘은 $O(nlog(n))$ 의 속도를 가지는데 퀵 정렬은 최악의 경우 $O(n^2)$ 이 될 수도있다.
  • 여기서 말하는 최악의 경우와 일반적인 경우는?
  • 그렇다면 병렬 정렬은 항상 $O(nlog(n))$ 시간인가요? 그렇다면 병합 정렬을 왜 사용하지 않는 건가요? 라는 질문을 받을 수 있다.
from time import sleep
def print_items(list):
  	for item in list:
      	sleep(1) # 매 수행마다 1초씩 Sleep
      	print(item)
  • 여기서 $sleep$의 수행과 상관없이 빅오표기법에서는 순서대로 전체를 확인해야 하므로 $O(n)$ 시간이 걸린다.
  • 즉, 표기법이 동일한 속도를 가지는 함수일지라도 실제적으로 수행되는 시간을 다를 수 있다.

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

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

문제

  • sum 함수를 작성
def sum(list):
  	if len(list) < 2:
      	return 0
    return list[0] + sum(list[1:])
  • 원소의 수를 세는 재귀함수를 작성
def count(list):
  	if len(list) < 1:
      	return 0
    return 1 + count(list[1:])
  • 리스트에서 가장 큰 수를 찾으시오.
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