[Algorithm] 퀵(Quick)/계수(Count)정렬

 

• 퀵 정렬(Quick Sort)
  • 리스트에서 첫 번째 데이터를 피벗으로 설정 후 피벗값을 기준으로 왼쪽과 오른쪽부분으로 정렬한다.
  • 시간복잡도 O(NlogN)

  array = [7,5,9,0,3,1,6,2,4,8]
  
  def quick_sort(array):
      # 리스트가 하나 이하의 원소만을 담고 있다면 종료
      if len(array) <= 1:
          return array
      pivot = array[0]
      tail = array[1:]
  
      left_side = [x for x in tail if x <= pivot]
      right_side = [x for x in tail if x > pivot]
  
      # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
      return quick_sort(left_side) + [pivot] + quick_sort(right_side)
  
  print(quick_sort(array))
  

• 계수 정렬(Count Sort)
  • 비교 기반인 선택,삽입,퀵과는 다르게 특정한 조건이 부합할 때만 사용
  • 시간복잡도 O(N+K), 공간복잡도 O(N+K)

  • # 모든 원소의 값이 0보다 크거나 같다고 가정
    array = [7,5,9,0,3,1,6,2,4,8]
    # 모든 범위를 포함하는 리스트 선언(모든값은 0으로 초기화)
    count = [0] * (max(array) + 1)
    
    for i in range(len(array)):
        count[array[i]] += 1
    
    for i in range(len(count)):
        for j in range(count[i]):
            print(i, end=' ')