공부/알고리즘 및 기타 공부
삽입 정렬 (C#)
ENUM01
2022. 1. 26. 17:02
개요
삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
처음 Key 값은 두 번째 자료부터 시작한다.
시간복잡도
O(N²)
들어갈 위치를 선택할 때 N 번,
선택하는 횟수 N 번
(일반적으로 선택 정렬보다 조금 빠르다.)
최선의 경우는 O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class 삽입정렬
{
static void Main(string[] args)
{
int[] array = { 10, 9, 6, 3, 8, 1 };
for (int i = 0; i < array.Length - 1; i++)
{
int j = i;
while (j >= 0 && array[j] > array[j + 1])
{
Swap(ref array[j], ref array[j + 1]);
}
}
for (int i = 0; i < array.Length; i++)
Console.WriteLine(array[i]);
}
private static void Swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
}
|
cs |