[공유] Quick Sorting

출처 오분쯤 느린 시계|영양 (4) 퀵 정렬법(Quick Sorting) 퀵 정렬의 기본 동작은 정렬하고자 하는 리스트에서 하의기준이 되는 키를 선정하여 기준키를 적당한 위치로 이동하는 것이다. 이때 리스트에서 기준키를 경계로 기준키보다 앞에 있는 키들은 모두 기준키보다 작거나 같으며 기준키보다 뒤에 있는 키들은 모두 기준키보다 크거나 같게 만 든다. 다음과 같은 키들로 구성된 리스트를 생각해 보자. 리스트의 첫 원소를 기준키로 선정한 후 다음과 같은 동작을 수행한다. 기준키 바로 다음의 위치 부터 뒤쪽으로 기준키보다 큰 키를 찾으며, 동시에 리스트의 마지막 키부터 앞쪽으로 지준키보다 작은 키를 찾아 서로 교환한다. 위의 예에서 기준키는 17로 잡게 되며, 기준키보다 큰 키는 26이 되고 기준키보다 작은 키는 2가 되어 서로 교환을 하면 다음과 같은 리스트가 된다. 계속해서 다음 키부터 이러한 동작을 반복하면 기준키 17보다 큰 키는 24가 되고 작은 키는 8이 되어 서로 교환하면 ...

원문링크 : [공유] Quick Sorting