정렬 알고리즘 (Algorithm)
퀵 정렬 (Quick Sort)
- 대표적인 ‘분할 정복’ 알고리즘
- 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식
- 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.
- 피벗 값을 설정
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Cycle 1
기본
3 7 8 1 5 9 6 10 2 4 -> 3을 피벗으로 정한다
첫번째
3 2 8 1 5 9 6 10 7 4 -> 왼쪽에서는 3보다 큰 값을 찾는다 = 7
↑ ↑ -> 오른쪽에서는 3보다 작은 값을 찾는다 = 2
두번째
3 2 1 8 5 9 6 10 7 4
↑ ↑
세번째
1 2 3 8 5 9 6 10 7 4 -> 왼쪽값 8, 오른쪽 1 이 엇갈려있기 때문에 피벗값인 3과 1을 바꿔준다.
↑ ↑ -> 3 왼쪽 값은 3보다 작은 값, 오른쪽은 큰 값으로 정렬이 됨
1
2
3
4
5
6
7
8
Cycle 2
기본
1 2 3 8 5 9 6 10 7 4 -> 3을 기준으로 왼쪽 피벗 값은 1, 오른쪽 피벗 값은 8로 정한 뒤 정렬
첫번째
1 2 3 8 5 9 6 10 7 4 -> 정리할게 없기 때문에 그 자리 그대로 정렬된다.
↑
1
2
3
4
5
6
7
8
Cycle 3
기본
1 2 3 8 5 9 6 10 7 4 -> 1을 기준으로 왼쪽 피벗 값은 없고, 오른쪽 피벗 값은 2로 정한 뒤 정렬
첫번째
1 2 3 8 5 9 6 10 7 4 -> 정리할게 없기 때문에 그 자리 그대로 정렬된다.
↑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Cycle 4
기본
1 2 3 8 5 9 6 10 7 4 -> 1, 2, 3이 정렬된 상태이고 8을 피벗으로 정한다
첫번째
1 2 3 8 5 4 6 10 7 9 -> 왼쪽에서는 8보다 큰 값을 찾는다 = 9
↑ ↑ -> 오른쪽에서는 8보다 작은 값을 찾는다 = 4
두번째
1 2 3 8 5 4 6 7 10 9 -> 왼쪽에서는 8보다 큰 값을 찾는다 = 10
↑ ↑ -> 오른쪽에서는 8보다 작은 값을 찾는다 = 7
세번째
1 2 3 7 5 4 6 8 10 9 -> 왼쪽값 10, 오른쪽 7 이 엇갈려있기 때문에 피벗값인 8과 7을 바꿔준다.
↑ ↑ -> 8 정렬 완료
·
·
·
마지막
1 2 3 4 5 6 7 8 9 10 으로 정렬된다.
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
41
42
43
44
45
46
47
48
49
50
51
52
53
퀵 정렬 공식
int number = 10;
int data[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
void quickSort(int * data, int start, int end)
{
if(start >= end)
{ // 원소가 1개인 경우
return;
}
int key = start; // 키는 첫번째 원소
int i = start + 1;
int j = end;
int temp;
while(i <= j)
{ // 엇갈릴 때까지 반복
while(data[i] <= data[key]) // 키 값보다 큰 값
{
i++;
}
while(data[j] >= data[key] && j > start) // 키 값보다 작은 값
{
j--;
}
if(i > j)
{ // 현재 엇갈린 상태면 키 값과 교체
temp = data[j];
data[j] = data[key];
data[key] = temp;
}
else
{
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
int main (void)
{
quickSort(data, 0, number - 1);
for(int 1 = 0; i < number; i++)
{
printf("%d ", data[i]);
}
}