[Algorithm] 퀵정렬 (빠르고 효율적인 정렬방법)

계속해서 o(n log n) 시간복잡도를 가지는 정렬방법에 대해 알아보겠습니다. 이번에는 퀵정렬입니다. 실무에서도 가장 많이쓰이고 속도와 효율성이 가장 좋다고도 할수있는 정렬 방식입니다.

 

퀵정렬 

이번에도 그림을 통해 설명해드리겠습니다.

 

 

☞ 먼저 PVIOT을 정합니다. 대부분 정렬속도를 위하여 가운데 숫자를 PIVOT으로 정하는게 효율적입니다.

 

☞ PVIOT값과 LEFT값을 비교하여 LEFT값이 PIVOT보다 크다면 PIVOT값과 RIGHT값을 비교합니다.

RIGHT값이 PIVOT보다 크다면 RIGHT커서를 왼쪽으로 이동시킨후 다시 PIVOT값과 비교합니다.

 

☞ RIGHT값이 PIVOT보다 작다면 LEFT값과 RIGHT값을 바꿉니다. 그런뒤 LEFT값을 오른쪽으로 한칸 옮깁니다.

 

☞ LEFT값과 RIGHT값이 만날때까지 무한반복합니다.

 

☞ LEFT커서와 RIGHT커서가 만나면 해당값과 PIVOT값을 비교합니다. PIVOT값이 크면 오른쪽에 위치시키고 PIVOT값보다 작으면 왼쪽에 위치시킵니다.

 

☞ 이전 PIVOT을 기준으로 이전PIVOT보다 작은값과 큰값으로 나누고 이전 PIVOT값보다 작은값을 기준으로 새로운 PIVOT을 설정합니다.

 

☞ 다시 앞에서 한 방식으로 PIVOT을 기준으로 LEFT값과 RIGHT값을 교환합니다.

 

☞ 정렬이 완료됩니다.

 

퀵정렬 소스 코드(C언어/C++)

#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 (low <= right && pivot >= arr[low]) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
        while (high >= (left+1)  && pivot <= arr[high]) // 피벗보다 작은 값을 찾는 과정 
        {
            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;
}

 

결과

 

[C언어] 버블정렬 (배열에 있는 정수값 오름차순 정렬하기)

[C언어] 선택정렬 (배열에 있는 정수값 내림차순 정렬하기)

[C언어] 삽입정렬 (배열에 있는 알파벳 차례대로 정렬하기)

[C언어] 병합정렬 (실무에서 많이쓰는 정렬방법)

[C언어] 여러가지 정렬 속도 비교(정렬의 시간복잡도