1. 📖 재귀(recursion)
일단 알고리즘을 시작하기 전에 재귀라는 개념을 알고 있는 것이 좋습니다.
재귀(recursion)는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 말합니다.
재귀 함수는 결국 함수에서 함수 자신을 호출하는 것을 말하는겁니다.
가장 대표적인 코드 예시가 팩토리얼입니다.
1-1 🖥️ 팩토리얼!
public static void Main(string[] args)
{
string input;
int num1;
Console.Write("팩토리얼 구하기! 숫자를 입력하세요 : ");
input = Console.ReadLine();
num1 = int.Parse(input);
Console.WriteLine($"{num1}!은 {Factorial(num1)} 이다.");
}
static int Factorial(int n)
{
if (n == 0 || n == 1)
{
return 1;
}
return n * Factorial(n - 1); // 자기 자신을 참조해서 코드를 줄일 수 있습니다.
}팩토리얼 구하기! 숫자를 입력하세요 : 5
5!은 120 이다.재귀함수를 사용하면 코드로 표현하기 어려운 경우도 직관적으로 처리가 가능하며 복잡한 문제를 더 작은 하위문제를 해결할 수 있도록 만들 수 있습니다.
2. 📖 정렬 알고리즘
2-1 🔖 선택정렬
데이터 중 가장 작은 값을 선택하여 앞으로 옮겨서 정렬하는 방식입니다.
시간복잡도 - O(n²)
공간복잡도 - O(1)
public static void SelectionSort(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
int minIndex = i;
for (int j = i + 1; j < array.Length; j++)
{
if (array[j] < array[minIndex])
minIndex = j;
}
swap(array, i, minIndex);
}
}
static void Main(string[] args)
{
Random rnd = new Random();
int count = 20;
int [] selectArray = new int[count];
for(int i = 0;i < count; i++)
{
int rend = rnd.Next(0, 100);
Console.WriteLine($"{rend,3}");
selectArray[i] = rend;
}
Console.WriteLine();
Console.WriteLine();
SelectionSort(selectArray);
Console.WriteLine("선택 정렬 결과 : ");
foreach(int value in selectArray)
{
Console.WriteLine($"{value, 3}");
}
Console.WriteLine();
}
public static void swap(int[] array ,int left, int right) // 서로 바꿔주는 함수
{
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}2-2 🔖 삽입정렬
데이터를 하나씩 꺼내어 정렬된 자료 중 적합한 위치에 삽입하여 정렬하는 방식입니다.
예를 들어 4 3 5가 있다고 했을 때 먼저 4을 꺼내서 3과 5을 사이에 삽입하여 배치해서 3 4 5 를 만드는 식으로 숫자를 배치하는 정렬방식이라고 생각하시면 됩니다.
시간복잡도 - O(n²)
공간복잡도 - O(1)
public static void InsertionSort(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
for (int j = i; j > 0; j--)
{
if (array [j-1]> array[j])
{
Swap(array, j - 1, j);
}
else
{
break;
}
}
}
}2-3 🔖 버블정렬
서로 인접한 데이터를 비교하여 정렬하는 방식인데 서로 붙어있는 데이터 2개를 비교하여 앞에 수가 더 크다면 뒤집에서 정렬합니다.
시간복잡도 - O(n²)
공간복잡도 - O(1)
public static void BubbleSort(int[] array)
{
for (int i = 1; i < array.Length; i++)
{
for (int j = 0; j < array.Length; j++)
{
if (array[j] > array[j + 1])
{
Swap(array, j, j + 1);
}
}
}
}2-4 🔖 병합정렬
데이터를 2분할하여 정렬 후 병합하는 정렬방식입니다.
분할해서 정렬되기 때문에 시간복잡도가 O(nlogn)로 나옵니다.
하지만 공간을 추가해야하기 때문에 메모리를 많이 먹는 단점이 있어 공간복잡도가 O(n)입니다.
시간복잡도 - O(nlogn)
공간복잡도 - O(n)
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);
}
private 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++]);
}
else
{
sortedList.Add(array[rightIndex++]);
}
}
if (leftIndex <= mid)
{
while (leftIndex <= mid)
{
sortedList.Add(array[leftIndex++]);
}
}
else // if (rightIndex <= end)
{
while (rightIndex <= mid)
{
sortedList.Add(array[rightIndex++]);
}
}
for (int i = 0; i < sortedList.Count; i++)
{
array[start + i] = sortedList[i];
}
}2-5 🔖 퀵정렬
일단 먼저 퀵정렬은 일단 다른 정렬에 비해 이해하기 상당히 어려울 수도 있습니다.
하나의 피벗을 기준으로 작은값과 큰값을 2분할하여 정렬하는 방식입니다.
여기서 피벗을 기준점이라고 생각하면 더 이해하기 쉬울 것 같네요.
피벗을 기준으로 왼쪽은 큰 수를 만날 때까지 이동하고 오른쪽은 작은 수를 만날 때까지 진행한 후 서로 교체하면 자연스럽게 왼쪽에 작은 수 오른쪽에 큰 수가 이동하는 방식으로 정렬합니다.
진행하다보면 무조건 왼쪽과 오른쪽이 교차하는 경우가 생깁니다. 이 때 피벗과 오른쪽이 교체를 하고 피벗을 기준으로 분할하여 앞에서 했던 방식으로 정렬하는 식으로 진행됩니다.
시간복잡도 - 평균 : O(nlogn), 최악 : O(n²)
공간복잡도 - O(1)
병합정렬과 마찬가지로 분할해서 정렬되기 때문에 시간복잡도가 O(nlogn)로 나옵니다.
하지만 최악의 경우는 어떤 경우일까요?
8 1 2 3 4 5 6 7 9
이 경우 8이 피벗으로 되는데 7,8이 변경이 되고 그러면 이렇게 나누어집니다.
7 1 2 3 4 5 6 | 8 9
여기서 또 정렬을 하면
6 1 2 3 4 5 | 7 8 9
이런 식으로 상당히 비효율적으로 정렬되는 경우가 간혹 있습니다.
이때 시간복잡도가 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[left] <= array[pivot] && left < right)
{
left++;
}
while (array[right] > array[pivot] && 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);
}2-6 🔖 힙정렬
자료구조 중에 힙이라는 자료구조를 이용하여 정렬하는 방식입니다.
힙을 이용하여 우선순위가 가장 높은 요소가 가장 마지막 요소와 교체된 후 제거되는 방법을 이용합니다.
시간복잡도 - O(nlogn)
공간복잡도 - O(1)
시간복잡도와 공간복잡도가 좋아서 완벽한 정렬방식으로 보일 수는 있습니다.
힙정렬의 문제는 배열에서 연속적인 데이터를 사용하지 않기 때문에
캐시 메모리를 효율적으로 사용할 수 없어 오히려 다른 정렬 방식보다 느립니다.
public static void HeapSort(int[] array)
{
MakeHeap(array);
for (int i = array.Length - 1; i > 0; i--)
{
Swap(array, 0, i);
Heapify(array, 0, i);
}
}
private static void MakeHeap(int[] array)
{
for (int i = array.Length / 2 - 1; i >= 0; i--)
{
Heapify(array, i, array.Length);
}
}
private static void Heapify(int[] array, int index, int size)
{
int left = index * 2 + 1;
int right = index * 2 + 2;
int max = index;
if (left < size && array[left] > array[max])
{
max = left;
}
if (right < size && array[right] > array[max])
{
max = right;
}
if (max != index)
{
Swap(array, index, max);
Heapify(array, max, size);
}
}2-7 🔖 정렬 알고리즘 비교
2-8 🔖 인트로 정렬
앞에서 배운 정렬들을 봤을 때 상황에 따라 다른 정렬을 사용해야겠다는 것은 알겠는데 이것을 일일히 상황에 따라 판단하는 것은 쉽지 않을 수 있습니다.
그래서 C#에서는 인트로 정렬이라는 정렬 방식을 채택하고 있습니다.
인트로 정렬은 상황에 따라 퀵정렬, 힙 정렬, 삽입정렬을 번갈아가면서 정렬하는 하이브리드 방식의 정렬 방식입니다.
인트로 정렬은 보통은 퀵 정렬을 기반으로 사용하고 있지만 상황에 따라서 힙정렬이나 삽입정렬로 변경해서 사용합니다.
이로 인해 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있는 단점이 있는 퀵 정렬에 비해
인트로 정렬은 항상 O(nlogn)의 시간 복잡도를 가집니다.
정렬을 바꾸는 기준을 살펴보겠습니다.
삽입 정렬을 사용하는 경우작은 배열에서는 빠르고 캐시 효율성이 좋기 때문에 정렬할 부분
배열의 크기가 16개 이하로 작아진다면 삽입 정렬을 사용합니다.
힙 정렬로 사용하는 경우
재귀 깊이가 임계값을 초과하면 힙 정렬로 전환하는데 힙 정렬은 최악의 경우에도 O(nlogn) 시간 복잡도를 가지기 때문입니다.
2-9 🔖 안정정렬 vs 불안정정렬
2-9-1 ✔️ 안정정렬
동일한 값의 원소들이 원래의 순서를 유지하는 정렬 방식입니다.
예를 든다면 1 1 9 3 7 6 3 이 있다면 여기서 1과 3은 같은 수입니다.
동일한 값의 원소들의 순서가 맨 앞에 있는 1과 3은 정렬을 거친 후에도 맨 앞에 있고 뒤에 있던 1과 3은 정렬 후에도 뒤에 배치됩니다.
즉 입력된 순서대로 유지되는 것이죠.
대표적으로 삽입정렬, 병합정렬, 버블정렬이 있습니다.
변경이 되지 않으니 데이터 일관성을 유지해야 하는 경우 사용됩니다.
즉, DB에서 중복된 레코드를 정렬할 때 원래의 입력 순서를 유지해야하는 경우에 사용되겠죠.
2-9-2 ✔️ 불안정정렬
불안정정렬은 안정정렬과 다르게 동일한 값의 원소가 정렬되면서 순서가 바뀌는 정렬방식을 말합니다.
대표적으로 퀵 정렬, 선택 정렬, 힙 정렬이 있습니다.
보통 불안정정렬이 안정정렬보다 빠른 경우가 많아서 순서에 영향을 받지 않는 데이터를 처리해야 한다면 불안정정렬을 사용해야 더 효율적이겠죠.
