퀵 소트
퀵 소트(quick sort) ( * 오름차순 기준 * )
기준을 잡은 후 기준을 피벗이라고 하자 피벗을 제외한 숫자들을 가지고 정렬하는데 피벗 보다 작다면 왼쪽을 크다면 오른쪽으로 나눈 후 왼쪽과 오른쪽에서 다시 피벗을 잡아 다시 정렬하며 모든 정렬이 끝날 때까지 이를 반복한다.
< 비교 방법 >
0. 피벗을 재외한 후 두개의 비교할 값을 정한다.(편의상 l(left)와 r(right)로 칭하겠다.)
1. l이 피벗보다 작고 r이 피벗보다 크다면 둘다 새로운 값을 정한다.
(l과 r의 값이 같아도 동일하다.)
2. l이 피벗보다 크고 r이 피벗보다 작다면 서로 값을 바꾼 후 새로운 값을 정한다.
3. l이 피벗보다 작고 r이 피벗보다 작다면 l의 값만 새로 정한다.
4. l이 피벗보다 크고 r이 피벗보다 크다면 r의 값만 새로 정한다.
5. l이 r보다 오른쪽으로 간다면 l의 값과 피벗을 서로 바꾼다.
(해당 피벗에 대한 정렬은 끝이며 왼쪽과 오른쪽에 정렬해야할 수가 남았다면 피벗을 잡고 다시 정렬한다.)
ex )
l = 7 , r = 6 , 피벗 = 4
7 |
5 |
3 |
2 |
1 |
6 |
4 |
l |
|
|
|
|
r |
피벗 |
< 비교 4 >
7 |
5 |
3 |
2 |
1 |
6 |
4 |
l |
|
|
|
r |
|
피벗 |
< 비교 2 >
1 |
5 |
3 |
2 |
7 |
6 |
4 |
|
l |
|
r |
|
|
피벗 |
< 비교 2 >
1 |
2 |
3 |
5 |
7 |
6 |
4 |
|
|
l, r |
|
|
|
피벗 |
< 비교 3 >
1 |
2 |
3 |
5 |
7 |
6 |
4 |
|
|
r |
l |
|
|
피벗 |
< 비교 5 >
1 |
2 |
3 |
4 |
7 |
6 |
5 |
|
|
|
|
|
|
|
피벗 4에대한 정렬 완료. 이 후 4의 왼쪽과 오른쪽에서 동일하게 퀵 소트를 진행하면 된다.
위 소스 코드에서 최악의 경우는 7 6 5 4 3 2 1나 1 2 3 4 5 6 7 일 것이다.
이런 최악의 경우에 대비하고자 한다면 피벗에 대한 선택을 개선하면 될것이다.