CH10-2복잡하지만 효율적인 정렬 알고리즘(9)
퀵 정렬에 대해 배워보자.
윤성우님은… 병합정렬 설명할때는 병합정렬이 멋있어보이고, 퀵정렬 설명할때는 퀵 정렬이 멋있어보인다고 함..
퀵정렬에는 4개의 변수를 둔다. left, right, low, high
left와 right는 정렬대상의 시작과 끝 인덱스 값이다.
low와 high는 무엇인가? 이건 다음 단계에 말해주겠다. 그전에 pivot을 설명해야 한다.
이 피벗이 퀵정렬에서 핵심적인 역할을 한다. 어떤 인덱스를 pivot으로 정하냐에 따라 퀵 정렬의 성능이 달라질 정도이다.
pivot은 정렬 대상에서 가장 왼쪽에서 위치한 데이터로 pivot을 정한다. 이때 low는 pivot을 제외한 가장 왼쪽에 있는 인덱스, high는 pivot을 제외한 가장 오른쪽에 있는 인덱스이다.
위와 같은 방식으로 변수를 정의해주는게 퀵 정렬의 초기화이다.
초기화가 끝나면 다음단계로 넘어간다. 목표를 오름차순 정렬로 정하자. 작은 숫자일수록 정렬에 우선순위를 갖는다.
low는 피벗보다 정렬의 우선순위가 낮은 데이터를 만날때까지 오른쪽으로 이동시키고
high는 피벗보다 정렬의 우선순위가 높은 데이터를 만날때까지 왼쪽으로 이동시킨다.
위 그림대로라면, low는 7에서 멈추고, hight는 4에서 멈춘다.
참고로 low와 high의 이동은 서로 독립적이다. 별개의 문제로 다룬다.