1. 퀵 정렬(Quick Sort)?
한 원소를 축으로 하여 축보다 작은 원소는 축보다 앞에 위치시키고, 축보다 큰 원소는 축보다 뒤에 위치 시킵니다. 그 다음, 축의 앞부분과 축의 뒷부분을 각각 같은 방법으로 반복해줘서 정렬하는 방법이 퀵 정렬입니다.
2. 퀵 정렬의 실제
3
|
8
|
7
|
1
|
5
|
데이터를 가지고 직접 퀵 정렬을 해봅시다. (여기서는 축을 구간의 가장 뒤의 원소로 잡습니다)
1. 축을 설정한다.
3
|
8
|
7
|
1
|
5
|
2. 축보다 작은 원소는 앞쪽으로, 축보다 큰 원소는 뒷쪽으로 배치한다.
2-1. 앞쪽에서 축보다 큰 원소를 찾고, 뒤쪽에서 축보다 작은 원소를 찾은 뒤 교환해준다.
3
|
8
|
7
|
1
|
5
|
3
|
8
|
7
|
1
|
5
|
3
|
1
|
7
|
8
|
5
|
3
|
1
|
7
|
8
|
5
|
3
|
1
|
5
|
8
|
7
|
3
|
1
|
5
|
8
|
7
|
3
|
1
|
5
|
8
|
7
|
1
|
3
|
5
|
8
|
7
|
1
|
3
|
5
|
8
|
7
|
1
|
3
|
5
|
8
|
7
|
1
|
3
|
5
|
7
|
8
|
1
|
3
|
5
|
7
|
8
|
3. C를 이용한 구현
4. 축으로 어떤 원소를 설정해야하는가? 퀵 정렬은 축을 어떤 원소로 설정하느냐에 따라 속도차이가 발생한다. 예를 들어 축이 가장 작은 원소나 가장 큰 원소일 경우, 분할의 의미가 없어지게 된다. 이렇게 될 경우 정렬하는데 소요되는 시간이 늘어나고 -> O(N^2), 심할 경우에는 함수 호출의 누적으로 인한 Stack Overflow가 발생할 수 있다. 이를 해결하기 위해서는 중간값을 갖는 원소를 축으로 설정하는 경우가 최적이겠지만, 중간값을 찾는데도 시간이 소모되기 때문에, 다음과 같은 방법들이 이용된다.
1. 랜덤으로 축을 지정.
축을 랜덤으로 지정할 경우 가장 작은 원소나 가장 큰 원소를 축으로 설정할 확률이 낮아지기 때문에 최악의 상황을 피할 수 있다.
2. 구간내 맨 앞의 원소, 중간에 위치하는 원소, 맨 뒤의 원소중에서 중간값으로 축을 지정.
이 방법을 사용할 경우 최악의 경우 일지라도 축보다 작은 값과 큰 값이 항상 하나씩 존재하게 되기 때문에 축을 중심으로 배치하는데 걸리는 시간을 조금이나마 줄일 수 있다.
이외에도 여러가지 방법이 있을 수 있고, 퀵정렬에서 축을 어떤 원소로 지정하느냐는 속도에 큰 영향을 중요한 문제이므로, 상황에 따라 적절한 방법을 이용하자.
※ 축을 나눌때 같은 값이 존재하는 경우에는 둘로 나누기 위해서 작은 쪽이나 큰 쪽에 포함되도록 해야한다.
