[알고리즘] Sort 구현

개발자라면!! 종종 손코딩 면접을 보는 경우가 있습니다. 

가장 대표적으로 버블소트와 퀵소트가 있습니다. Swap 함수는 구현하지 않았습니다.^^

 

1. 버블소트

버블 소트는 인접한 두개의 값을 비교하여 오른쪽 값이 왼쪽 값보다 작다면 교환하는 방법입니다.

void bubleSort(ref int[] array)
{
    for(int i=0; i < array.Length; i++)
    {
        //(i+1) 을 빼주는 이유는 한번의 loop(i 기준) 가 완료될때 마다 가장 오른쪽 (가장 큰 값)은 정렬이 되기 때문입니다.
        for(int j = 0; j < (array.Length - (i+1)); j++)
        {
            if(array[j] > array[j+1])
            {
                Swap(ref array, j, j+1);
            }
        }
    }
}

 

2. 퀵소트

퀵소트는 임의의 Pivot (비교 기준) 을 정하고 데이터의 가장 왼쪽과 오른쪽부터 비교하면서 왼쪽값이 Pivot 값 보다 크고 오른쪽 값이 Pivot 보다 작다면 그 두 값을 교환하는 방법입니다.

교환을 한 후 Pivot 값을 중심으로 좌측, 그리고 우측을 재귀로 호출하면 됩니다.

wikipedia 에 잘 표현한 그림이 있어  첨부하였습니다.

(출처 : 위키페디아 https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC )

void quickSort(ref int[] array, int left, int right)
{
    int l_hold, r_hold, pivot;
    l_hold = left;
    r_hold = right;


    // 기준 값은 가운데 값으로 설정합니다.
    pivot = array[(left + right) / 2];


    while(left < right)
    {
        while (array[left] < pivot) left++;
        while (array[right] > pivot) right--;


        if(left <= right)
        {
            Swap(ref array, left, right);
            left++;
            right--;


            this.printArray(array);
        }
    }


    if (l_hold < right) quickSort(ref array, l_hold, right);
    if (r_hold > left) quickSort(ref array, left, r_hold);
}

 

이상 대표적인 두가지 정렬 방법인 버블소트와 퀵소트에 대하여 소스를 정리하였습니다.

물론 이 방법이외에도 구현하는 방법은 많이 있으니 참고 하시면 좋을 것 같습니다.