[알고리즘] #5. 퀵정렬

1. 퀵정렬(Quick Sort) 알고리즘

• 분할 정복 알고리즘을 사용, 일정하지 않은 형태로 분할. 수행속도 빠름
  → 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 피봇(pivot)이라 부르는 배열 원소를 기준으로 피봇보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 위치하도록 분할.
  이 과정을 통해 분할된 왼쪽 배열과 오른쪽 배열에도 동일한 과정을 수행. 이를 반복하면 정렬되는 방식.
  → 주의 : 피봇은 분할된 왼편이나 오른편에 포함되지 않음.

1-1. 퀵정렬의 피봇 선정방법

• ① 랜덤하게 선정하는 방법
• ② 3개의 숫자의 중앙 값으로 선정하는 방법
  → 가장 왼쪽 숫자 / 중간숫자 / 가장 오른쪽숫자 중에서 중앙값으로 피봇을 정함
• ③ Median-of-Medians
  → 배열을 3등분 후, 각 부분에서 가장 왼쪽 숫자 / 중간 숫자 / 가장 오른쪽 숫자 중에서 중앙값을 찾은 후,
       세 중앙값들 중에서 중앙값으로 피봇을 정함

③ Median-of-Medians

 

 

 

2. 퀵정렬 알고리즘의 구현

# include <stdio.h>
# define LEN 7
 
void quickSort(int arr[], int L, int R) {
      int left = L, right = R;
      int pivot = arr[(L + R) / 2];    // pivot 설정 (가운데) 
      int temp;
      do
      {
        while (arr[left] < pivot)    // left가 pivot보다 큰 값을 만나거나 pivot을 만날 때까지 
            left++;
        while (arr[right] > pivot)    // right가 pivot보다 작은 값을 만나거나 pivot을 만날 때까지 
            right--;
        if (left<= right)    // left가 right보다 왼쪽에 있다면 교환 
        {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            /*left 오른쪽으로 한칸, right 왼쪽으로 한칸 이동*/
            left++;
            right--;
        }
      } while (left<= right);    // left가 right 보다 오른쪽에 있을 때까지 반복 
 
    /* recursion */
    if (L < right)
        quickSort(arr, L, right);    // 왼쪽 배열 재귀적으로 반복 
 
    if (left < R)
        quickSort(arr, left, R);    // 오른쪽 배열 재귀적으로 반복 
}
 
int main(){
  int i;
  int arr[LEN] = {5,1,6,3,4,2,7};
  printf("정렬 전 : ");
  for(i=0; i<LEN; i++){
    printf("%d ", arr[i]);
  }
  printf("\n");
    
  quickSort(arr, 0, LEN-1);
  
  printf("정렬 후 : ");
  for(i=0; i<LEN; i++){
    printf("%d ", arr[i]);
  }
  
  return 0; 
}

 

 

3. 퀵정렬 알고리즘의 특징

3-1. 장점

• 커다란 크기의 입력에 대해서 가장 좋은 성능
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음

3-2. 단점

• 불안정 정렬이다.
• 정렬된 배열에 대해서는 퀵정렬의 불균형 분할에 의해 수행시간이 오히려 더 많이 걸림

 

 

참고) https://bblackscene21.tistory.com/9

[ 알고리즘 공부 ] 퀵정렬 퀵소트(Quick Sort) - 분할 정복 알고리즘(feat. python 파이썬)

참고) https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

퀵 정렬(Quick Sort) | 👨🏻‍💻 Tech Interview