오늘 배운 내용

- 알고리즘

---

퀵 정렬

• 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한다.

• 파티션 크기가 16개 요소보다 작거나 같은 경우 : 삽입 정렬

• 파티션 수가 2 log n을 초과하는 경우 : 힙 정렬

• 위의 두가지 경우가 아닐경우 : 퀵 정렬

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        List<int> list = new List<int>();

        list.Add(7);
        list.Add(3);
        list.Add(9);
        list.Add(1);
        list.Add(5);
        list.Add(8);
        list.Add(2);
        
        Print(list);
        Console.WriteLine();
        
        QuickSort(list, 0, list.Count - 1);
        
        Print(list);
    }

    static void QuickSort(List<int> list, int left, int right)
    {
        if (left >= right) return;

        int pivot = Partition(list, left, right);
        
        QuickSort(list, left, pivot - 1);
        QuickSort(list, pivot + 1, right);
    }

    static void Print(List<int> list)
    {
        foreach (int i in list)
        {
            Console.Write($"[{i}]");
        }
    }

    static int Partition(List<int> list, int left, int right)
    {
        int pivot = list[right];
        int i = left - 1;
            
        // 리스트 내부에서 pivot보다 작은 값들을 왼쪽으로
        for (int j = left; j < right; j++)
        {
            if (list[j] < pivot)
            {
                i++;
                Swap(list, i, j);
            }
        }
        
        // pivot을 작은 값 바로 다음 영역으로 이동시키고 고정
        int pivotIndex = i + 1;
        Swap(list, pivotIndex, right);
        
        return pivotIndex;
    }

    static void Swap(List<int> list, int a, int b)
    {
        int temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }
}

병합 정렬

• 분할 정복 기법을 사용하는 정렬 알고리즘으로, 리스트를 반으로 나눈 후 재귀적으로 정렬된 부분 리스트를 병합하여 최종적으로 정렬을 수행한다.

class Program
{
    static void Main(string[] args)
    {
        List<int> list = new List<int>();
        
        list.Add(5);
        list.Add(2);
        list.Add(8);
        list.Add(3);
        list.Add(1);
        list.Add(6);
        list.Add(4);
        list.Add(7);

        PrintAll
        
        MergeSort(list, 0, list.Count - 1);

        PrintAll(list);
    }
    
    static void PrintAll(List<int> list)
    {
    }

    static void MergeSort(List<int> list, int left, int right)
    {
     	if (left >= right) return;
      	int center = (left + right) / 2;
    
     	MergeSort(list, left, center);
      	MergeSort(list, center + 1, right);
    
      	Merge(list, left, center, right);
    }

    static void Merge(List<int> list, int left, int center, int right)
    {
        // 임시 배열의 크기 = 현재 병합하는 범위의 길이
        int[] temp = new int[right - left + 1];
    
        int leftIndex  = left;
        int rightIndex = center + 1;
        int tempIndex = 0;              // temp에서 사용할 인덱스
    
        // 두 범위에서 남아있는 동안 계속 비교하고, 작은 값을 temp로 이동
        while (leftIndex <= center && rightIndex <= right)
        {
            // 불안정 정렬 [2a][1][2b][3] => [1][2b][2a][3]
            // 안정 정렬 [2a][1][2b][3] => [1][2a][2b][3]

            if (list[leftIndex] <= list[rightIndex]) // 왼쪽을 우선시 함
            {
                temp[tempIndex] = list[leftIndex];
                leftIndex++;
            }
            else
            {
                temp[tempIndex] = list[rightIndex];
                rightIndex++;
            }

            tempIndex++;
        }
            // 왼쪽 범위에 남은 값이 있다면? => 그대료 temp로
        while (leftIndex <= center)
        {
            temp[tempIndex] = list[leftIndex];
            leftIndex++;
            tempIndex++;
        }
            // 오른쪽 범위에 남은 값이 있다면? => 그대로 temp로
        while (rightIndex <= right)
        {
            temp[tempIndex] = list[rightIndex];
            rightIndex++;
            tempIndex++;
        }
            // temp배열의 원소만 기존의 list에 덮어쓰기
        for (int t = 0; t < temp.Length; t++)
        {
          list[left + t] = temp[t];
        }
    }
}