정렬 알고리즘
데이터를 특정 순서(사전 순서, 대소 크기 등...)으로 배열하는 방법!
선택 정렬(Selection Sort)
- 선택 정렬은 배열에서 최소값 혹은 최대값을 찾아 맨 뒤나 앞과 교환하는 방식이다.
- 시간 복잡도는 최악과 평균의 경우 모두 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;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
foreach (int num in arr)
{
Console.WriteLine(num);
}
삽입 정렬(Insertion Sort)
- 정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법.
- 시간 복잡도는 최악의 경우 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];
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
foreach (int num in arr)
{
Console.WriteLine(num);
}
코드를 확인해보면 i는 arr[1]이고, j는 arr[0]이다.
key라는 변수에 arr[i]를 저장한 뒤, while문에서 arr[j]와 arr[i]를 비교하여 arr[j]가 더 클 경우 arr[j + 1]에 arr[j]를 넣는다.
이 후 j--가 실행되어 j = -1이 되고, j가 0보다 작기 때문에 while문에서 벗어난다.
그 후, arr[j + 1] = key가 실행되어 arr[0]에 key값을 넣는다.
결과적으로 {2, 5, 4, 6, 1, 3}으로 정렬되게 된다.
for문을 한 번 더 돌면 {2, 4, 5, 6, 1, 3} 처럼 이미 정렬되어 있는 자리에 정렬되지 않은 부분을 삽입하는 것처렴 정렬이 되게 된다.
삽입 정렬 순서 { 5, 2, 4, 6, 1, 3 }
{2, 5, 4, 6, 1, 3} → {2, 4, 5, 6, 1, 3} → {2, 4, 5, 6, 1, 3} → {1, 2, 4, 5, 6, 3} → {1, 2, 3, 4, 5, 6}
만약 이미 정렬되어 있는 경우, 위의 코드의 while문이 실행이 되지 않기 때문에 시간 복잡도가 O(n)이 된다.
퀵 정렬(Quick Sort)
- 퀵 정렬은 피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법이다.
- 시간 복잡도 : 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n)
- 공간 복잡도 : 평균적으로 O(log n), 최악의 경우 O(n)
예제)
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);
}
}
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;
}
void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
QuickSort(arr, 0, arr.Length - 1);
foreach (int num in arr)
{
Console.WriteLine(num);
}
Partition 함수가 1번 실행되고 난 모습, pivot이 자신의 자리를 찾았고 pivot 왼쪽으로는 더 작은 수들이, 오른쪽으로는 더 큰 수들이 모여있는 것을 확인할 수 있다.
이후, 왼쪽과 오른쪽에 QuickSort를 다시 적용해주고, 이를 더 이상 분할할 수 없을 때까지 반복해서 실행하면 최종적으로 정렬이 된다.
참고하기
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
병합 정렬(Merge Sort)
- 병합 정렬은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법이다.
- 퀵 정렬은 pivot을 잡는 기준이 없지만, 병합 정렬의 경우 가운데를 기준으로 분할하기 때문에 데이터의 분포에 영향을 덜 받는다. 이러한 이유로 항상 시간 복잡도가 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];
}
}
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
MergeSort(arr, 0, arr.Length - 1);
foreach (int num in arr)
{
Console.WriteLine(num);
}
병합 정렬의 진행 방식 ▼
※ 출처 및 참고하기
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
C#의 Sort
Sort 메서드
Sort메서드는 배열이나 리스트의 요소들을 정렬하는 메서드이다.- 정렬은 오름차순으로 수행되나, 다양한 정렬 기준을 사용할 수 있다.
Sort메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없다!
사용 예제)
// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
// 배열을 정렬하는 방법(배열.Sort()는 없음!)
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));
