퀵 정렬
-
Quick SortC 자료구조/Sort Advanced 2020. 6. 22. 17:57
퀵 정렬도 분할 정복 방법에 근거한다. 여기서 정렬방식은 오름차순 기준이다. 퀵 정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각 각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용한다. 그러나, 병합 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비 균등하게 분할한다. 먼저, 리스트 안에 있는 한 요소를 피봇으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피봇으로 하기로 한다. 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로 옮겨지고 피봇보다 큰 요소들은 모두 피봇의 오른쪽으로 옮겨진다. 결과적으로 피봇을 중심으로 왼쪽은 피봇보다 작은 요소들로 구성되고, 오른쪽은 피봇보다 큰 요소들로 구성된다. 이 상태에서 피봇을 제외한 왼쪽 리스트와 오른쪽 리..