반응형


퀵 정렬(Quick Sort)는 이름 그대로 빠른 정렬의 효과를 가지는 알고리즘이다.


퀵 정렬 만큼은 글로 푸는 설명보다 그림으로 보는 설명이 훨씬 쉽고 이해가 잘 된다.




[정렬 과정]


pivot이라는 기준을 잡아주고, pivot 바로 오른쪽에 low를 잡아준다. 그리고 그 정렬 구간의 가장 오른쪽을 high로 잡아준다.


low는 +1씩 증가하면서 pivot보다 큰 값이 나오면 그 자리에 멈춘다.


low가 멈춘 후, high는 -1씩 감소하면서 pivot보다 작은 값이 나오면 그 자리에 멈춘다.


low와 high가 서로 멈췄다면 low에 위치한 값과 high에 위치한 값을 바꿔준다.


이때 만약 low가 high를 지나쳐 간다면(low와 high위치가 같을때 까지는 괜찮다.) pivot과 high의 값을 바꿔준다.


pivot에 의해 high위치로 들어간 값은 지금부터 고정된다.


그리고 고정된 값을 기준으로 좌우의 배열을 또 정렬 구간으로 지정해준다.


나뉜 구간들을 가장 처음 내용 부터 반복해주면 된다.



[시간 복잡도]


시간 복잡도는 


T(n) = 2T(n/2) + n 에 의해 이고


최악의 경우( 5 4 3 2 1 순으로 역순 정렬 되어있을 때 )

의 복잡도를 가진다.



퀵 정렬의 동작 방식은 다음 그림과 같다.



















[소스 코드]


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
54
55
56
/*
    MAX를 4000으로 두고
    for (int i = 0; i < MAX; i++)
        arr[i] = i;
    를 할 때 재귀가 심하게 들어가게 되어 퀵소트가 터지게 된다.
    이때는 피벗을 (s + e) / 2로 잡게되면 해결 할 수 있는데
    꼬이게 된다.
    그런데 여기서 피벗을 mid로 잡게되면 퀵소트 중에 
    피벗위치와 다른 값들이 스왑이 될 수 있기 때문에 
    이 코드 내에서는 피벗을 mid로 두면 위험해진다.
*/
#include <iostream>
 
#define MAX 10
 
int arr[MAX] = { 2,1,3,4,7,5,6,9,8,};
 
void quickSort(int s, int e) {
    if (s < e) {
        int p = s;
        int l = s;
        int r = e;
 
        while (l <= r) {
            while (arr[p] >= arr[l] && l <= e)
                l++;
            while (arr[p] < arr[r])
                r--;
            if (l <= r) {
                int t = arr[l];
                arr[l] = arr[r];
                arr[r] = t;
            }
        }
 
        int t = arr[r];
        arr[r] = arr[p];
        arr[p] = t;
 
        quickSort(s, r - 1);
        quickSort(r + 1, e);
    }
}
 
int main() {
    printf("정렬 전 :: ");
    for (int i = 0; i < MAX; i++)
        printf("%d ", arr[i]);
    printf("\n");
    quickSort(0, MAX - 1);
    printf("정렬 후 :: ");
    for (int i = 0; i < MAX; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
cs




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
54
55
56
/*
    MAX를 4000으로 두고
    for (int i = 0; i < MAX; i++)
        arr[i] = i;
    를 할 때 재귀가 심하게 들어가게 되어 퀵소트가 터지게 된다.
    이때는 피벗을 (start + end) / 2로 잡게되면 해결 할 수 있는데
    꼬이게 된다.
    그런데 여기서 피벗을 mid로 잡게되면 퀵소트 중에 
    피벗위치와 다른 값들이 스왑이 될 수 있기 때문에 
    이 코드 내에서는 피벗을 mid로 두면 위험해진다.
*/
#include <iostream>
 
#define MAX 10
 
int arr[MAX] = { 2,1,3,4,7,5,6,9,8,2 };
 
void quickSort(int start, int end) {
    if (start < end) {
        int pivot = start;
        int low = start;
        int high = end;
 
        while (low <= high) {
            while (arr[pivot] >= arr[low] && low <= end)
                low++;
            while (arr[pivot] > arr[high])
                high--;
            if (low <= high) {
                int tmp = arr[low];
                arr[low] = arr[high];
                arr[high] = tmp;
            }
        }
 
        int tmp = arr[high];
        arr[high] = arr[pivot];
        arr[pivot] = tmp;
 
        quickSort(start, high - 1);
        quickSort(high + 1end);
    }
}
 
int main() {
    printf("정렬 전 :: ");
    for (int i = 0; i < MAX; i++)
        printf("%d ", arr[i]);
    printf("\n");
    quickSort(0, MAX - 1);
    printf("정렬 후 :: ");
    for (int i = 0; i < MAX; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
cs






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
54
55
#include <iostream>
#include <cstdio>
 
#define swap(a, b){char t = a; a = b; b = t;}
using namespace std;
 
int _strlen(char *input)
{
    int i = 0;
    while (input[i] != '\0')
        i++;
 
    return i;
}
void _qsort(char *input, int l, int r)
{
    if (l >= r)
        return;
 
    int i = l;
    int j = r;
    int pivot = input[l];
 
    while (i <= j)
    {
        while (input[i] < pivot)
            i++;
        while (input[j] > pivot)
            j--;
        if (i <= j)
        {
            swap(input[i], input[j]);
            i++;
            j--;
        }
    }
 
    if (l < j)
        _qsort(input, l, j);
    if (i < r)
        _qsort(input, i, r);
}
int main()
{
    char str[11= "asdcfkbqz";
 
    _qsort(str, 0, strlen(str) - 1);
 
    cout << str;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
 
 
void Swap(int arr[], int a, int b) // a,b 스왑 함수 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (pivot >= arr[low] && low <= right) // 피벗보다 큰 값을 찾는 과정 
        {
            low++// low를 오른쪽으로 이동 
        }
 
        while (pivot <= arr[high] && high >= (left+1) ) // 피벗보다 작은 값을 찾는 과정 
        {
            high--// high를 왼쪽으로 이동
        }
 
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            Swap(arr, low, high); //low와 high를 스왑 
        }
 
    }
    Swap(arr, left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
 
void QuickSort(int arr[], int left, int right)
{
    if (left <= right)
    {
        int pivot = Partition(arr, left, right); // 둘로 나누어서
        QuickSort(arr, left, pivot - 1); // 왼쪽 영역을 정렬한다.
        QuickSort(arr, pivot + 1, right); // 오른쪽 영역을 정렬한다.
    }
}
 
 
// 사용 예시
int main()
{
    int n,i;
    int arr[100];
  
     scanf("%d",&n);
 
     for(i = ; i < n ; i++)
          scanf("%d",&arr[i]);
 
    QuickSort(arr,0,n-1);
  
    for(i = ; i < n ; i++)
        printf("%d ", arr[i]);
 
    return 0;
}
                                                                        
Crocus



[결과 화면]



반응형