정렬 알고리즘 Part2

Part2 에서는 복잡하지만 효율적인 정렬 알고리즘을 다룬다.

힙 정렬, 병합 정렬, 퀵 정렬 알고리즘을 다루려 했으나..

힙 정렬은 자료구조 힙의 특성을 이용한 정렬로, 힙에 데이터를 추가하는 과정에서 정렬된 데이터가 만들어지므로 딱히 쓸게 없다. (자료구조 힙이란? - https://sjkitpro.blogspot.com/2018/07/heap.html)

병합 정렬은.. 간신히 알고리즘을 이해하고 서적을 참고하여 소스를 짯으나, 완전히 이해하지 못한 것 같아 추후에 다시 공부할 때 이 부분을 업데이트 하겠다.

정렬 Part2 지만 퀵 정렬 하나만 다루는 슬픔....

퀵 정렬

퀵 정렬이 무엇인지는 아래에 나오는 그림들을 보고 이해하도록 한다. 말로는 어렵다는

퀵 정렬에서는 몇 가지 알아야 하는 용어가 있는데 하나씩 설명하겠다.

left : 정렬 대상 중 가장 왼쪽 데이터를 가리키는 이름

right : 정렬 대상 중 가장 오른쪽 데이터를 가리키는 이름

pivot : 정렬의 기준, 중심축이라는 의미

low : pivot을 제외한 가장 왼쪽 데이터를 가리키는 이름

high : pivot을 제외한 가장 오른쪽 데이터를 가리키는 이름

퀵 정렬에서 low는 오른쪽으로, high는 왼쪽으로 이동하는데 이동하는 기준은 아래와 같다.

low의 오른쪽 이동 : pivot보다 큰 값을 만날 때 까지 이동

high의 왼쪽 이동 : pivot 보다 작은 값을 만날 때 까지 이동

위에서 말한대로 low와 high가 이동하는 그림을 아래와 같은데 step 별로 설명을 담겠다.

step1 : low는 오른쪽으로 이동하다 pivot(5)보다 큰 데이터 8을 만나 멈춘다.

         high는 가리키던 데이터 4가 pivot(5)보다 작아 이동하지 않는다.

step2 : low와 high의 값을 바꾼다.

step3: 다시 low는 오른쪽으로 이동하다 pivot보다 큰 데이터 6을 만나 멈춘다.

         high는 왼쪽으로 이동하다 pivot보다 작은 데이터 2를 만나 멈춘다.

step4: low와 high 값을 바꾼다.

step5: 서로 이동하다 low가 high보다 큰 인덱스를 가리키는 상황.  더 이상 이동하지 않는다.

step6: pivot과 high의 값을 교환한다.

위 step 6의 데이터를 보면 pivot 값을 중심으로 왼쪽에는 pivot보다 작은 데이터가 오른쪽에서는 pivot보다 큰 데이터가 정렬된 걸 확인 할 수 있다.

나머지 정렬을 진행하기 위해 pivot을 기준으로 왼쪽과 오른쪽으로 분할한다.

분할된 왼쪽과 오른쪽에 left, right, low, high 개념을 지정하고 재귀적으로 위 과정을 반복한다.

퀵 정렬 성능평가

퀵 정렬의 시간 복잡도는 아래와 같다. (구글 블로그는 수식 추가 없나...???)

동일한 빅-오 를 갖는 다른 정렬 알고리즘에 비해 평균적으로 가장 빠른 정렬 속도를 보인다.