C#_12 Algorithm, Sort

SeonggyuMin·2025년 4월 2일

CSharp

목록 보기
10/12

1. 알고리즘

1. 알고리즘(Algorithm)

알고리즘(Algorithm)이란 문제를 해결하기 위해 정해진 진행절차나 방법이다. 이는 컴퓨터에서 알고리즘은 어떠한 행동을 하기 위해서 만들어진 프로그램명령어의 집합이다.

<알고리즘 조건>
1. 입력 : 알고리즘은 0개 이상의 입력을 가져야 함
2. 출력 : 알고리즘은 최소 1개 이상의 결과를 가져야 함
3. 명확성 : 수행 과정은 모호하지 않고 정확한 수단을 제공해야 함
4. 유한성 : 수행 과정은 무한하지 않고 유한한 작업 이후에 정지해야 함
5. 효과성 : 모든 과정은 명백하게 실행 가능해야 함

알고리즘을 설계하기 위해서는 보통 문제 이해 -> 예시와 테스트 케이스 작성 -> 알고리즘 설계 -> 알고리즘 구현 및 검증 -> 알고리즘 분석과 개선의 과정을 거친다.

알고리즘 설계 단계에서 슈도 코드(의사 코드) 및 플로우차트 등을 활용하여 먼저 흐름을 파악하는 것이 좋다. 또한 알고리즘을 설계할 때는 알고리즘의 정확성과 이를 검증할 검증 방법을 최우선으로 고려해야 한다.

2. 재귀(recursion)

재귀함수의 조건
1. 함수 내용 중 자기 가진 함수를 다시 호출해야 한다.
2. 종료 조건이 있어야 한다.

public class Folder
{
    public List<Folder> children;
}

public static void RemoveFolder(Folder folder)
{
    foreach (Folder child in folder.children)
    {
        RemoveFolder(child);
    }
}
int Factorial(int x)
{
    if (x == 1)
        return 1;
    else
        return x * Factorial(x - 1);
}

위 예시와 같이 자기 자신 함수를 다시 호출하며 동시에 종료 조건을 가지고 있다.
만약 종료 조건이 없을 시 스택 오버플로우(Stack Overflow) 현상이 나타난다.

재귀의 장점
1. 코드로 표현하기 어려운 경우도 직관적이게 처리가 가능
2. 분할정복 (Divide and Conquer)(큰 문제를 해결하기 위해 더 이상 쪼갤 수 없는 정도의 작은 문제로 만든 후 합치는 것)을 통한 반절 계산이 가능해서 효율이 높아지게(O=log(n))(O = log (n)) 구현이 가능하다.

또한 재귀로만 표현할 수 있는 것들이 있기도 하며 재귀가 효율적일 때가 있다.(병합 정렬 같은 경우)

재귀 단점
1. 재귀를 생각해내기 어려움

또한 오히려 재귀가 비효율적일 때도 있다. 특히 피보나치 수열 (Fibonacci Sequence)에서는 재귀를 쓰는 것이 최악의 경우가 된다.

2. 정렬 알고리즘(Sorting Algorithm)

1. 선택 정렬(Selection sort)

선택 정렬은 데이터 중 가장 작은 값부터 하나씩 선택하여 정렬하는 것이다.
시간복잡도 - O(n2)O(n^2)
공간복잡도 - O(1)O(1)
안정정렬 - XX

public static void SelectionSort(int[] array)
{
    for (처음부터 끝까지 쭉 훑기)
    {
        가장 낮은 수 찾기;
        
        앞에 교체해주기
    }    

}

public static void Swap(int[] array, in left, int right)
{

}

의사코드의 예시

 public static void SelectionSort(int[] array)
 {
     for (int i = 0; i < array.Length; i++)
     {
         int minIndex = i;
         for (int j = i; j < array.Length; j++)
         {
             if (array[j] < array[minIndex])
                 minIndex = j;
         }
         Swap(array, i, minIndex);
     }
 }

 public static void Swap(int[] array, int left, int right)
 {
     int temp = array[left];
     array[left] = array[right];
     array[right] = temp;
 }

 static void Main(string[] args)
 {
     Random random = new Random();
     int count = 20;

     int[] selectArray = new int[count];

     Console.WriteLine("랜덤 데이터: ");
     for (int i = 0; i < count; i++)
     {
         int rand = random.Next(0, 100);
         Console.Write($"{rand,3}");

         selectArray[i] = rand;
     }
     Console.WriteLine();
     Console.WriteLine();

     SelectionSort(selectArray);
     Console.WriteLine("선택 정렬 결과 : ");
     foreach (int value in selectArray)
     {
         Console.Write($"{value,3}");
     }
     Console.WriteLine();
 }

2. 삽입정렬(Insertion sort)

삽입 정렬은 데이터를 하나씩 꺼내어 정렬된 자료 중 적합한 위치에 삽입하여 정렬하는 것이다. 또한 삽입정렬은 인간에게 시켰을 때 무의식적으로 하는 것으로 유명하다.

시간복잡도 - O(n²)O(n²)
공간복잡도 - O(1)O(1)
안정정렬 - OO

public static void InsertionSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (array[j - 1] > array[j])
            {
                Swap(array, j - 1, j);
            }
            else
            {
                break;
            }
        }
    }
}

3. 버블 정렬(Bubble sort)

버블 정렬은 서로 인접한 데이터를 비교하여 정렬하는 것이다. 큰 것들이 거품처럼 올라온다고 해서 버블정렬이라고한다.
키 순으로 설 때 옆 사람과 비교해서 크면 뒤로 가는 방식, 구현하기 쉬운 방식이기도 하다.

public static void BubbleSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        for (int j = 0; j < array.Length - i; j++)
        {
            if (array[j] > array[j + 1])
            {
                Swap(array, j, j + 1);
            }
        }
    }
}

시간복잡도 - O(n²)O(n²)
공간복잡도 - O(1)O(1)
안정정렬 - OO

4. 병합정렬(Insertion sort)

병합정렬이란 데이터를 2분할하여 정렬 후 합병하는 것이다. 데이터 갯수만큼의 추가적인 메모리가 필요하다.

public static void MergeSort(int[] array) => MergeSort(array, 0, array.Length - 1);
public static void MergeSort(int[] array, int start, int end)
{
    if (start == end)
        return;

    int mid = (start + end) / 2;
    MergeSort(array, start, mid);
    MergeSort(array, mid + 1, end);
    Merge(array, start, mid, end);
}

public static void Merge(int[] array, int start, int mid, int end)
{
    List<int> sortedList = new List<int>();
    int leftIndex = start;
    int rightIndex = mid + 1;

    while (leftIndex <= mid && rightIndex <= end)
    {
        if (array[leftIndex] < array[rightIndex])
        {
            sortedList.Add(array[leftIndex]);
            leftIndex++;
        }
        else
        {
            sortedList.Add(array[rightIndex]);
            rightIndex++;
        }
    }

    if (leftIndex <= mid)
    {
        while (leftIndex <= mid)
        {
            sortedList.Add(array[leftIndex]);
            leftIndex++;
        }
    }
    else // if (rightIndex <= end)
    {
        while (rightIndex <= end)
        {
            sortedList.Add(array[rightIndex]);
            rightIndex++;
        }
    }

    for (int i = 0; i < sortedList.Count; i++)
    {
        array[start + i] = sortedList[i];
    }
}

시간복잡도 - O(nlogn)O(n log n)
공간복잡도 - O(n)O(n)
안정정렬 - OO

버블 정렬 vs 병합 정렬 실행 시간 비교 (단위: tick)

데이터 개수버블 정렬 (tick)병합 정렬 (tick)
500개8,300 tick3,290 tick
1,000개20,000 tick4,700 tick
2,000개80,000 tick7,600 tick
4,000개320,000 tick12,350 tick
8,000개12,600,000 tick20,000 tick

버블은 O(n2)O(n^2)의 시간 복잡도를 가지고 있고 병합은 O(nlogn)O(n log n)의 시간복잡도를 가지고 있기에 상승 폭의 양상이 차이가 심해진다.

5. 퀵 정렬(Quick Sort)

퀵 정렬은 하나의 피벗을 기준으로 작은값과 큰값을 2분할하여 정렬하는 것이다.
최악의 경우(피벗이 최소값 또는 최대값)인 경우 시간복잡도가 O(n²)O(n²)이 된다.

public static void QuickSort(int[] array) => QuickSort(array, 0, array.Length - 1);
public static void QuickSort(int[] array, int start, int end)
{
    if (start >= end)
        return;

    int pivot = start;
    int left = pivot + 1;
    int right = end;

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

        if (left < right)
        {
            Swap(array, left, right);
        }
        else
        {
            Swap(array, pivot, right);
            break;
        }
    }

    QuickSort(array, start, right - 1);
    QuickSort(array, right + 1, end);
}

시간복잡도 - 평균 : O(nlogn)O(nlogn) 최악 : O(n2)O(n^2)
공간복잡도 - O(1)O(1)
안정정렬 - XX

퀵정렬의 경우 이미 정렬된 배열에 대해 최악의 시간복잡도를 가지게 된다. 기준을 항상 첫 번째 혹은 마지막 요소로 잡으면 분할이 잘 되지 않아 일어나는 문제이다.

6. 힙 정렬 (Heap Sort)

힙 정렬은 힙을 이용하여 우선순위가 가장 높은 요소가 가장 마지막 요소와 교체된 후 제거되는 방법을 이용한는 것이다. 배열에서 연속적인 데이터를 사용하지 않기 때문에 캐시 메모리를 효율적으로 사용할 수 없어 상대적으로 느리다.

public static void HeapSort(IList<int> list)
	{
		MakeHeap(list);

		for (int i = list.Count - 1; i > 0; i--)
		{
			Swap(list, 0, i);
			Heapify(list, 0, i);
		}
	}

	private static void MakeHeap(IList<int> list)
	{
		for (int i = list.Count / 2 - 1; i >= 0; i--)
		{
			Heapify(list, i, list.Count);
		}
	}

	private static void Heapify(IList<int> list, int index, int size)
	{
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		int max = index;
		if (left < size && list[left] > list[max])
		{
			max = left;
		}
		if (right < size && list[right] > list[max])
		{
			max = right;
		}

		if (max != index)
		{
			Swap(list, index, max);
			Heapify(list, max, size);
		}
	}

시간복잡도 - O(nlogn)O(nlogn)
공간복잡도 - O(1)O(1)
안정정렬 - XX

힙 정렬은 이론상으론느 항상 O(nlogn)O(nlogn)의 성능을 유지하기에 안정적으로 보일 수 있으나 캐시 적중률때문에 실제 성능은 낮을 수 있다. 힙 정렬은 내부적으로 이진트리 형태를 배열 인덱스로 구현한 구조이기에 요소들이 메모리 상에서 비연속적으로 접근된다. 따라서 실제 성능은 퀵 정렬보다 낮은 경우가 많다.

7. 인트로 정렬(Intro Sort)

인트로 정렬이란 퀵 정렬 + 힙 정렬 + 삽입 정렬 세 개로 구현이 되어있는 하이브리드 정렬이다. 위 세 가지 정렬을 상황에 따라 유동적으로 바꿔 사용한다. 또한 위 세 가지 정렬은 불안정 정렬이다.

인트로 정렬을 사용하는 이유로는 퀵 정렬에서 평균 성능은 O(nlogn)O(n log n)이지만 최악의 경우 O(n²)** 성능까지 떨어질 수 있다. 따라서 이를 방지하기 위해 재귀 깊이가 임계치를 넘으면 힙 정렬로 전환한다.

메모

  • 안정 정렬(Stable Sort)
    안정 정렬이란 같은 값을 가진 요소들의 원래 순서를 정렬 후에도 유지하는 정렬 알고리즘이다.

  • 안정 정렬과 불안정 정렬
    파이썬 같은 대규모 데이터를 처리하는 언어들은 기본적으로 안정 정렬을 지원하지만 c#, c++, java 등은 하이브리드 정렬(불안정 정렬)을 기본적으로 지원한다. 보통 안정 정렬보다 불안정 정렬이 빠른 경향성이 있기 때문이다. 반대로 파이썬은 대규모 데이터 처리, 빅데이터 등 정렬 결과에서 원래 순서 유지가 중요한 경우가 많아 안정 정렬을 기본적으로 지원한다. 또한 파이썬의 높은 메모리 접근성과 데이터 모델 친화도 덕분에 메모리 사용량보다 정확성 및 안정성이 더 중요하게 평가되었다.

  • 만능 정렬 알고리즘은 없음
    삽입 정렬은 기본적으로 인덱스에 접근이 가능한 배열 기반만 사용이 가능하다. 그러나 연결리스트는 인덱스에 접근하지 못하기에 삽입정렬을 사용할 수 없다. 이럴 때 사용할 수 있는 것이 버블정렬이다. 버블 정렬은 인접한 요소들만 필요로 하기에 사용이 가능하다. 이러한 사례처럼 만능 정렬 알고리즘은 없고 상황에 따라 사용할 수 있어야 한다.

profile
SeonggyuMin
Hello~
이전 포스트

C#_11 Hashtable, Dictionary, Graph

다음 포스트

C#_13 Search Algorithm

0개의 댓글