Algorithm _#8 정렬 알고리즘(2)

Quick Sort 알고리즘

: 실제 가장 빠른 정렬 알고리즘

• 방법: quick select와 동일

  -> pivot 정한 후, S/M/L로 나눠 정렬

  def quick_sort(A):
      if |A| <= 1: return A
      p = A[0]
      S,M,L = [],[],[]
        
      #(n-1)번 비교
      for x in A:
          if p>x:
              S.append(x)
          elif p<x:
              L.append(x)
          else:
              M.append(x)
          return quick_sort(s)+M+quick_sort(L)
  

  in-place (X) stable(O)

• 수행 시간

  -> T(n)= T(

  s

  )+ T(

  L

  ) +cn

  • worst case: (S나 L로 치우쳐져서 나오는 경우)(흔하지 않음)

    T(n) = T(n-1)+cn

    ​ =O(n^2)

  • best case: (S, L이 동일하게 반반씩 나오는 경우)

    T(n) = T(n/2)+T(n/2)+cn

    ​ = 2T(n/2) + cn

    ​ = O(nlogn)

in-place Quick_Sort algorithm

-> not in-place한 quick_sort의 단점을 보완한 알고리즘

def quick_sort(A, first, last):
    #A[first]...A[last]를 quick.sort!
   	p = A[first]
	left = first + 1,right = last 
    
    #pivot보다 큰 것과 작은 것으로 정렬
    while left <= right:
        while left <= last and A[left]<p:
            left += 1
        while A[right] > p:
            right -= 1
        if left<=right:
            A[left], A[right] = A[right], A[left]
            left += 1, right -= 1 # 계속 진행
    # 현재 p, first+1 ~right(작은 것), left~last(큰 것)으로 정렬됨
    A[first], A[right] = A[right], A[first]
    
    quick_sort(A, first, right-1)
    quick_sort(A, left, last)

Merge Sort 알고리즘

• 방법: 반으로 나눈 후 각각 정렬후 두 부분을 합병(merge)

  def merge_sort(A, first, last):#A[first].. A[last]merge sort
      if first>=last: return 
      merge_sort(A, first, (first+last)//2)
      merge_sort(A, (first+last)//2 + 1, last)
      merge_two_sorted_lists(A, first, last)
  def merge_two_sorted_lists(A, first, last):
      m = (first+last)//2
      i, j = first, m+1
      B=[]
    
      while i<=m and j<=last:
          if A[i] <= A[j]:
              B.append(A[i])
              i += 1
          else:
              B.append(A[j])
              j+=1
      for k in range(i,m+1):
          B.append(A[k])
      for k in range(j, last+1): 
          B.append(A[k])
    
      for i in range(first, last+1): #O(n)
          A[i] = B[i-first]
  

• 수행시간

  T(n) = 2T(n/2)+cn

  ​ =O(nlogn)

비교 횟수에 대한 하한(lower bound)

• 비교 중심 정렬 알고리즘:
  • O(n^2): selection, bubble, insertion
  • O(n^2) & O(nlogn) : quick
  • O(nlogn): merge, heap

decision tree(결정 트리)

ex) A = [a0, a1, …,an-1] (n개 값에 대한 결정 트리)

h(높이)만큼의 비교가 필요함!

하한: h

• h 구하기

  heap 모양: n개의 leaf

  -> h>= log(n+1)

  -=> h>= logn! >= (n/2)log(n/2)

  ​ = O(nlogn)