[알고리즘] 기준에 따라 시간복잡도에 많은 영향을 끼치는 퀵 정렬

하나의 기준을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는것이 핵심이다. 

기준이 되는 pivot 과 start 가 가리키는 데이터, end 가 가리키는 데이터를 비교하게 되는데 

pivot < start : 오른쪽 한칸 포인터 이동

pivot > end : 왼쪽으로 한칸 포인터 이동

pivot > start : 그 자리에서 멈추어 end 포인터를 기다림(또는 기다린 end 포인터 자리와 swap)

pivot < end : 그 자리에서 멈추어 start 포인터를 기다림(또는 기다린 start 포인터 자리와 swap)

 

swap 후 start 는 오른쪽, End 는 왼쪽으로 1칸씩 이동 start 와 end 가 만날때까지 반복하고 만나는 지점에서 가리키는 데이터를 비교하여 pivot 이 더 크면 만나는 지점 데이터 오른쪽에, pivot 이 더 작으면 만나는 지점 데이터 왼쪽에 삽입하여 준다.

 

생각보다 구현하기에 복잡할거라 생각하고 해당 유형을 담은 코딩테스트 진행 후 링크를 걸어 게시할 예정이다.