정렬 알고리즘
1) 선택 정렬
배열에서 최소값(또는 최대값)을 찾아 맨 앞(또는 맨 뒤)와 교환하는 방법
- 시간 복잡도: O(n^2)
- 공간 복잡도: O(1)
코드
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
for(int i = 0; i < arr.Length - 1; i++)
{
int minIndex = i; //첫번째 인덱스부터 기준을 잡고 확인
for (int j = i + 1; j < arr.Length; j++)
{ //기준 인덱스 뒤의 모든 숫자들 중 가장 최소값을 가진 인덱스 번호 찾기
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
//기준 인덱스보다 작은 값의 인덱스가 뒤에 있다면 서로 바꾸기(swap)
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
foreach(int num in arr)
{
Console.WriteLine(num);
}2) 삽입 정렬
정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법
- 시간 복잡도: 최악의 경우 O(n^2), 하지만 정렬되어 있는 경우에는 O(n)
- 공간 복잡도: O(1)
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
for (int i = 1; i < arr.Length; i++)
{
int j = i - 1;
int key = arr[i]; //비교 대상이 될 현재 key 값 저장
//비교 대상 인덱스 앞의 모든 숫자들과 key값 비교하여 key값보다 크면 우측으로 옮기기, 작으면 비교대상은 그대로 두고 key값은 그 우측에 두기
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
foreach (int num in arr)
{
Console.WriteLine(num);
}입력 자료가 정확하게 역순일 경우 매번 모든 왼쪽의 자료와 비교해야하므로 시간 복잡도가 최악의 상황이 됨. 제대로 정렬되어 있을 경우에는 전체 탐색만 한 번 하면 끝이므로 시간 복잡도 측면에서 최상의 결과를 보임.
3) 퀵 정렬
피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법
여기서 피벗은 임의로 정해진다. (아래 코드는 배열 가장 우측의 값을 pivot으로 정함)
- 시간 복잡도: 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n)
- 공간 복잡도: 평균적으로 O(log n), 최악의 경우 O(n) (재귀 호출에 필요한 스택 공간)
static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int Partition(int[] arr, int left, int right)
{
int pivot = arr[right];
int i = left - 1;
for(int j = left; j < right; j++)
{
if (arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, right);
return i + 1;
}
static void QuickSort(int[] arr, int left, int right)
{
if(left < right)
{
int pivot = Partition(arr, left, right);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
}
static void Main(string[] args)
{
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
QuickSort(arr, 0, arr.Length - 1);
foreach (int num in arr)
{
Console.WriteLine(num);
}
}삽입 정렬과 다르게 퀵 정렬은 이미 정렬된 배열에 대해서 진행할 때 가장 최악의 효율을 보인다.
4) 병합 정렬 (Merge Sort)
배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법
- 시간 복잡도: 모든 경우에 대해 O(n log n)
- 공간 복잡도: O(n) (정렬을 위한 임시 배열이 필요함)
void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
void Merge(int[] arr, int left, int mid, int right)
{
int[] temp = new int[arr.Length];
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
while (i <= mid)
{
temp[k++] = arr[i++];
}
while (j <= right)
{
temp[k++] = arr[j++];
}
for (int l = left; l <= right; l++)
{
arr[l] = temp[l];
}
}
static void Main(string[] args)
{
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
MergeSort(arr, 0, arr.Length - 1);
foreach (int num in arr)
{
Console.WriteLine(num);
}
}이 모든 걸 C#에서 구현해서 쓸 일은 거의 없다. C#은 Sort 메소드를 제공하기 때문.
// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);
Console.WriteLine(string.Join(", ", numbers));
// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort();
Console.WriteLine(string.Join(", ", names));
개발 공부 블로그