고급정렬 알고리즘(2) - 퀵 정렬

이전에 분리작업 후 병합작업을 통해서 정렬을하는 병합정렬에 대해 알아보았다.

이때 분리작업에서 가장 끝을 기준원소로 정해서 진행했는데, 퀵 정렬 또한 기준원소가 핵심이 되며, 재귀를 통해 정렬이 이루어진다.

퀵 정렬은 기준원소를 전체 원소들의 크기와 비교하여 (정렬이 되도록)알맞은 위치에 넣어주고 기준원소보다 작은 원소들을 모아두는 형태를 가진다. 그리고 기준원소의 앞 뒤를 전반, 후반부로 나누어 이전의 작업(기준원소를 알맞은 위치에 넣어주고 그 값보다 작은 원소들을 모아두는 작업)을 각각 반복한다며 정렬이 되어가는 형태를 볼 수 있다.

예를들어, 

7, 4, 5, 2, 1, 3일 경우에 맨 뒤의 원소(3)를 기준원소로 가정해보자.

정렬 전  :   7, 4, 5, 2, 1, 3      → 기준원소 (3)

1회 과정을 거치면 2, 1, 3, 7, 4, 5가 된다.

아까 위에서 설명한 것처럼 기준원소 3이 전체의 원소들과의 비교를 통해 적절한 위치에 맞춰준것을 볼 수 있으며, 이 작업들을 통해서 기준원소보다 작은 원소들(2, 1)은 앞에, 큰 원소들(4, 5, 7)은 뒤에 위치하는 (전반부, 후반부로 나누는)과정을 볼 수 있다. 

그리고 전반부의 원소들과 후반부를 각각 맨 끝값을 기준원소로 가정해서 위의과정을

똑같이 이어가면 된다. 

1회 퀵 정렬 :  7, 4, 5, 2, 1, 3 

맨 끝이 3이 기준원소로 전반부(2, 1)와 후반부(4, 5, 7)로 나누어 진다.

자세히 살펴보면, 기준원소 3을 나머지 원소(7, 4, 5, 2, 1)와 차례로 비교하면서

작거나 같은 값을 앞의 원소(3보다 큰 원소이어야 함)부터 위치를 바꾸어주면 된다.

ex) 1회 퀵 정렬의 과정들

- 첫 번째 비교    7, 4, 5, 2, 1, 3      -  Not Exchange

  : 기준원소 3과 첫 번째 7을 비교하면, 7이 더 크므로 그대로 둔다.

- 두 번째 비교    7, 4, 5, 2, 1, 3      -  Not Exchange

  : 기준원소 3과 두 번째 4를 비교하면, 4가 더 크므로 그대로 둔다.

- 세 번째 비교    7, 4, 5, 2, 1, 3      -  Not Exchange

  : 기준원소 3과 세 번째 5를 비교하면, 5가 더 크므로 그대로 둔다.

- 네 번째 비교    7, 4, 5, 2, 1, 3      -  Exchanged  ( 2, 4, 5, 7, 1, 3 )

  : 기준원소 3과 네 번째 2를 비교하면, 2가 더 작으므로 앞의 3보다 

    큰 값(7)과 자리 교환!

- 다섯 번째 비교 2, 4, 5, 7, 1, 3      -  Exchanged  ( 2, 1, 5, 7, 4, 3 )

  : 기준원소 3과 다섯 번째 1를 비교하면, 1이 더 작으므로 앞의 3보다 

    큰 값(4)과 자리 교환!

- 여섯 번째 비교 2, 1, 5, 7, 4, 3      -  Exchanged  ( 2, 1, 3, 7, 4, 5 )

  : 기준원소 3을 전체원소와 비교과정을 마쳤다면, 이제 3을 알맞은 위치에 넣어주어야

    하는데, 맨 앞의 3보다 큰 값(5)과의 자리를 바꾸어주면, 알맞은 위치에 들어가며

    퀵 정렬 1회 과정을 마친셈이다.

기준원소를 어떻게 이용하는지 위에서 살펴보았으며,

전반부와 후반부의 각각의 기준원소를 정해서 위의 과정과 같은 비교를 진행하면 된다.
1회 결과  :   2, 1, 3, 7, 4, 5

▶ 전반부 : 2, 1              → 기준원소 (1)

▶ 후반부 : 7, 4, 5           → 기준원소 (7)

2회 퀵 정렬 :  2, 1 

맨 끝의 1이 기준원소로 2보다 작으므로 앞으로보내면 된다.

2회 결과  :  1, 2

▶ 전반부 :  없음.            → 전반부 원소가 없으므로 진행  X

▶ 후반부 :  2                 → 후반부 원소가 하나이므로 굳이 진행할 필요가 없다.

3회 퀵 정렬 :  7, 4, 5 

맨 끝의 5가 기준원소로 5보다 작은 값 4는 전반부이며, 5보다 큰 7은 후반부가 된다.

3회 결과  :  4, 5, 7

▶ 전반부 :  4                → 전반부 원소가 하나이므로 굳이 진행할 필요가 없다.

▶ 후반부 :  7                → 후반부 원소가 하나이므로 굳이 진행할 필요가 없다.

이처럼 전반부, 후반부로 나누어가며 진행을 하고 각각의 기준원소를 

각 (전반 or 후반)부의 전체 원소들과 비교를 하면서 기준원소를 적절히 위치시키면 된다.

복잡해 보이지만.. 실제 업무에서 퀵 정렬은 효율성이 좋아서 실제 업무에서도 빈번히

사용된다.

그렇다면, 퀵 정렬의 수행시간은?

위에서 살펴본 퀵 정렬의 과정들은 크게 2개의 수행으로 나눌 수 있다.

1) 먼저 기준원소를 전체와 비교하는 수행시간             →  n에 비례

: n에 갯수에 따라서 기준원소를 전체와 비교하는 시간은 증가할 것이다. 그러므로,

  n의 수행시간이 걸린다.

2) 기준원소를 통해 전반, 후반으로 나누는 수행시간     →  log(n)에 비례

: 기준원소에 따라서 전반부와 후반부를 나눌 수 있으므로, log(n)의 수행시간이 걸린다.

이 두개의 과정을 합치면 n log(n)의 수행시간이 걸린다. 

이는 병합정렬의 수행시간과 거의 흡사하며 이전에 살펴본 기초적인 정렬알고리즘에서

삽입, 선택, 버블정렬의 수행시간보다는 더 뛰어난 수행시간을 갖는다. 하지만 이것은

평균적인 수행시간의 비교했을 경우라는 점을 꼭 잊지말자!

퀵 정렬의 알고리즘을 살펴보면,

▶실행결과