n(log(n)) 정렬

 

n(log(n)) 정렬

 

불안정 정렬, 안정 정렬은 뭘까요?

정렬 후에 정렬 기준 값이 같은 원소의 상대적인 위치가 바뀌는 것의 유무를 말합니다.

출처 : 제타위키

• 불안정 정렬의 종류 : Selection, Heap, Quick
• 안정 정렬의 종류 : Bubble, Insert, Merge, Counting, Radix

 

Quick sort

피봇을 기준으로 왼쪽은 작은값, 오른쪽은 큰값으로 한다는 왼쪽, 오른쪽에서 재귀적으로 다시 실행합니다.

불안정 정렬입니다.

가장 빠릅니다.

다른 n(log(n)) 정렬 중 quick sort가 왜 제일 빠를까요?

데이터의 locality(지역성)가 높기 때문에 그렇습니다.

그럼 locality는 뭘까요?

모든 데이터는 시간 지역성, 공간 지역성이 있습니다. 데이터는 자주 사용하는 것과 적게 사용하는 것이 있습니다(1 : 9 법칙). 시간 지역성은 최근에 사용된 데이터는 다시 사용될 가능성이 높다는 것입니다. 공간 지역성은 비슷한 위치에 있는 데이터는 재사용될 가능성이 높다는 것입니다. 컴퓨터에서는 캐시가 이런 것을 활용합니다.

  function quicksort(a, left, right)
      if right > left then
          select a pivot value a[pivotIndex]
          pivotNewIndex := partition(a, left, right, pivotIndex)
          quicksort(a, left, pivotNewIndex-1)
          quicksort(a, pivotNewIndex+1, right)

  function partition(a, left, right, pivotIndex)
      pivotValue := a[pivotIndex]
      swap(a[pivotIndex], a[right]) // 피벗을 끝으로 옮겨 놓는다.
      storeIndex := left
      for i from left to right-1
          if a[i] <= pivotValue then
              swap(a[storeIndex], a[i])
              storeIndex := storeIndex + 1
      swap(a[right], a[storeIndex]) // 피벗을 두 리스트 사이에 위치시킨다.
      return storeIndex

 

Merge sort

가장 작은 단위로 쪼갠다음 merge를 반복해서 정렬합니다.

안정정렬입니다.

메모리보다 큰 데이터를 정렬 가능합니다(External Merge sort)

 

Point는 '안정정렬이냐 유무', '메모리보다 큰 데이터 정렬하느냐' 입니다.

 

Heap sort

Heapify를 하여 정렬한 것입니다.

배열의 인덱스를 통해 자식, 부모를 알 수 있습니다.

전체 정렬보다는 일부 몇 개를 가져올 때 가장 빠릅니다.

우선순위큐를 만들 때 주로 사용합니다.