퀵 정렬 알고리즘

안녕하세요 박스여우입니다.

 

이번에는 정렬 알고리즘의 최강자 퀵 정렬에 대해서 알아보도록 하겠습니다.

 

위 영상은 퀵 정렬 알고리즘의 이해를 돕기위해 만들어진 영상입니다.

 

퀵 정렬은 기준키(피벗)을 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰값을 지니면 뒤로 보내서

작은값과 큰값을 분리해가는 방식의 알고리즘 입니다.

 

기준키를 left(제일 첫번째데이터)로 잡고, i값을 한개씩 증가시켜 기준키보다 큰값을 찾고,

j값(right)값을 1씩 캄소시켜 기준키보다 작은값을 찾은뒤 두 데이터의 위치를 교환합니다.

 

계속해서 같은방식으로 진행하다가 i값과 j값이 서로 교차하면, 작은 데이터를 기준키의 데이터와 교환합니다.

이렇게 되면, 기준키가 옮겨진 부분을 중심으로 앞쪽엔 작은값, 뒤쪽엔 큰값으로 나뉘게 되고,

앞쪽에서도 같은 방식으로 정렬이 될때까지 진행하고, 뒤쪽에서도 같은방식으로 진행하면 됩니다.

 

 

아래는 소스코드 입니다.

int partition(int array[], int min, int max)
{
    // define a pivot as the max item of the (sub)array
    int pivot = array[max] ;
    int i = min - 1 ;
    // loop through the elements of the (sub)array
    for (int j = min ; j < max ; j++)
    {
        // in case the element has a smaller value that the pivot
        // bring it in front of it (larger elements will come after it)
        if (array[j] <= pivot)
        {
            i++ ;
            int temp = array[i] ;
            array[i] = array[j] ;
            array[j] = temp ;
        }
    }
    // bring the pivot to its correct position
    int temp = array[i+1] ;
    array[i+1] = array[max] ;
    array[max] = temp ;
 
    return i+1 ;
}
 
void quickSort(int array[], int min, int max)
{
    if (min < max)
    {
        // partition the array in two parts
        int q = partition(array, min, max) ;
        // apply QuickSort recursively to both parts
        quickSort(array, min, q-1) ;
        quickSort(array, q+1, max) ;
    }
}

정렬 알고리즘은 데이터의 랜덤상태, 역정렬 등의 상황에 따라서 속도가 다르지만,

퀵정렬이 평균적으로 빠르다고 합니다(테스트 해본결과 버블-15초/퀵-2초)

 

 

http://ddeville.me/2010/10/sorting-algorithms-comparison/

위의 주소를 통해 정렬 알고리즘을 비교해볼수 있습니다.