자료의 정렬 - 퀵 정렬(Quick sorting)

퀵 정렬(Quick sorting)

피벗(pivot)을 기준으로 분류만을 통해 정렬을하는 방법.

 

  -피벗(pivot)이라고 부르는 기준을 필요로 함.

  -그 기준을 이용해 그 기준보다 작은 수들의 그룹과 그 기준보다 큰 수들의 그룹으로 나눈다.

  -일반적으로 왼쪽에서 오른쪽으로 가면서 피벗보다 큰 수를 찾아가고

  -오른쪽에서 왼쪽으로 가면서 피벗보다 작은 수들을 찾아 서로 자리를 바꾼다.

 

퀵정렬(Quick sorting)의 방법

① pivot을 선정하여 pivot을 기준으로 좌측과 우측으로

② 왼쪽→오른쪽으로 가면서 pivot보다 큰 값을 찾고, 오른쪽→왼쪽으로 작은값 찾기

③ 두 값 교환→ pivot값과 작은 값 교환

④ pivot 변경→ 왼쪽으로 오면서 작은 값이 pivot 바로 다음 값일때→ pivot과 교환 후, pivot 변경

퀵정렬(Quick sorting) 예시

Case1. 6개의 자료가 3, 7, 2, 5, 1, 4와 같이 임의의 순서를 가진 경우를 예시로 들어본다.

 

우선 첫 번째 수를 pivot으로 결정하고 왼쪽에서 오른쪽으로 가면서 pivot보다 큰 값을 찾으면두 번째 7이

되고 오른쪽에서 왼쪽으로 가면서 pivot 3보다 작은 값을 찾으면 1이 되므로 이 둘을 교환한다.

위 과정을 반복하면 네 번째 수에서 pivot에 대한 비교가 중단되므로 pivot의 값과 네 번째 수를 교환하여

두 개로 분할되고 pivot 3의 위치가 결정된다.

분할된 두 부분에 대해 각각 pivot을 선정하고 위 과정을 반복한다. 분할된 한 영역의 정렬이 완료되면 다른

영역도 동일한 과정을 반복하면 된다.

정렬완료.

 

Case2. 6개의 자료가 1, 3, 4, 2, 5, 7와 같이 어느 정도 정렬이 된 순서를 가진 경우.

첫 번째 수 1을 pivot으로 선정하고 왼쪽에서 오른쪽으로 가면서 pivot 1보다 큰 값 3을 찾고 오른쪽에서 왼쪽으로

가면서 pivot 1보다 작은 값을 찾으면 되지만, 없으므로 pivot 1의 위치는 변경 없이 단계가 종료된다.\

pivot을 다음 수인 3으로 선정하고 위 과정을 반복하여 pivot 3보다 큰 값 4와 작은 값 2를 찾고 두 수를 교환한다.

다시 pivot 3보다 큰 값과 작은 값을 더 이상 없으므로 pivot 3과 2를 교환한다.

pivot이 2이고 남은 수가 없으므로 왼쪽 영역은 정렬이 완료된다. 오른쪽 영역은 pivot을 4로 선정하고 pivot보다

큰 값과 작은 값을 찾아 교환한다.

pivot을 5로 하고 pivot보다 큰 값과 작은 값을 찾지만, pivot보다 큰 값만 존재하므로 교환없이 오른쪽 영역의 정렬이

완료된다.

정렬완료.

 

퀵정렬(Quick sorting) 알고리즘

코드 출처 : 제타위키

퀵정렬 구현 - 제타위키

퀵정렬(Quick sorting) 특징

  -교환 및 비교 횟수가 매우 적으며 단순하고 매우 빠른 속도로 정렬을 수행한다. 편균 연산 시간에 있어서

    내부 정렬 방법 중 가장 우수하다.

  -pivot이 중간값을 갖도록 해야 수행 속도가 좋다.(pivot의 위치가 수행 속도에 관련이 깊다.)

  -스택 공간을 사용하며 재귀 호출을 기반으로 동작한다.(분할 정복 설계 기법 활용)

  -n개의 데이터가 저장된 배열이 각 분할 단계에서 정확히 이등분될 경우 효과적이다.

퀵정렬(Quick sorting) 비교횟수

  -최대 Quick sorting 비교횟수  ⇒ n²

  -탐색의 평균 비교 횟수  ⇒ n log₂n

 

 

도움되는 사이트

  - https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

정렬되는 모습을 실시간으로 보여주는 사이트이다.

사진으로 보는것보다 직접 정렬되는 모습을 보면 이해하기 더욱 쉽다.