<개인공부>/[Algorithm]

퀵 정렬 (Quick Sort) 이론과 코드

BlockDMask 2017. 10. 19. 03:51
반응형

안녕하세요. BlockDMask 입니다. 

오늘은 지난시간에 언급 한 대로 퀵 정렬, 퀵 소트(Quick Sort)에 대해 알아보겠습니다.

부족한 부분이나 이상한 부분이 있으면 댓글 부탁드리겠습니다.


0. 원리

  • Quick sort(퀵 소트)는 divide and conquer (분할 정복) 방식으로 정렬을 수행합니다.

  • Quick sort(퀵 소트)는 n 개의 데이터를 정렬할때, 평균적으로 O(nlogn) 번을 수행하고 최악의 경우 O(n^2) 번을 수행합니다.

  • 평균적으로 log 의 시간복잡도를 가지기 때문에 다른 정렬 알고리즘에 비해 속도가 빠르므로, 사용빈도가 높습니다. 

  • 과정
    : 리스트에서 임의의 원소를 고릅니다. 그것을 pivot이라 합니다. (일반적으로 가운데 원소를 고릅니다.)
    : pivot의 앞에는 pivot 보다 작은 원소들로, pivot의 뒤에는 pivot 보다 큰 원소들이 오도록 교환해 줍니다. (divided)
    : divided 된 두 개의 작은 리스트에 대해 Recursive 하게 위의 과정을 반복합니다.
    : Recursive의 종료조건은 리스트의 크기가 0 입니다.

<STEP 1>


  1. 배열의 전체 범위는 index = 0~6 (start~end) 까지 입니다.
  2. 가장 좌측에 있는 arr[start]를 pivot으로 설정합니다. (pivot은 index가 아닌 해당 값입니다.)
  3. pivot을 제외한 가장 왼쪽 부터 오른쪽으로(left) 가면서 pivot보다 큰 값이 있는지 찾습니다. (작은값을 위치하게 하기위해)
  4. 배열의 가장 우측에서 부터 왼쪽으로(right) 오면서 pivot보다 작은 값이 있는지 찾습니다. (큰값들이 위치하게 하기위해)


<STEP 2>


  1. left가 우측으로 쭉 쭉 가던중 arr[left]의 값이 pivot 보다 큰 값을 찾았다!! 대기.(right랑 스왑하기 위해)

  2. right가 왼쪽으로 쭉 쭉 오던중 arr[right]의 값이 pivot 보다 작은 값을 찾았다!! 대기.(left랑 스왑하기 위해)

  3. arr[left], arr[right] 값을 스왑해줍니다.


<STEP 3>


  1. 또다시 가던길 마저 가다가

  2. 스왑할 거리 생겨서 다시 스왑해줍니다.

  3. 언제까지 가냐? -> left가 right 보다 오른쪽으로 갈때 까지.



  1. 드디어 탐색을 다했군요!

  2. left가 right보다 오른쪽으로 가게 됬습니다. (엇갈림)

  3. left는 pivot 보다 큰놈을 찾을때 멈추고, right는 pivot 보다 작은놈을 찾았을때 멈추게 됩니다.

  4. 제가 설계한 코드는 pivot이 왼쪽에 있는 경우니까 right가 가리키는 (pivot보다 작은놈)과 pivot을 swap 해줍니다.


<STEP 4>


  1. right가 가리키는 놈과 pivot을 스왑한 결과입니다.

  2. 그결과 이전 pivot이었던 "5" 를 기준으로 왼쪽으로는 "5"보다 작은 수, 오른쪽으로는 "5" 보다 큰 수가 위치하게되었습니다.

  3. "5"의 위치는 이제 fixed되었으니, "5"를 제외한 왼쪽, 오른쪽으로 나누어 다시 퀵 소트를 진행해 줍니다.

  4. 왼쪽의 범위는 처음에서부터 fixed가 된 값 왼쪽까지. [start ~ right-1]

  5. 오른쪽의 범위는 fixed가 된 값 오른쪽 부터 맨 끝까지. [right+1 ~ end]

  • 이런식으로해서 나누어 집니다. 편의를 위해서 두단계를 건너 뛰고 
    맨마지막 recursive의 종료 조건을 확인하는 과정만 보여드리겠습니다. 
    더이상 쪼개지지 않을때. 즉, 한 칸으로 쪼개졌을때가 종료조건입니다.

  • 쪼개지고 -> 왼쪽 오른쪽 recursive -> pivot 이 위치 잡고 -> 쪼개지고 -> 왼쪽 오른쪽 recursive
    -> ; ; ;  -> . . . -> 쪼개졌는데 한칸이네? -> Okay 종료!

이런식으로 돌아가는 정렬입니다.


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
//quick_sort
 
#include<iostream>
using namespace std;
 
void swap(int *arr,int a, int b){
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}
 
void myQuickSort(int *arr, int start, int end){
    int pivot = arr[start];
    int left = start+1;
    int right = end;
 
    while(left <= right){
 
        while(arr[left] < pivot){ left++; } //pivot보다 작은 경우는 건너뛰고 크거나 같은경우 멈춤
        while(arr[right] > pivot) { right--; } //pivot보다 큰 경우는 건너뛰고 작거나 같은경우 멈춤
 
        if(left <= right){ swap(arr, left, right); }
    }
 
 
    if(start < end){  //1개로 쪼개질때 까지
        swap(arr, start, right);   //pivot값과 arr[right] 값 swap
 
        myQuickSort(arr, start, right-1);  //앞 부분
        myQuickSort(arr, right+1end);    //뒷 부분
    }
 
    return;
}
 
void outPut(int *arr, int len){
 
    for(int i=0; i<len ; i++){
        cout << "[" << arr[i] << "]";
    }
    cout << endl;
}
 
 
int main(void){
    int arr[7= {5,3,7,6,2,1,4};
    
    outPut(arr, 7);
 
    //0 ~ len-1 범위.
    myQuickSort(arr, 06);
 
    outPut(arr, 7);
 
    return 0;
}
cs


2. 출력 결과

z


다음시간에는 병합정렬(merge sort)에 대해 알아보겠습니다.


반응형