[알고리즘] 퀵정렬(Quick sort)

알고리즘

 

퀵정렬(Quick sort)

 

 

 

 

간단 요약

 

 

1. 임의의 값을 피벗(Pivot) 으로 정한다.

 

2. 피벗을 기준으로 하나씩 비교하여 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 정리한다.

 

3. 피벗을 기준으로 왼쪽 과 오른쪽의 배열을 비균등 분할을 한다.

 

4. 각각의 배열에서 순환 호출을 통해 더 이상 분할되지 않을 때 까지 반복

 

 

상세 설명

 

 

병합 정렬은 분할, 정복, 결합 세단계의 과정을 거쳐서 완성된다.

분할 : 피벗을 기준으로 비균등 분할

정복 : 각 배열의 크기가 더 이상 분할 할 수 없을 때 까지 순환 호출을 통해 분할을 반복한다.

결합 : 한회의 분할,정복이 끝날 때 마다 최소 하나이상의 피벗값이 생긴다.

-> 각 회마다 결정되는 피벗값의 위치는 정렬이 완성되었을때의 위치와 같기 때문에 각 피벗값을 한 배열에 결합

 

 

무작위로 정해진 배열을 오름차순으로 정렬해보자

 

 

우선 가장 왼쪽 값(20)을 피벗으로 정한후

왼쪽에서 부터 피벗보다 큰값을 찾는다.

오른쪽에서 부터 피벗보다 작은 값을 찾는다.

 

 

 

 

만약 left 의 인덱스가 right 보다 작다면 두 값의 자리를 바꾼다.

다시 이전 과정을 반복한다.

 

 

 

 

이번에도 40과 19의 자리를 바꿔준다.

 

 

 

 

 

지금 상황을 보면 왼쪽에서 하나씩 검사하던 left의 인덱스가 right의 인덱스 값보다

커진 것을 확인 할 수 있다. 이렇게 인덱스가 서로 엇갈렸을때, right 와 피벗 을 바꾼다.

이때, 피벗이였던 20은 정렬이 완성되었을 때의 위치가 된다.

이렇게 피벗값을 하나씩 Fix 시키면서 정렬을 하는것이다.

 

 

 

 

이 다음 부터는 순환 호출을 하면서 배열의 범위에서 이전 피벗값을 제외 시킨후 지금 까지의

과정을 반복한다.

 

 

 

 

시간복잡도

 

 

 

최악의 경우

 

퀵 정렬은 유일하게 Worst의 경우 n^2 의 시간복잡도가 나타난다. 이게 어떤 경우에 일어나는지 확인해 볼 필요가 있다.

 

예를 들어 arr = { 1, 2, 3, 4, 5, 6 } 처럼 이미 오름차순 정렬이 되어있는 배열이 있다고 가정하자.

그리고 피벗(Pivot) 값을 가장 왼쪽의 값으로 정했다면 이미 오른쪽 값들이 피벗보다 큰수이기 때문에 두개의 배열로 분할이 되지 않고, 피벗을 제외한 모든 수가 배열이 된다. 하지만 그 배열에서도 이 과정이 반복되고 결국 n번의 분할이 시행된다.

 

이런 상황을 보완하기 위해 배열값들의 중앙값을 찾아 균등 분할을 하는 병합정렬이 나왔다.

 

 

 

 

 

 

코드

 

#include <stdio.h>
#include <stdlib.h> //랜덤함수 호출
 
void Swap(int arr[], int a, int b) // a,b 스왑 함수 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (pivot >= arr[low] && low <= right) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
        while (pivot <= arr[high] && high >= (left+1) ) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            Swap(arr, low, high); //low와 high를 스왑 
        }
    }
    Swap(arr, left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
 
void QuickSort(int arr[], int left, int right)
{
    if (left <= right)
    {
        int pivot = Partition(arr, left, right); // 둘로 나누어서
        QuickSort(arr, left, pivot - 1); // 왼쪽 영역을 정렬한다.
        QuickSort(arr, pivot + 1, right); // 오른쪽 영역을 정렬한다.
    }
}
 
//메인함수
int main()
{
    int n,i;
    int arr[100];
 
    
    printf("몇개의 숫자로 정렬하시겠습니까?\n");
    scanf("%d",&n);
 
    for(i = 0 ; i < n ; i++)
         arr[i]=rand()%1000;
 
     printf("정렬전 배열 :");
     for(i = 0 ; i < n ; i++)
        printf("%d ", arr[i]);
     printf("\n");
 
    QuickSort(arr,0,n-1);
 
    printf("정렬후 배열 :");
    for(i = 0 ; i < n ; i++)
        printf("%d ", arr[i]);
    printf("\n");
 
    return 0;
}

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

출처 : https://terms.naver.com/entry.nhn?docId=2270437&cid=51173&categoryId=51173