퀵정렬을 알아보자.araboja

퀵정렬 알고리즘을 포크댄스로 표현해준 영상입니다. 정렬 과정을 쉽게 이해 할 수 있으니 즐겁게 시청합시다. 쿵짝 쿵짝짝.

퀵정렬에서 가장 중요한 개념은 pivot과 분할이라고 생각합니다.

pivot으로 지정된 인덱스를 기준으로 다른 인덱스들을 비교하는 과정으로 정렬이 이루어 집니다.

• 이 과정에서 아래와 같은 단계를 거치게 됩니다.
  1. 배열의 가운데 인덱스를 pivot으로 지정하고 오른쪽 끝으로 밀어낸다. (혹은 처음부터 오른쪽 끝 값을 pivot으로 지정한다) 이 때, pivot이 외친다. “기준~!”
  2. 왼쪽부터 pivot과 비교해가며 pivot보다 큰 수를 찾아낸다.
  3. 오른쪽부터 pivot과 비교해가며 pivot보다 작은 수를 찾아낸다.
  4. 찾아낸 두 숫자의 위치를 바꿔준다.
  5. 반복

예를 들어 2,6,5,3,8,7,1,0 와 같은 배열이 있을 때 3을 pivot으로 지정했다고 가정합시다.

1. 퀵정렬은 우선 3을 가장 오른쪽으로 치워줍니다. 0은 3의 자리로 밀려납니다.
   • 2,6,5,0,8,7,1,3
2. 위에서 설명한 비교과정을 통해 6과 1을 찾았어요. 두 숫자의 위치를 바꿔줍니다.
   • 2,1,5,0,8,7,6,3
3. 위치가 바뀐 두 숫자보다 안쪽에 있는 숫자들을 다시 비교하고 위치를 바꾸기 시작해요.
   • 2,1,0,5,8,7,6,3
4. 마지막에 위치가 바뀌어 오른쪽으로 보내진 숫자와 pivot을 바꿔줍니다.
   • 2,1,0,3,8,7,6,5
5. 이 과정이 반복됩니다.

자, 자세히 보면 4번째 과정을 끝냈을 때 pivot의 위치는 제자리가 맞습니다. 앞으로도 이 위치는 변하지 않습니다.
3 왼쪽의 숫자들은 모두 3보다 작고 3 오른쪽의 숫자들은 모두 3보다 큽니다.
앞으로 3은 그대로 두고 다른 숫자들만 정렬해주면 됩니다.
매력적인 점은 앞으로 제 자리를 찾은 3을 기준으로 왼쪽 오른쪽 숫자들을 각각 따로 정렬해 주게 된다는 것인데, 이로써 비교 횟수가 많이 줄어들게 됩니다.

남은 정렬 과정을 나열하면 아래와 같게 됩니다.

1. 우선 오른쪽 큰 조각부터 정렬 합니다.
   • 8,7,6,5
   • 8,5,6,7
   • 6,5,8,7
   • 6,5,7,8
2. 자 이제 7이 제 자리를 찾았습니다. 자리를 찾지 못한 숫자들은 이제 세조각이 되었습니다. 비교 횟수가 더욱 줄게 됩니다.
   • 2,1,0
   • 2,0,1
   • 0,2,1
   • 0,1,2
3. 또 줄어든 조각.
   • 6,5
   • 5,6
4. 이와 같은 과정으로 정렬된 조각들이 다 합쳐집니다
   • 0,1,2,3,5,6,7,8

• 그렇다면 pivot은 어떻게 정해지는가? 가장 흔히 쓰이는 방법은 median-of-three 입니다. 가운데 있는 값을 선택 합니다. 위의 예제에서는 2,6,5,3,8,7,1,0 에서 3이 선택 되었습니다.

• 시간복잡도는 어떤가요?
  • 주어진 배열에 따라 달라지게 되는데, 최악의 상황에서는 O(n2)가 나오게 되고 평균적인 상황에서는 O(nlogn)이 나옵니다.
• 세줄요약
  1. 퀵정렬은 pivot을 기준으로 움직인다.
  2. 분할하고 각각 정렬하는 방식을 택한다.
  3. 이름처럼 빠른 정렬적인 정렬! 그러나 제일 빠른 정렬 방식은 아니다.

Reference

-Quick-sort with Hungarian (Küküllőmenti legényes) folk dance by AlgoRythmics
-Quick sort in 4 minutes by Michael Sambol
-programcreek.com