[알고리즘] 퀵 정렬

퀵 정렬 ( 출처 : https://ko.wikipedia.org/wiki/퀵_정렬 )

 

 

퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다.

 

분할 정복 방법

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

분할 정복 방법은 대개 순환 호출을 이용해 구현한다.

 

퀵 정렬 알고리즘의 구체적인 방법

하나의 리스트를 피벗을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,

두 개의 정렬된 부분 리스트를 합해 전체가 정렬된 리스트가 되게 하는 방법이다.

 

퀵 정렬은 다음의 단계로 이루어진다.

• 분할 : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열 ( 피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들 )로 분할한다.
• 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
• 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 순환 호출이 한번 진행될 때마다 최소한 하나의 원소 ( 피벗 )는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.