[JAVA/자료구조] 퀵 정렬(Quick Sort)

---

평균 수행 시간이 O(logN)인 알고리즘

• 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)
• 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다.
• 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다.

 

퀵 정렬(Quick Sort)

• 퀵 정렬은 n개의 데이터를 정렬할 때 최악의 경우 O(n^2)번의 비교를 수행하고, 평균적으로 O(logN)번의 비교를 수행한다.
• 퀵 정렬은 찰스 앤터니 리처드호어가 개발한 정렬 알고리즘이다.
• 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있기 때문에 불안정 정렬에 속한다.

퀵 정렬(Quick Sort) 구현

• 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한다.
• 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라 한다.
• 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 후 피벗은 더이상 움직이지 않는다.
• 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때 까지 반복된다.
• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

 

퀵 정렬(Quick Sort) 구현 결과

[0] : 10 [1] : 20 [2] : 30 [3] : 40 [4] : 70 [5] : 90