[알고리즘/자료구조] 퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다.

1. 소스

/*    
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*    
/*    2018 - 11 - 09
/*
*/
 
 
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>
 
using namespace std;
 
 
int Data[10] = {9, 5, 12, 23, 4, 1, 18, 6, 3, 11};
 
void quickSort(int arr[], int left, int right) 
{
    int i = left, j = right;
    int pivot = arr[(left + right) / 2];
    int temp;
 
    cout << " Data Array is [ " ;
    for (int i = 0; i < 10; i++)
    {
        cout << Data[i] << " ";
    }
    cout << "]  The Pivot Value is : [ " << pivot << " ] "<< endl;
 
    do
    {
        while (arr[i] < pivot)
        {
            i++;
        }
 
        while (arr[j] > pivot)
        {
            j--;
        }
 
        if (i<= j)
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    } while (i<= j);
 
    if (left < j)
        quickSort(arr, left, j);
    if (i < right)
        quickSort(arr, i, right);
    
}
 
void main()
{
 
    int array_length = sizeof(Data) / sizeof(Data[0]);
 
    quickSort(Data, 0, 9);
 
 
    cout << " Data Array is [ " ;
    for (int i = 0; i < array_length; i++)
    {
        cout << Data[i] << " ";
    }
    cout << "] ";
    getch();
}

2. 결과화면

출처

위키백과 https://en.wikipedia.org/wiki/Quicksort