목차
C# 언어로 백준 문제를 풀다가 연습한 정렬 알고리즘을 한 게시글로 정리했습니다.
혹시나 틀린 정보가 있다면 알려주시기 바랍니다 :)
시간 복잡도가 O(n²)
└ 버블 정렬(Bubble Sort)
: 인접한 두 원소를 비교하여 정렬하는 간단한 알고리즘
--> 1번째 원소와 2번째 원소를 비교하여 정렬하는 식으로 n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n-2번째와 n-1번째까지 정렬하는 방식으로 반복하여 정렬한다.
- 코드
public void BubbleSort(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
{
for (int j = 1; j < n - i; j++)
{
if (arr[j - 1] > arr[j])
{
(arr[j - 1], arr[j]) = (arr[j], arr[j - 1]);
}
}
}
}
※ 이해를 위한 영상
└ 선택 정렬(Selection Sort)
: 1번째 원소부터 끝까지 훑어서 가장 작은 게 1번째 원소, 그 다음엔 2번째 원소부터 끝까지 훑어서 가장 작은게 2번째 원소와 같은 방식으로 (n - 1)번 반복하여 정렬한다.
- 어떻게 정렬이 되어 있든 일관성 있게 n(n - 1) / 2 에 비례하는 시간이 걸린다.
- 버블 정렬에 비해 두 배 정도 빠르다.
- 코드
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;
}
(arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
}
※ 이해를 위한 영상
└ 삽입 정렬(Insertion Sort)
: k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식으로 정렬한다.
- 시간 복잡도 O(n²)의 정렬들 중 빠른 편이나, 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크다.
- 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거하는 경우에는 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.
- 배열이 작을 경우에 상당히 효율적이다.
- 코드
public void InsertionSort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
for (int j = i; j > 0; j--)
{
if (arr[j] < arr[j - 1])
(arr[j], arr[j - 1]) = (arr[j - 1], arr[j]);
}
}
}
※ 이해를 위한 영상
시간 복잡도가 O(n log n)
└ 병합/합병 정렬(Merge Sort)
: 원소 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개고 쪼개서 자른 순서의 역순으로 크기를 비교해 병합해 나가며 정렬한다.
- O(n log n) 의 시간복잡도를 가진다.
- 성능은 퀵 정렬보다 전반적으로 뒤떨어지고, 데이터 크기만한 메모리가 더 필요하다.
- 최대의 장점은 데이터의 상태에 별 영향을 받지 않는다. --> 동일 값에 대해서 기존 기준의 정렬순서가 유지되는 안정 정렬이다.
- 도식화
→ Stack(1)의 Merge() 함수 도식화
- 코드
int[] temp;
void Main()
{
temp = new int[arr.Length];
}
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 i = left; // 왼쪽 부분 시작점
int j = mid + 1; // 오른쪽 부분 시작점
int k = left; // temp 배열에 저장할 위치
while (i <= mid && j <= right) // 왼쪽과 오른쪽의 각 index가 끝을 넘을 때까지 반복
{
if (arr[i] <= arr[j]) // 왼쪽과 오른쪽의 각 데이터 값을 비교하여 더 작은 쪽을 temp에 추가
{
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];
}
}
※ 이해를 위한 영상
└ 퀵 정렬(Quick Sort)
: 분할 정복 방법을 통해 정렬하는 알고리즘으로 다음과 같은 과정을 통해 정렬한다.
- 원소 하나를 기준(피벗, pivot)으로 삼는다.
- 피벗보다 작은 것을 앞으로 빼내고 그 뒤에 피벗을 옮겨 피벗보다 작은 것, 큰 것으로 나눈다. --> 이를 'partition step'이라 한다.
- 나누어진 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다.
>> 퀵 정렬의 특징
- 같은 값의 순서가 바뀔 수 있는 불안정 정렬이다.
- 평균 O(n log n)의 시간복잡도를 갖지만, 최악의 경우 O(n²)의 시간복잡도를 갖는다.
→ 퀵 정렬의 핵심은 어떻게 pivot을 선정하는가?
: 피벗을 최솟값이나 최댓값으로 계속해서 잡게 되는 최악의 경우 O(n²)의 시간복잡도를 갖게 된다.
>> pivot을 선정하는 여러가지 방식
- 첫번째 값이나 마지막 값을 pivot으로 선정한다. --> 퀵 정렬의 원리와 과정을 이해하기 가장 용이한 방법
- 중간값을 pivot으로 선정한다.
- 무작위 값을 pivot으로 선정한다.
- Median of Three : 첫번째 값, 중간값, 마지막 값을 먼저 정렬하고 그 중 중간값을 pivot으로 선정한다. --> 성능적으로 더욱 향상된 방식이다.
>> Partition Step 방식
- Hoare Partition : 주로 첫번째 값을 pivot으로 선정하고, 양쪽 끝에서 포인터를 시작해 pivot보다 작은 값을 앞으로, pivot보다 큰 값을 뒤로 모은 뒤, 마지막에 pivot을 정확한 자리에 이동시킨다.
- 구현이 좀 복잡하지만 성능이 더 우수하다.
- Lomuto Partition : 마지막 값을 pivot으로 고정하고, 하나의 포인터를 사용해서 pivot보다 작은 값들을 앞으로 모은 뒤, 마지막에 pivot을 정확한 자리에 이동시킨다.
- 비효율적이라 큰 배열이나 중복이 많은 데이터에서 성능이 저하되지만 간단하고 직관적이다.
>> 첫번째 값을 pivot으로 선정한 방식 (Hoare Partition)
- 도식화
- 코드
private int Partition(int[] arr, int l, int h)
{
int pivot = arr[l]; // pivot 설정
int low = l + 1; // low는 pivot의 바로 다음 위치
int high = h;
while (low <= high)
{
if (arr[low] < pivot) // pivot보다 큰 값이 나올 때까지 이동
{
low++;
continue;
}
if (arr[high] > pivot) // pivot보다 작은 값이 나올 때까지 이동
{
high--;
continue;
}
if (low < high) // low와 high가 멈춘 지점이 서로 역전되지 않았다면
(arr[low], arr[high]) = (arr[high], arr[low]); // swap
}
(arr[l], arr[high]) = (arr[high], arr[l]); // pivot과 high swap
return high; // pivot 위치 반환
}
public void MyQuickSort(int[] arr, int l, int h)
{
if (l < h)
{
int pivot = Partition(arr, l, h);
MyQuickSort(arr, l, pivot - 1);
MyQuickSort(arr, pivot + 1, h);
}
}
※ 이해를 위한 영상
>> 랜덤으로 Pivot을 선정하는 방식
: 랜덤으로 Pivot을 선정하고 이를 첫번째 값과 Swap하여 Hoare 방식으로 Quick Sort
- 입력 패턴에 관계없이 QuickSort의 평균 성능을 안정적으로 유지하는 효과 --> 최악의 경우가 발생할 확률을 줄이고, 항상 평균적으로 O(n log n) 의 시간복잡도에 가깝게 만든다.
- 코드
Random rand = new Random();
private int Partition(int[] arr, int l, int h)
{
int randomPivot = rand.Next(l, h + 1); // 랜덤으로 pivot 설정
(arr[l], arr[randomPivot]) = (arr[randomPivot], arr[l]) // Pivot과 첫번째 값 Swap
int pivot = arr[l] // 첫번째 값 pivot 설정
int low = l + 1; // low는 pivot의 바로 다음 위치
int high = h;
while (low <= high)
{
if (arr[low] < pivot) // pivot보다 큰 값이 나올 때까지 이동
{
low++;
continue;
}
if (arr[high] > pivot) // pivot보다 작은 값이 나올 때까지 이동
{
high--;
continue;
}
if (low < high) // low와 high가 멈춘 지점이 서로 역전되지 않았다면
(arr[low], arr[high]) = (arr[high], arr[low]); // swap
}
(arr[l], arr[high]) = (arr[high], arr[l]); // pivot과 high swap
return high; // pivot 위치 반환
}
public void MyQuickSort(int[] arr, int l, int h)
{
if (l < h)
{
int pivot = Partition(arr, l, h);
MyQuickSort(arr, l, pivot - 1);
MyQuickSort(arr, pivot + 1, h);
}
}
>> Median Of Three 방식
: 맨 앞, 중앙, 맨 뒤의 값을 미리 정렬하고 정렬된 세 값 중 중앙값을 Pivot으로 선정한다. 이후 선정된 pivot을 첫번째 값과 Swap하여 Hoare 방식으로 QuickSort
- 항상 중앙값을 Pivot으로 선정하기 때문에 대부분의 상황에서 O(n log n) 의 시간복잡도에 가깝게 유지된다.
- 코드
private int MedianOfThree(int[] arr, int l, int h)
{
int mid = (l + h) / 2;
// 중앙값 정렬
if (arr[mid] < arr[l])
(arr[l], arr[mid]) = (arr[mid], arr[l]);
if (arr[h] < arr[l])
(arr[l], arr[h]) = (arr[h], arr[l]);
if (arr[h] < arr[mid])
(arr[mid], arr[h]) = (arr[h], arr[mid]);
// 찾은 중앙값을 Pivot으로 쓰기 위해 첫번째 값과 Swap
(arr[l], arr[mid]) = (arr[mid], arr[l]);
return arr[l];
}
private int Partition(int[] arr, int l, int h)
{
int pivot = MedianOfThree(arr, l, h); // pivot 설정
int low = l + 1; // low는 pivot의 바로 다음 위치
int high = h;
while (low <= high)
{
if (arr[low] < pivot) // pivot보다 큰 값이 나올 때까지 이동
{
low++;
continue;
}
if (arr[high] > pivot) // pivot보다 작은 값이 나올 때까지 이동
{
high--;
continue;
}
if (low < high) // low와 high가 멈춘 지점이 서로 역전되지 않았다면
(arr[low], arr[high]) = (arr[high], arr[low]); // swap
}
(arr[l], arr[high]) = (arr[high], arr[l]); // pivot과 high swap
return high; // pivot 위치 반환
}
public void MyQuickSort(int[] arr, int l, int h)
{
if (l < h)
{
int pivot = Partition(arr, l, h);
MyQuickSort(arr, l, pivot - 1);
MyQuickSort(arr, pivot + 1, h);
}
}
시간 복잡도가 O(n + k)
: 여기서 k 는 데이터의 최댓값을 의미한다.
└ 계수 정렬(Counting Sort)
: 특정 데이터의 개수를 데이터의 값에 대응하는 위치(index)에 저장한 뒤, 자신의 위치에서 앞에 있던 값을 모두 더한 배열을 만든 뒤, 거기서 데이터가 들어가야 할 위치를 찾아내는 정렬 알고리즘
- O(n + k) (k 는 데이터의 최댓값을 의미한다.)의 시간복잡도를 가진다. 즉, 최댓값에 따라 효율이 좌지우지된다.
- 배열을 사용하는 특성상, 정수라는 전제를 깔고 한다.
>> 음수 제외, 비안정 정렬
: 자연수로 이루어진 배열을 입력 순서 상관없이 정렬한다.
- 코드가 단순하여 구현하기 쉬우며 코드 처리 속도가 빠르다.
- 코드
private void CountingSort(int[] arr)
{
// 최댓값 찾기
int max = 0;
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > max)
max = arr[i];
}
// 수의 개수를 저장할 배열 생성 및 카운트
int[] count = new int[max + 1];
for (int i = 0; i < arr.Length; i++)
{
count[arr[i]]++;
}
// count 배열을 기반으로 원본 배열 정렬
int index = 0;
for (int i = 0; i < count.Length; i++)
{
while (count[i] > 0)
{
arr[index++] = i;
count[i]--;
}
}
}
>> 음수 포함, 안정 정렬
: 음수가 포함된 정수로 이루어진 배열을 입력 순서를 신경써서 정렬한다.
- 코드를 구현하기가 비교적 복잡하며, 비안정 정렬에 비해 코드 처리 속도가 약간 느리다.
- 코드
private void CountingSort(int[] arr)
{
// 최솟값, 최댓값 찾기
int min = arr[0];
int max = arr[0];
foreach (int num in arr)
{
if (num < min) min = num;
if (num > max) max = num;
}
// 수의 개수를 저장할 배열 생성 및 카운트
int range = max - min + 1;
int[] count = new int[range];
for (int i = 0; i < range; i++)
{
count[arr[i] - min]++; // 음수 보정 --> 최솟값의 index가 0이 되도록
}
// 누적 합 계산 --> 안정 정렬을 위해
for (int i = 1; i < range; i++)
{
count[i] += count[i - 1];
}
// 출력용 임시 배열 생성
int[] temp = new int[arr.Length];
// 역순으로 정렬 결과 채우기 --> 안정성 유지
for (int i = arr.Length - 1; i >= 0; i--)
{
int num = arr[i];
int index = count[num - min] - 1;
temp[index] = num;
count[num - min]--;
}
// 정렬 결과를 원본 배열로 덮어쓰기
for (int i = 0; i < arr.Length; i++)
{
arr[i] = temp[i];
}
}'Development > Knowledge' 카테고리의 다른 글
| 자료구조 (0) | 2025.11.15 |
|---|---|
| 소수 판별 함수 만들기 (0) | 2025.11.11 |
| 유클리드 호제법을 활용하여 최대공약수, 최소공배수 구하기 (0) | 2025.11.06 |