Selection Sort
위 막대그래프들을 크기 순서대로 정렬해 보자.
보통 정렬은 크기가 젤 큰 것부터 정렬을 하거나, 크기가 젤 작은 것부터 정렬을 한다.
최악의 경우의 연산 횟수를 헤아려보자.
N + (N-1) + (N-2) + (N-3) + ... + 1 = N(N+1) / 2 = (N^2+N) / 2
상수를 떼면 N^2 + N이고 시간복잡도는 O(N^2)이다.
시간제한이 1초라면 시간초과가 난다.
코드
public class 기초정렬(선택정렬)
{
static int[] arr = { 3, 2, 7, 116, 62, 235, 1, 23, 55, 77 };
static int n = 10;
static void Main(string[] args)
{
for(int i = n-1; i > 0; i--)
{
int mxidx = 0;
for(int j = 1; j <= i; j++)
{
if(arr[mxidx] < arr[j])
mxidx = j;
Swap(arr, mxidx, i);
}
}
}
static void Swap(int[] arr, int idx1, int idx2)
{
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
}
Bubble Sort
- 앞 원소가 뒤 원소보다 크면, 앞 원소와 뒤 원소 자리를 바꾸는 것을 반복하는 정렬
코드
public class 버블정렬
{
static void Main(string[] args)
{
int[] arr = { -2, 2, 4, 6, 13 };
int n = 5;
for(int i = 0; i < n; i++)
for(int j = 0; j < n-1-i; j++)
if(arr[j] > arr[j+1])
Swap(arr, j, j+1);
}
static void Swap(arr, int idx1, int idx2)
{
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
}
시간복잡도는 O(N^2)으로 1초 제한이 걸려있는 문제에서는 적합하지 않다.
삽입 정렬이라는 것도 있다. 이것 또한 시간복잡도가 O(N^2)이라서 1초 제한 문제에서 적합하지 않다.
Merge Sort
- 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬
- 길이가 N, M인 두 정렬된 리스트를 합쳐서 정렬하면 된다.
- 시간복잡도는 O(NlogN)이다.
(예시)
정렬된 두 배열 { -9, 1, 6, 8, 12 }와 { -7, 7, 13, 15 }를 Merge Sort
0. 두 배열의 인덱스를 변수로 만든다. (idx1, idx2)
1. 각 배열의 첫 번째 인덱스부터 하나씩 비교해 가며 가장 작은 수를 찾는다.
2. 가장 작은 수는 정답 배열 answer에 넣는다.
3. 가장 작은 수를 찾은 배열의 인덱스를 +1 한다.
4. 이 과정을 두 배열의 인덱스(idx1, idx2)가 배열 길이를 초과할 때까지 반복한다.
코드 (BOJ 11728 - 배열 합치기)
using System.Text;
namespace 정렬
{
internal class 배열_합치기
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
StringBuilder sb = new StringBuilder();
string[] input1 = sr.ReadLine().Split(" ");
int N = int.Parse(input1[0]);
int M = int.Parse(input1[1]);
int[] arrayA = new int[N];
input1 = sr.ReadLine().Split(" ");
for(int i = 0; i < arrayA.Length; i++)
{
arrayA[i] = int.Parse(input1[i]);
}
int[] arrayB = new int[M];
input1 = sr.ReadLine().Split(" ");
for(int i = 0; i < arrayB.Length; i++)
{
arrayB[i] = int.Parse(input1[i]);
}
int index1 = 0;
int index2 = 0;
int[] answerArray = new int[N + M];
int answerArrayIndex = 0;
bool isComplete = false;
while (answerArrayIndex < answerArray.Length)
{
if(index1 >= N)
{
// arrayB에 있는 것들 전부 다 answerArray에 넣기
while (answerArrayIndex < answerArray.Length)
{
answerArray[answerArrayIndex++] = arrayB[index2++]; // answerArray에 다 채워질 때까지
}
isComplete = true;
}
else if(index2 >= M)
{
while (answerArrayIndex < answerArray.Length)
{
answerArray[answerArrayIndex++] = arrayA[index1++]; // answerArray에 다 채워질 때까지
}
isComplete = true;
}
if (isComplete)
{
break;
}
if (arrayA[index1] <= arrayB[index2])
{
answerArray[answerArrayIndex++] = arrayA[index1++];
}
else if (arrayB[index2] <= arrayA[index1])
{
answerArray[answerArrayIndex++] = arrayB[index2++];
}
}
for(int i = 0; i < answerArray.Length; i++)
{
sb.Append($"{answerArray[i]} ");
//sw.Write($"{answerArray[i]} ");
}
sw.WriteLine(sb.ToString());
sw.Close();
sr.Close();
}
}
}using System.Text;
namespace 정렬
{
internal class BOJ11728_배열_합치기
{
static void Main(string[] args)
{
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
StringBuilder sb = new StringBuilder();
string[] input = sr.ReadLine().Split(" ");
int n = int.Parse(input[0]);
int m = int.Parse(input[1]);
int[] a = new int[n];
int[] b = new int[m];
int[] c = new int[n + m];
input = sr.ReadLine().Split(" ");
for (int i = 0; i < n; i++)
a[i] = int.Parse(input[i]);
input = sr.ReadLine().Split(" ");
for (int i = 0; i < m; i++)
b[i] = int.Parse(input[i]);
int aidx = 0;
int bidx = 0;
for(int i = 0; i < n+m; i++)
{
if (bidx == m)
c[i] = a[aidx++];
else if (aidx == n)
c[i] = b[bidx++];
else if (a[aidx] <= b[bidx])
c[i] = a[aidx++];
else
c[i] = b[bidx++];
}
for (int i = 0; i < n + m; i++)
sb.Append($"{c[i]} ");
sw.WriteLine(sb.ToString());
sw.Close();
sr.Close();
}
}
}
Merge Sort 구현
using System.Text;
namespace 정렬
{
internal class 머지정렬
{
static int n = 10;
static int[] arr = new int[1000001];
static int[] tmp = new int[1000001];
static void Merge(int st, int en)
{
int mid = (st + en) / 2;
int lidx = st;
int ridx = mid;
for(int i = st; i < en; i++)
{
if (lidx == mid)
tmp[i] = arr[ridx++];
else if (ridx == en)
tmp[i] = arr[lidx++];
else if (arr[lidx] <= arr[ridx])
tmp[i] = arr[lidx++];
else if (arr[ridx] <= arr[lidx])
tmp[i] = arr[ridx++];
}
for (int i = st; i < en; i++)
arr[i] = tmp[i];
}
static void Merge_Sort(int st, int en)
{
if (en == st + 1)
return;
int mid = (st + en) / 2;
Merge_Sort(st, mid);
Merge_Sort(mid, en);
Merge(st, en);
}
static void Main(string[] args)
{
Array.Copy(new int[] { 15, 25, 22, 357, 16, 23, -53, 12, 46, 3 }, arr, 10);
StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
StringBuilder sb = new StringBuilder();
Merge_Sort(0, n);
for (int i = 0; i < n; i++)
sb.Append($"{arr[i]} ");
sw.WriteLine(sb.ToString());
sw.Close();
sr.Close();
}
}
}
Stable Sort
우선순위가 같은 원소들끼리 원래 순서를 따라가도록 하는 정렬
ex) Merge Sort
Quick Sort
- 매 단계마다 pivot이라는 원소를 제자리로 보내며 정렬하는 방법
- 정렬은 재귀적으로 한다.
- Quick Sort는 시간복잡도가 O(N^2)이니 코딩테스트에서 Quick Sort는 직접 구현해서 문제를 풀지 말자.
Quick Sort 1회전
using System.Text;
namespace 정렬
{
internal class 퀵정렬_1회전
{
static int[] arr = { 6, -8, 1, 12, 8, 3, 7, -7 };
static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
static StringBuilder sb = new StringBuilder();
static void Main(string[] args)
{
int pivot = arr[0];
int lidx = 1;
int ridx = arr.Length - 1;
// lidx와 ridx가 교차되기 전까지 반복
while(lidx <= ridx)
{
// arr[lidx]가 pivot보다 큰 값이 나올때까지 lidx를 오른쪽으로 이동
while (arr[lidx] <= pivot) // arr[lidx]가 pivot보다 작으면
{
lidx++;
}
// arr[ridx]가 pivot보다 작은 값이 나올때까지 ridx를 왼쪽으로 이동
while (arr[ridx] >= pivot) // arr[ridx]가 pivot보다 크면
{
ridx--;
}
// arr[lidx] > pivot이고 arr[ridx] < pivot임
if (lidx <= ridx && arr[lidx] > pivot && arr[ridx] < pivot)
{
// 두 값을 교환
Swap(arr, lidx, ridx);
}
}
// arr[lidx]와 pivot을 교환
Swap(arr, 0, ridx);
foreach(int num in arr)
{
sb.Append($"{num} ");
}
sw.WriteLine(sb.ToString());
sw.Close();
}
static void Swap(int[] arr, int idx1, int idx2)
{
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
}
}
Quick Sort
using System.Text;
namespace 정렬
{
internal class 퀵정렬
{
static int[] arr = { 15, 25, 22, 357, 16, 23, -53, 12, 46, 3 };
static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
static StringBuilder sb = new StringBuilder();
static void Main(string[] args)
{
int n = arr.Length;
Quick_Sort(0, n);
foreach (int num in arr)
sb.Append($"{num} ");
sw.WriteLine(sb.ToString());
sw.Close();
}
static void Swap(int[] arr, int idx1, int idx2)
{
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
static void Quick_Sort(int st, int en)
{
if (en <= st + 1) return;
int pivot = arr[st];
int l = st + 1;
int r = en - 1;
while (true)
{
while (l <= r && arr[l] <= pivot) l++;
while (l <= r && arr[r] >= pivot) r--;
if (l > r) break;
Swap(arr, l, r);
}
Swap(arr, st, r);
Quick_Sort(st, r);
Quick_Sort(r + 1, en);
}
}
}
Merge Sort, Quick Sort 비교
| Merge Sort | Quick Sort | |
| 시간복잡도 | O(NlogN) | 평균 O(NlogN) 최악의 경우 O(N^2) 평균적으로 Merge Sort보다 빠르다. |
| 추가적으로 필요한 공간(Overhead) | O(N) | O(1) |
| Stable Sort 여부 | O | X |
cf) 바킹독 실전 알고리즘 - 정렬1
'자료구조, 코딩테스트 > 정렬(Sort)' 카테고리의 다른 글
| [코딩테스트] Programmers - 문자열 내 마음대로 정렬하기 (실패) (0) | 2026.05.23 |
|---|---|
| [코딩테스트] Programmers - 가장 큰 수 (실패) (0) | 2026.05.22 |
| [코딩테스트] Programmers - K번째수 (실패) (0) | 2026.05.02 |
| [자료구조] Radix Sort (0) | 2026.05.02 |
| [자료구조] Counting Sort (0) | 2026.05.01 |