티스토리 뷰
퀵 정렬 (Quick Sort)
기준이 되는 원소를 기준으로 하여 기준 원소보다 작거나 같은 값을 지닌 자료는 앞으로 큰 값을 진ㄴ 자료는 뒤로 가도록 하여 기준 원소를 중심으로 분할해가며 정렬을 진행하는 방식입니다.
■ 정렬방식
1. 기준이 되는 원소를 정합니다. 배열의 시작 원소를 pivot으로 설정합니다.
2. 좌우 인덱스를 지정합니다. 해당 인덱스는 다음을 의미합니다.
- left : pivot 보다 큰 값을 찾으러 다니는 index
- right : pivot 보다 작은 값을 찾으러 다니는 index
- left_hold : pivot을 제외하고 정렬 대상의 시작점
- right_hold : pivot을 제외하고 정렬 대상의 끝점
3. left를 pivot보다 큰 값을 찾을 때 까지 이동합니다.
4. right를 pivot보다 작은 값을 찾을 때 까지 이동합니다.
5. left <= right 조건이라면 두 원소를 스왑합니다.
6. 3번 4번 과정을 left<=right 만족 할때까지 반복합니다.
7. left 와 right가 교차하게 되면 right 위치에 pivot 값을 대입합니다.
8. right를 기준으로 분열된 배열에대해서 퀵 정렬을 반복합니다.
|
|
: pivot
|
|
: Swap 되는 원소
|
5 |
4 |
8 |
2 |
9 |
3 |
11 |
1 | ||
다음 원소들에 대해서 퀵 정렬을 실행 해보겠습니다.
|
5 |
4 |
8 |
2 |
9 |
3 |
11 |
1 |
pivot left right
먼저 배열의 첫 번째 요소인 5가 pivot이 됩니다. left는 pivot을 제외한 배열의 가장 앞에로 지정을 하고 right도 pivot을 제외한 배열의 끝점으로 지정을 합니다.
|
5 |
4 |
8 |
2 |
9 |
3 |
11 |
1 |
pivot left right
이제부터 left부터 5보다 큰 수를 찾아가보겠습니다. 4는 5보다 작으므로 left를 이동시킵니다.
|
5 |
4 |
8 |
2 |
9 |
3 |
11 |
1 |
pivot left right
8은 5보다 크므로 멈춥니다. 다음으로 right를 피벗보다 작은 수를 찾아 이동시키겠습니다. 이번 경우는 시작부터 5보다 작은 수 1이므로 그대로 멈추게 됩니다.
|
5 |
4 |
1 |
2 |
9 |
3 |
11 |
8 |
pivot left right
이제 left와 right가 가르키는 원소를 서로 스왑합니다. 다음으로 아직 left와 right가 교차하지 않았으므로 다시 left부터 맞는 위치를 찾아갑니다.
|
5 |
4 |
1 |
2 |
9 |
3 |
11 |
8 |
pivot left right
다음으로 5보다 큰 수 9에서 left는 멈추게 됩니다.
|
5 |
4 |
1 |
2 |
9 |
3 |
11 |
8 |
pivot left right
right의 다음위치는 3이 됩니다.
|
5 |
4 |
1 |
2 |
3 |
9 |
11 |
8 |
pivot left right
left와 right를 교환합니다.
|
5 |
4 |
1 |
2 |
3 |
9 |
11 |
8 |
pivot right left
다음으로 left와 right를 이동시키게 되면 드디어 right와 left가 교차하게 됩니다.
|
3 |
3 |
1 |
2 |
5 |
9 |
11 |
8 |
pivot right left
right와 pivot이 가르키는 원소를 서로 교환해줍니다.
그림을 보면, 현재 5를 기준으로 하여 왼쪽에는 5보다 작은 수 오른쪽에는 5보다 큰수가 놓이게 됩니다. 즉 5는 제자리를 찾게 되는 겁니다. 이제 계속해서 5를 기준으로 분열 된 두 배열에 대해서도 똑같은 작업을 반복을 해주면 됩니다.
■ 특징
1. 최악의 경우 O(n＾2) 비교를 수행하고, 평균적으로 O(nlog n)번의 비교를 수행
2. 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘 설계가 가능
3. 다른 정렬 알고리즘에 비해 빠르게 동작 가능
■ 소스코드 (Source Code)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 |
public int[] Quick_Sort(int[] data,int left,int right)
{
int pivot_index = left;
int pivot = data[pivot_index];
int hold_left = left;
int hold_right = right;
left++;
while(right>=left)
{
while(left<=right &&data[left]<=pivot)
{
left++;
}
while(data[right]>=pivot && left<=right)
right--;
if(left <=right)
{
int tmp = data[left];
data[left] = data[right];
data[right] = tmp;
}
}
int tmp =data[pivot_index];
data[pivot_index] = data[right];
data[right]=tmp;
if(right >hold_left)
data = Quick_Sort(data,hold_left,right-1);
if(hold_right>right)
data= Quick_Sort(data,right+1,hold_right);
return data;
}
|
다른 정렬 알고리즘 공부하러 가기!!
2017/11/07 - [Study/알고리즘] - 07 정렬 알고리즘 - 힙 정렬 (Heap Sort)
2017/09/29 - [Study/알고리즘] - 06 정렬 알고리즘 - 기수 정렬(Radix Sort)
2017/09/25 - [Study/알고리즘] - 05 정렬 알고리즘 - 병합 정렬 (Merge Sort)
2017/09/17 - [Study/알고리즘] - 03 정렬 알고리즘 - 버블 정렬 (Bubble Sort)
2017/09/15 - [Study/알고리즘] - 02 정렬 알고리즘 - 삽입 정렬 (Insetion Sort)
2017/09/14 - [Study/알고리즘] - 01 정렬 알고리즘 - 선택 정렬(Selection Sort)
'Study > 알고리즘' 카테고리의 다른 글
| 06 정렬 알고리즘 - 기수 정렬(Radix Sort) (0) | 2017.09.29 |
|---|---|
| 05 정렬 알고리즘 - 병합 정렬 (Merge Sort) (0) | 2017.09.25 |
| 03 정렬 알고리즘 - 버블 정렬 (Bubble Sort) (0) | 2017.09.17 |
| 02 정렬 알고리즘 - 삽입 정렬 (Insetion Sort) (0) | 2017.09.15 |
| 01 정렬 알고리즘 - 선택 정렬(Selection Sort) (0) | 2017.09.14 |