퀵정렬

피벗을 정하고 좌 , 우측 포인터를 가리키며 기준값보다 작다면 왼쪽 , 보다 크다면 오른쪽으로 정렬하는 알고리즘

한번의 탐색이 완료되면 피벗으로 정한 값은 정렬이 완료된다.

 

이후 다시 피벗을 정한뒤 재귀 함수를 사용해 반복시킨뒤 더이상 정렬할 데이터가 없을때까지 반복한다.

평균적인 시간 복잡도는 O(nlogn) 이지만 최악의 상황엔 O(N²)가 된다.

 

또한 기존의 정렬 방식과는 달리 분할된 데이터들을 다시 함수로 다뤄줘야하므로 재귀에 대한 개념도 필요하다.

 

 

 

문제

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

풀이

int count = int.Parse(Console.ReadLine());

int[] arr = new int[count];

for (int i = 0; i < count; i++)
{
    arr[i] = int.Parse(Console.ReadLine());
}

QuickSort(arr,0,arr.Length-1);

foreach (var item in arr)
{
    System.Console.WriteLine(item);
}

int Partition(int[] arr, int p, int r)
{
    int pivot = arr[p];
    int left = p + 1;
    int right = r;

    while (true)
    {
        while (left <= r && arr[left] < pivot) left++;
        while (right > p && arr[right] > pivot) right--;

        if (left >= right) break;

        Swap(arr, left, right);
        left++;
        right--;
    }

    Swap(arr, p, right);
    return right;
}

void Swap(int[] arr, int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void QuickSort(int[] arr, int l, int r)
{
    if(l >= r)
        return;

    int pivot = Partition(arr,l,r);

    QuickSort(arr,l,pivot-1);
    QuickSort(arr,pivot+1,r);
}

 

미흡한부분이나 개선될 수 있는부분이 있다면 댓글 부탁드립니다.