Quick Sort (퀵 정렬)

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