랭킹 시스템 정렬 알고리즘 변경

퀵 정렬

튜터님의 추천대로 랭킹 시스템의 정렬에 퀵 정렬 알고리즘을 적용했다.

private void QuickSort(List<RankingEntry> list, int low, int high)
{
    int partition = Partition(list, low, high);

    QuickSort(list, low, partition - 1);
    QuickSort(list, partition + 1, high);
}

private int Partition(List<RankingEntry> list, int low, int high)
{
    int pivot = list[high].Score;
    int left = low;
    int right = high - 1;

    while(left <= right)
    {
        while (list[left].Score > pivot)
            ++left;
        while (list[right].Score < pivot)
            --right;

        if(left <= right)
            Swap(list, left, right);
    }

    Swap(list, left, high);

    return left;
}

private void Swap(List<RankingEntry> list, int i, int j)
{
    RankingEntry temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

위 코드는 내가 랭킹 시스템에 사용한 퀵 정렬이다.

퀵 정렬 문제점

하지만 하나의 문제점을 찾았다.
바로 Pivot값과 같은 요소가 존재할 때 Partition함수의 While문을 벗어나지 못한다는 것이다.

중복 요소로 인한 불안정함은 퀵 정렬의 대표적인 문제이다.

물론 중간에 로직을 추가해서 중복요소에 대한 문제를 해결할 수 있지만, 시간, 능력 한계상 다른 알고리즘을 선택하기로 했다.

---

병합 정렬을 선택

병합 정렬은 정렬 대상을 잘게 나누어 각 부분 배열을 재귀적으로 정렬한 뒤에 다시 뭉탱이 배열끼리 병합하고 정렬하여 최종적으로 모든 부분을 정렬하는 알고리즘이다.

병합 정렬은 새로운 공간을 미리 마련해놔야 하는 작은 단점이 있지만, 안정적이고 퀵 정렬과 같은 성능을 보이는 정렬 방법이다.

private void MergeSort(List<RankingEntry> list)
{
    if (list.Count <= 1)
        return;

    int mid = list.Count / 2;
    List<RankingEntry> left = new List<RankingEntry>(list.GetRange(0, mid));
    List<RankingEntry> right = new List<RankingEntry>(list.GetRange(mid, list.Count - mid));

    MergeSort(left);
    MergeSort(right);

    Merge(list, left, right);
}

private void Merge(List<RankingEntry> list, List<RankingEntry> left, List<RankingEntry> right)
{
    int i = 0, j = 0, k = 0;

    while (i < left.Count && j < right.Count)
    {
        if (left[i].Score >= right[j].Score)
        {
            list[k++] = left[i++];
        }
        else
        {
            list[k++] = right[j++];
        }
    }

    while (i < left.Count)
    {
        list[k++] = left[i++];
    }

    while (j < right.Count)
    {
        list[k++] = right[j++];
    }
}

인터넷에 있는 예제들을 참고해서 프로젝트에 맞는 병합 정렬을 구현하였다.

중복되는 요소를 계속 넣어도 문제 없이 정렬해주는 것을 볼 수 있다.