기준값으로 분할과 정복을 수행하는 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)의 개요

개념

기준 값인 피벗(Pivot)을 중심으로 작은 값은 좌측에 큰 값은 우측에 위치시켜 분할과 정복(Divide and Conquer)으로 정렬을 수행하는 알고리즘

 

특징

빠른 속도 : 선택정렬과 삽입정렬보다 빠른 정렬 수행 (다만 힙정렬보다는 느림)

분할과 정복 : 기준 값(Pivot)을 기준으로 앞, 뒤의 비교를 통해 스왑(Swap) 수행

재귀적 수행 : 분할을 마친 후 분할된 부분에서 반복 수행

- 수행시간 복잡도 : O(n-log2n)

 

퀵 정렬의 과정

 

퀵 정렬의 과정

1. 리스트(5,3,8,4,6,3,2)에서 피벗으로 4의 값을 선택

2. 4보다 작은 값(3,3,2)은 좌측, 4보다 높은 값은 (5,8,6)

3. 좌측과 우측에서 다시 Pivot(좌측은 3, 우측은 8)을 선정하고 정렬 수행

 

퀵 정렬의 알고리즘 

quickSort(array, leftmostIndex, rightmostIndex)
  if (leftmostIndex < rightmostIndex)
    pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
    quickSort(array, leftmostIndex, pivotIndex)
    quickSort(array, pivotIndex + 1, rightmostIndex)

partition(array, leftmostIndex, rightmostIndex)
  set rightmostIndex as pivotIndex
  storeIndex <- leftmostIndex - 1
  for i <- leftmostIndex + 1 to rightmostIndex
  if element[i] < pivotElement
    swap element[i] and element[storeIndex]
    storeIndex++
  swap pivotElement and element[storeIndex+1]
return storeIndex + 1