[Algorithm] 퀵 정렬 QuickSort - C언어

분할 정복 알고리즘(Divide-and-Conquer)

• 합병정렬 MergeSort
• 퀵 정렬 QuickSort
• 선택 문제 Selection Problem

 

퀵 정렬(QuickSort)

1. 피봇(pivot)이라 일컫는 배열의 원소(숫자)를 기준
2. 피봇보다 작은 숫자들은 왼쪽, 큰 숫자들은 오른쪽으로 위치하도록 분할
3. 분할된 부분문제들에 대해서도 위와 동일한 과정으로 재귀적으로 수행

 

개념 설명

 

** 해당 설명에서 pivot은 무작위로 정해짐 **

 

pseudo code

QuickSort(A, left, right)
입력 : 배열A[left] ~ A[right]
출력 : 정렬된 배열A[left] ~ A[right]
if(left < right){
	피봇을 A[left] ~ A[right] 중에서 선택하고
	피봇을 A[left]와 자리를 바꾼 후
	A[p+1] ~ A[right]를 A[left]와 비교
	QuickSort(A, left, p-1) // 피봇보다 작은 그룹
	QuickSort(A, p+1, right) // 피봇보다 큰 그룹
}

 

시간복잡도

• 평균 시간복잡도 : O(nlogn)
• 최선 시간복잡도 : O(nlogn)
• 최악 시간복잡도 : O(n^2)

-> (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2)

 

피봇 선정 방법

• 전체를 다 비교해서 중간값 찾기
• 랜덤하게 선정 -> 배열 사이즈가 작을 때 Best
• 세 개의 숫자(가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자)의 중간값으로 선정하는 방법

-> 배열 사이즈가 클 때 Best

 

구현 - C언어

#include <stdio.h>
#define MAX_NUM 12

int Pivot(int arr[], int left, int right);
void PrintArr(int arr[]); // 배열 출력
void QuickSort(int arr[], int left, int right);
void Swap(int arr[], int x, int y); // 값 교환

int main(void) {
  int arr[MAX_NUM] = {6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14};
  printf("Befor Quick Sort : ");
  PrintArr(arr); // 배열 출력
  // QuickSort 수행
  // (배열, left: 배열의 시작, right: 배열의 끝)
  QuickSort(arr, 0, MAX_NUM - 1);
  printf("After Quick Sort : ");
  PrintArr(arr); // 배열 출력
  return 0;
}

void PrintArr(int arr[]){
  for (int i = 0; i < MAX_NUM; i++) {
    printf("[%d] %d ", i, arr[i]);
  }
  printf("\n");
}

void QuickSort(int arr[], int left, int right) {
  // 정렬할 범위가 2개 이상
  if(left < right){
    // pivot을 기준으로 분할 후 정렬
    int p_idx = Pivot(arr, left, right);
    
    printf("located pivot : [%d] %d \n", p_idx, arr[p_idx]);
    printf("process : ");
    PrintArr(arr);
    
    // left ~ pivot-1 인덱스 부분의 배열 정렬
    QuickSort(arr, left, p_idx-1); 
    // pivot+1 ~ right 인덱스 부분의 배열 정렬
    QuickSort(arr, p_idx+1, right);
  }
}

int Pivot(int arr[], int left, int right){
  int low = left;
  int hight = right;
  // 정렬할 배열의 가장 왼쪽 데이터를 pivot로 선택
  int pivot = arr[left];
  
  while(low < hight){
    // arr[low]의 값이 pivot보다 작으면 계속 증가
    while(low <= right && arr[low] < pivot){
      low++;
    }
    
    // arr[hight]의 값이 pivot보다 크면 계속 증가
    while(hight >= left && arr[hight] > pivot){
      hight--;
    }
    // 앞서 while에서 pivot과 비교하였을 때
    // arr[low]>pivot && arr[hight]<pivot일 경우
    if(low < hight){
      // arr[low]와 arr[hight]의 값 교환
      Swap(arr, low, hight);
    }
  }
  // arr의 인덱스인 low와 hight의 값이 같아지면
  // pivot(arr[left])과 
  // arr[hight](pivot이 있어야 위치)의 값을 교환
  Swap(arr, low, hight);
  // pivot의 위치
  return hight;
}

void Swap(int arr[], int x, int y){
  int tmp;
  tmp = arr[x];
  arr[x] = arr[y];
  arr[y] = tmp;
}

 

결과