옆의 요소들의 순서가 잘못되어 있다면 두 요소들을 교환. 이를 통해 더 큰 요소가 뒤로 이동.
비교와 교환을 배열의 길이만큼 반복하여 정렬.
// Input
int[] data = { 3, 2, 1, 4, 5 };
int N = data.Length; // 배열의 길이
// Process: Bubble Sort
for (int i = 0; i < N - 1; i++) // i = 0 to N-1
{
for (int j = 0; j < N - i - 1; j++) // j = 0 to N-i-1
{
if (data[j] > data[j + 1]) // 현재 요소와 다음 요소를 비교하여 정렬
{
// 두 요소의 위치를 바꿈 (SWAP)
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
// Output
for (int i = 0; i < N; i++)
{
Console.WriteLine($"{data[i]}");
}
선택 정렬(Selection Sort)
전체 배열에서의 최솟값을 선택.
선택된 가장 최솟값을 가장 오른쪽의 요소와 교환.
정렬된 요소(가장 오른쪽)을 제외한 부분에서 범위를 좁히며 최솟값의 선택과 교환을 반복하여 정렬.
// Input
int[] data = { 3, 2, 1, 4, 5 };
int N = data.Length; // 배열의 길이
// Process: Selection Sort
for (int i = 0; i < N - 1; i++) // i = 0 to N-1
{
for (int j = i + 1; j < N; j++) // j = i+1 to N
{
if (data[i] > data[j]) // 부등호 방향에 따라 오름차순(>) 혹은 내림차순(<)
{
// 두 요소의 위치를 바꿈 (SWAP)
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
// Output
for (int i = 0; i < N; i++)
{
Console.WriteLine($"{data[i]}");
}
삽입 정렬(Insertion Sort)
초기에는 두 번째 요소와 그 왼쪽에 있는 요소를 비교하여 두 번째 요소가 더 작다면 교환.
세 번째 요소와 그 왼쪽에 있는 요소들을 비교하여 동일한 방식으로 교환.
마지막 요소까지 동일한 작업을 반복하여 정렬.
// Input
int[] data = { 3, 2, 1, 4, 5 };
int N = data.Length; // 배열의 길이
// Process: Insertion Sort
for (int i = 1; i < N; i++)
{
int key = data[i];
int j = i - 1;
// key보다 큰 요소들을 한 칸씩 뒤로 이동
while (j >= 0 && data[j] > key)
{
data[j + 1] = data[j];
j = j - 1;
}
data[j + 1] = key; // 적절한 위치에 key 삽입
}
// Output
for (int i = 0; i < N; i++)
{
Console.WriteLine($"{data[i]}");
}
퀵 정렬(Quick Sort)
배열의 마지막 원소를 피봇으로 선택.
피봇 값보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 분할.
작은 값들의 부분에 대해서 새로운 피봇값을 기준으로 위와 같이 퀵 정렬을 다시 수행.
큰 값들의 부분에 대해서 새로운 피봇값을 기준으로 위와 같이 퀵 정렬을 다시 수행.
이렇게 퀵 정렬을 재귀적으로 수행한 후 왼쪽 배열들과 기존 피봇 값, 오른쪽 배열들을 합쳐 정렬된 배열 완성.
// Input
int[] data = { 3, 9, 1, 4, 2, 8, 5, 7, 6 };
int N = data.Length; // 배열의 길이
// Process: Quick Sort
void QuickSort(int[] arr, int low, int high)
{
if (low < high)
{
int pivotIndex = Partition(arr, low, high);
QuickSort(arr, low, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, high);
}
}
// 분할 및 기준 원소 선택
int Partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
i++;
// 요소 교환
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// pivot 위치 재조정
int temp2 = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp2;
return i + 1;
}
// Output
QuickSort(data, 0, N - 1);
for (int i = 0; i < N; i++)
{
Console.WriteLine($"{data[i]}");
}
병합 정렬(Merge Sort)
배열을 중간지점을 기준으로 하여 왼쪽, 오른쪽 두 개의 작은 배열로 분할.
배열의 분할이 불가능할 때(배열의 길이가 1 이하)까지 계속해서 반복하여 분할.
각각의 가장 작은 부분 배열에 대해 비교하여 정렬.
정렬된 왼쪽 배열과 오른쪽 배열의 요소들을 비교하여 작은 값들을 순서대로 결과 배열 완성.
// Input
int[] data = { 3, 9, 1, 4, 2, 8, 5, 7, 6 };
int N = data.Length; // 배열의 길이
// Process: Merge Sort
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++];
}
// temp 배열의 내용을 원래 배열에 복사
for (int l = left; l <= right; l++)
{
arr[l] = temp[l];
}
}
// Output
MergeSort(data, 0, N - 1);
for (int i = 0; i < N; i++)
{
Console.WriteLine($"{data[i]}");
}
