Notice
Recent Posts
Recent Comments
Tags
more
Today
Total
«   2025/07   »
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
관리 메뉴

SW 꿈나무

Quick Sort (퀵 정렬) 본문

Computer Science/Algorithm

Quick Sort (퀵 정렬)

현식 :) 2020. 4. 1. 23:15

Quick Sort (퀵 정렬)

  • 분할 정복 알고리즘으로 인덱스를 분할(Devide) 후, 정복(Conquer)과 결합(Combine)하는 정렬

  • 피벗을 정한 후, 피벗과의 대소비교로 좌, 우를 정렬하고 각 좌, 우 정렬에 대해서도 반복하는 정렬

  • 장점 : 빠르다. 평균적으로 Merge Sort 보다 빠르다.

  • 단점 : 피벗 선택에 따라 시간복잡도가 바뀔 수 있다.

                같은 수를 비교할 경우, 위치 이동이 일어날 수 있다.
  • 시간복잡도 : Best T(n) = n log_2 n

                             Worst T(n) = n^2
  • 동작 순서

    1. 피벗을 선택한다.
    2. 피벗과 각 인덱스 대소비교 후, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킨다.
    3. 피벗을 제 위치로 이동시킨다.
    4. 나눈 배열의 사이즈가 1이 될 때까지 피벗 좌, 우 측 배열에 대해 반복한다.
  • Code

    #include <stdio.h>                                            // 헤더파일 선언
    #define ARRAY_SIZE 10                                         // ARRAY_SIZE 10으로 선언
    
    void swap(int* a, int* b);                                    // swap function 선언
    int partition(int array[], int left, int right);              // partition function 선언
    void quick_sort(int array[], int left, int right);            // quick_sort function 선언
    // main function----------------------------------------------
    void main()
    {
        int Arr[ARRAY_SIZE] = {2, 8, 9, 4, 5, 7, 1, 0, 3, 6};     // 임의의 배열 선언 및 초기화
        quick_sort(Arr, 0, ARRAY_SIZE-1);                         // quick_sort function 호출
        for(int i=0;i<ARRAY_SIZE;i++)                             // ARRAY_SIZE 만큼 반복
        {
            printf("%d",Arr[i]);                                  // Arr의 각 원소들 출력 (정렬된 배열 출력)
        }
    }
    
    void swap(int* a, int* b)                                     // swap function (정수형 포인터, 정수형 포인터)
    {
        int temp = *a;                                            // 정수형 변수 temp 선언 및 *a의 주소값 대입
        *a = *b;                                                  // *a에 *b의 주소값 대임
        *b = temp;                                                // *b에 temp 값 대입
    }
    
    void quick_sort(int array[], int left, int right)             // quick_sort function. (배열, 시작 인덱스, 끝 인덱스)
    {
        if(left<right)                                            // 시작 인덱스보다 끝 인덱스가 작으면
        {
            int pivot = partition(array, left, right);            // 정수형 변수 p 선언 및 partition 함수 호출 값 대입
    
            if(left<pivot-1)                                      // 시작 인덱스가 pivot-1 보다 작으면
            quick_sort(array, left, pivot-1);                     // quick_sort 호출 (배열, 시작 인덱스, 피벗-1)
            if(pivot+1<right)                                     // pivot+1 이 끝 인덱스보다 작으면
            quick_sort(array, pivot+1, right);                    // quick_sort 호출 (배열, 피벗+1, 끝 인덱스)
        }
    
    }
    
    int partition(int array[], int left, int right)               // partition function. (배열, 시작 인덱스, 끝 인덱스)
    {
        int pivot = array[right];                                 // 정수형 변수 pivot 선언 및 배열의 끝 인덱스 값 대입.
                                                                  // 배열의 마지막 인덱스의 값을 피벗으로 선언.
        //int temp;                                                  // swap 함수 대입 전 swap을 위한 임시 변수로 사용.
        for(int i=left; i<right; i++)                             // 시작 인덱스부터 끝 인덱스 수만큼 반복  
        {  
            if(array\[i\]<=pivot)                                 // i번째 인덱스의 값이 피벗 값보다 작으면  
            {  
                //temp = array\[i\];  
                //array\[i\] = array\[left\];  
                //array\[left\] = temp;                           // swap  
                swap(&array\[i\],&array\[left\]);                 // i번째 인덱스의 값과 시작 인덱스 교환  
                left++;                                           // 시작 인덱스++  
            }                                      // 피벗보다 작은 값을 0번째, 1번째, 2번째... 에 저장시키기 위해 left++ 사용.  
        }  
        //temp = array\[right\];  
        //array\[right\] = array\[left\];  
        //array\[left\] = temp;                                   // swap  
        swap(&array\[left\],&array\[right\]);      // left 번째 인덱스 (피벗이 들어갈 위치)와 right 번째 인덱스(피벗) 교환  
        return (left);                                            // left 반환 (피벗의 위치)
    }
    Output : 0 1 2 3 4 5 6 7 8 9

'Computer Science > Algorithm' 카테고리의 다른 글

Merge Sort (합병 정렬)  (0) 2020.03.31
Bubble Sort (거품 정렬)  (0) 2020.03.30
Insertion Sort (삽입 정렬)  (0) 2020.03.29
Selection Sort (선택 정렬)  (0) 2020.03.28
Comments