퀵정렬 (Quick-Sort)

퀵 정렬은 분할통치법에 기초한 정렬 알고리즘이다.

quickSort(L)

if(L.size() > 1)
{
 k ← position in List
 (Less , Equals , great) ← partition(L , k)
 quickSort(Less)
 quickSort(great)
 L ← merge(Less, Equals, great)
}
return

1. 분할

기준원소 pivot을 택하여 list를 세부분으로 나눈다.
less - pivot 보다 작은 원소
equals - pivot과 같은 원소
great - pivot 보다 큰 원소

2. 재귀
less와 great를 정렬

3. 세 리스트를 결합한다.

partition(L , k)

pivot ← L.element
less , equal , great ← empty list
while( !L.isEmpty() )
{
 element ← L.remove(L.first())
 if( element < pivot )
  less.insertLast(element)
 else if( element = pivot )
  equal.insertLast(element)
 else
  great.insertLast(element)
}
return (less , equal , great)

중복까지 처리 되지만 , 외부메모리를 사용한다.

삽입은 뒤에 추가하므로 복잡도는 O(1)이다.

그래서 partition의 복잡도는 O(n)이다.