C# 정렬 알고리즘 1 ( 선택정렬 / 삽입정렬 )
정렬 알고리즘
정렬 알고리즘이란 주어진 데이터 세트를 특정 순서 (보통 숫자의 오름차순 또는 내림차순, 문자열의 사전식 순서) 로 배열하는 방법을 한다.
정렬 알고리즘의 방식에는 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬이 있다.
이번 포스트에서는 선택정렬과 삽입정렬을, 다음 포스트에서는 퀵 정렬과 병합정렬을 다뤄볼 예정이다.
1. 선택 정렬
선택 정렬은 배열에서 최소값(또는 최대값)을 찾아 맨 앞(또는 맨 뒤)와 교환하는 방법이다.
시간 복잡도: 최악의 경우와 평균적인 경우 모두 O(n^2)
공간 복잡도: O(1) (상수 크기의 추가 공간이 필요없기 때문이다.)
O()의 경우 Big O라고 알고리즘의 효율성을 나타내는 표기법이다.
가장 작은 원소를 찾아서 맨 앞에 위치하는 것을 반복하여 정렬하는 알고리즘은 다음과 같다.
static void Main(string[] args)
{
// 배열
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
for(int i = 0; i < arr.Length; i++)
{
// 체크를 하려는 값 저장 ex) minIndex = 0
int minIndex = i;
// 자기 자신과 비교하는 건 의미없기 때문에 그 다음수와 비교하기 위해 i + 1을 해줌
for(int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minIndex]) //arr[1](2) < arr[0] 5
{
minIndex = j; // minIndex = 1
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
foreach(int num in arr)
{
Console.WriteLine(num);
}
}
주석을 달아 놨지만 작동하기 전까지는 혼동이 많이 오기 때문에 하나하나 수를 대입해보면서 가보자
현재 배열은 6개의 크기로 5, 2, 4, 6, 1, 3 이렇게 된다.
배열만큼의 반복을 먼저 돌리면서 minIndex라는 하나의 변수에 체크하려는 임의의 값을 대입한다.
i = 0 부터 시작하기 때문에 0을 minIndex에 넣고 또 다른 반복문을 돌린다.
int j = i 라고하면 i 와 j의 값이 같기 때문에 자기 자신과 비교하는것이 되어 i + 1을 해준다. 마찬가지로 배열 크기만큼 돌려준다.
조건을 arr[j] < arr[minIndex] 라고 줬는데 이는 가장 먼저 초기숫자와 그 앞의 숫자와 비교를 한 후 조건이 참이면 해당 수를 minIndex에 담아준다.
수를 대입해보면 arr[1] < arr[0] 이 되겠으며 이는 2 < 5 이므로 참이 되어 minIndex에 1을 넣어준다. 즉, 2가 작은 수라고 넣어 두는 것이다.
마찬가지로 j의 반복문이 돌면 이제는 j = 2가 되어 arr[2] 와 minIndex가 1이기 때문에 arr[1]을 비교하는 arr[2] < arr[1] 조건문이 된다.
이는 4 < 2 라는 식이 되며 거짓이기 때문에 바로 반복문으로 빠져나간다.
이런식으로 가다가 arr[4] (1) < arr[1] (2) 가 되는데 마찬가지로 조건문의 참이 성립하여 minIndex에 4를 대입하고 반복문이 끝난다.
그렇다면 int temp = arr[i], 즉, 지금은 arr[0] 이기 때문에 가장 앞자리가 되겠고, 이를 temp에 넣어둔다. 그럼 temp는 5가 되겠고, arr[i] = arr[minIndex]가 되는데 현재 minIndex = 4이므로 arr[4], 1이 arr[0] 로 위치하게 된다.
그리고 arr[0]에 위치해있던 5는 temp에 담아뒀기 때문에 이를 arr[minIndex]인 5번째 칸으로 옮겨주게 된다.
이렇게 한번 돌리고 나면 현재 배열은 {1, 2, 4, 6, 5, 3} 이런식으로 1과 5의 위치가 바뀌게 된다.
이러한 방법으로 하나하나 돌려서 반복문이 완전히 끝나게 되면 배열이 순차적으로 들어가게 된다.
복잡한 방법인 만큼 성능 자체는 그다지 좋지 않다.
2. 삽입 정렬
삽입 정렬은 정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법이다.
시간 복잡도: 최악의 경우 O(n^2) 하지만 정렬되어 있는 경우에는 O(n) (이유는 후술하겠다.)
공간 복잡도: O(1) (상수의 크기와 추가 공간이 필요하지 않다.)
현재 위치에서 그 이하의 배열을 정렬된 배열 부분에 삽입하는 방법으로 정렬하는 알고리즘이다.
static void Main(string[] args)
{
// 배열
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
// 배열 크기만큼 반복
for(int i = 1; i < arr.Length; i++) //ex) i = 1일때
{
int j = i - 1; // j = 0
int key = arr[i]; // key = 2
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
foreach(int num in arr)
{
Console.WriteLine(num);
}
}
마찬가지로 주석을 달아놨지만 수를 대입하면서 하나하나 알아가보도록 하자
배열은 5, 2, 4, 6, 1, 3 이며 배열의 크기만큼 반복문을 돌려준다. 여기서는 초기값 i 가 1이 된다.
그리고 임의의 변수 j 에 i - 1값을 주면 현재 j = 0이 된다.
거기에 또 다른 임의의 변수 key 값에 arr[i]인 2를 넣어준다. 그럼 key = 2, j = 0이 된다.
이후 반복문에서 j 가 0보다 크거나 같고, arr[j]가 key값보다 크다면 반복문이 실행된다.
수를 대입해보면 j 는 0 이면서, arr[j] 인 5 가 key값인 2보다 크기 때문에 반복문이 실행된다.
반복문 안에는 arr[j + 1] = arr[j] 인데 이는 5를 한 칸 우측으로 옮긴다는 뜻이다. 그렇다면 5, 5, 4 ,6, 1, 3 이런 느낌처럼 되는데 그렇다면 2는 어디갔냐하면 바로 key값에 넣어놨기 때문에 상관없다.
그리고 j--해줬으니 j = -1 이 되고, key는 그대로 2, arr[1] = 5가 된 상태로 반복문이 끝난다.
마지막으로 arr[j + 1] = key 즉, arr[0] 에 2를 넣어주도록 하자.
그러면 {2, 5, 4, 6, 1, 3} 이렇게 된다.
위에서 정렬이 되어 있는 경우에는 O(n) 이라고했는데 이는 while문의 조건을 보면 key값 보다 좌측에 있는 숫자가 클 경우만 작동하는 방식인데, 바꿔 말하면 5 , 4 라고하면 while문의 조건이 참이 되지만, 4, 5가 되면 while문의 조건은 참이 되지 않으므로 조건없이 그냥 지나가게 된다. 이런 식으로 모두 정렬되어있다면 조건문을 타지 않게 되므로 O(n)이 된다.