알고리즘이란, 컴퓨터가 문제를 해결하는 방식을 설명하는 일련의 과정이라고 한다.
즉, 우리가 지금까지 코딩을 해오면서 만들었던 여러 기능들이 사실은 알고리즘이었던 것이다.
이래도 아직 알고리즘이라는 단어 자체가 이해가 안 될 수 있다.
많은 곳에서 알고리즘이라는 단어를 접할 수 있는데, 유튜브 알고리즘이 대표적인 것 같다.
그래서 많은 사람들이 알고리즘 하면 유튜브만 떠올리는 경우도 있는데, 유튜브 알고리즘은 극히 일부일 뿐이다.
여러 종류의 알고리즘이 있고, 그 중에 유튜브의 영상노출 알고리즘도 있고, 오늘 알아볼 정렬 알고리즘도 있다.
정렬 알고리즘은 우리가 인터넷에서 사용해봤던 내림차순, 오름차순 등, 순서대로 데이터들을 나열해주는 알고리즘이다.
정렬 알고리즘의 종류와 수는 굉장히 다양하지만, 우선 하나씩 천천히 알아보도록 하자.
우선 버블정렬(Bubble Sort)이다.
버블정렬은 데이터가 들어있는 배열의 각 인덱스에 하나하나 접근하여,
오름차순일 경우 현재 인덱스보다 각 인덱스의 값이 작으면 교환하고,
내림차순일 경우 현재 인덱스보다 각 인덱스의 값이 크면 교환하는 방식으로 정렬한다.
이를 코드로 작성하면 다음과 같다.
int[] BubbleUp(int[] arr)
{
// 배열의 모든 요소를 탐색
for (int i = 0; i < arr.Length; i++)
{
// 각 반복에서 가장 큰 요소가 맨 뒤로 이동하므로
// 끝 인덱스는 감소하여 반복횟수를 줄임
for (int k = 0; k < arr.Length - i - 1; k++)
{
if (arr[k] > arr[k + 1])
{
int temp;
temp = arr[k];
arr[k] = arr[k + 1]
arr[k + 1] = temp;
}
}
}
return arr;
}
버블정렬은 이미 검사한 인덱스에도 다시 접근하여 비교하는 방식의 알고리즘이기 때문에, 불필요한 연산이 잦고, 이에 따라 정렬 속도가 느려지기 때문에 선호되지 않는다.
버블정렬을 통해 5만개의 정수를 오름차순으로 정렬할 때의 시간을 계산해보면 16초라는 시간이 소요된다.
이는 지금 생각해보면 그리 큰 시간이 아니라고 생각할 수 있지만, 데이터 수가 많으면 많아질 수록 소요시간이 기하급수적으로 증가하기 때문에 이 점을 생각해야한다.
다음으로는 선택정렬(Selection Sort)이다.
선택 정렬은 정렬을 원하는 배열 안의 가장 작은 (혹은 여타 정렬기준에 걸맞는) 값을 탐색한 후, 해당 항목을 순서대로 옮기는 정렬이다.
예를들어, 1부터 9까지의 무작위 정수가 하나씩 담긴 길이가 8인 정수 배열이 있다고 했을 때,
0번 인덱스 부터 8번 인덱스 까지 탐색하여 가장 작은 수인 1을 찾아 0번 인덱스에 삽입하고,
1번 인덱스부터 8번 인덱스까지 탐색하여 그 다음으로 작은 수인 2를 찾아 1번 인덱스에 삽입하는 방식을 반복하여 정렬하는 것이다.
선택 정렬을 코드로 작성하면 아래와 같다.
int[] SelSort(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
// 최소값 저장
int min = i;
// 현재 인덱스 i부터 배열 끝까지의 요소를 비교하여 최소값을 찾음
for (int k = i + 1; k < arr.Length; k++)
{
// 최소값을 찾았을 때 해당 인덱스를 min에 저장
if (arr[k] < arr[min])
min = k;
}
// 현재 인덱스와 최소값의 인덱스가 다른 경우에만 스왑
if (i != min)
{
int temp;
temp = arr[k];
arr[k] = arr[k + 1]
arr[k + 1] = temp;
}
}
return arr;
}
선택 정렬은 버블 정렬보다는 더 낮은 소요시간을 소모한다.
앞선 버블 정렬의 시간 계산 때와 마찬가지로 5만의 데이터를 정렬 했을 때, 버블 정렬의 약 8배에 달하는 2.2초의 소요시간을 소모했다.
이제 버블 정렬의 정렬 효율이 얼마나 떨어지는지 알 수 있다.
그러나, 선택 정렬역시 데이터의 수가 늘어날 떄의 소요시간의 증가폭이 높은 편에 속하기 때문에, 많은 양의 데이터를 정렬할 때도 바람직하지 않다.
다만 버블정렬 때와 같이 이미 비교를 마친 값에 다시 접근하지 않을 뿐이다.
다음으로는 퀵 정렬이다.
퀵정렬은 분할정복 과정을 통한 알고리즘 중 하나로, 정렬하려는 데이터 배열을 나누며 작은 단위로 쪼개진 배열을 대상으로 하나씩 정렬하여 전체를 정렬하는 것이다.
분할 정복이란, 큰 문제를 작은 하위문제들로 분할하여, 하위 문제들의 해답을 구한 뒤, 하위 문제들을 합쳐 전체 문제의 해답을 얻는 방식이다.
분할 정복의 절차는 다음 3단계와 같다.
1. 분할 : 원래 문제를 작은 하위 문제들로 분할한다. 이 과정은 보통 재귀적인 방법으로 이루어지며, 전체 문제를 하위 문제들로 분할하기 위해 필요한 절차다.
2. 정복 : 각 하위 문제들을 해결한다. 이 과정역시 재귀적인 방법으로 이루어지는 경우가 많으며, 하위 문제의 크기가 충분히 작아 직접 해결할 수 있는 범위일 경우 실행되는 부분을 말한다.
3. 결합 : 앞선 과정을 모두 거쳐 만들어진 해결된 하위 문제들을 순서에 맞게 결합한다.
절차적으로만 설명하면 쉽게 와닿지 않는다. 조금더 구체적으로 알아보자
예를들어, 0부터 10까지의 정수가 담긴 배열을 정렬하려고 했을 때, 중심점이 되는 Pivot을 정한다.
이때, 피벗은 되도록이면 배열의 중간지점으로 설정하는 것이 좋다.
피벗을 정하면, 배열을 순회하면서 피벗의 값보다 작은 것을 왼쪽으로, 큰것을 오른쪽으로 몰아서 분할한다.
이렇게 분할 한 후, 분할된 배열을 대상으로 다시 반복하여 분할하고, 그렇게 재귀를 통해 반복적으로 분할하면서 정렬하는 것이다.
위와 같은 내용을 코드로 작성한다면 아래와 같다.
우선, 분할의 내용이다.
// 배열을 분할하고, 분할 인덱스를 반환
int Partition(int[] arr, int min, int max)
{
// 중간 인덱스를 피벗으로
int pivotIdx = (min + max) / 2;
// 피벗값 설정
int pivotVal = arr[pivotIdx];
Swap(arr, pivotIdx, max);
// 배열을 순회하며 피벗보다 작은 값들을 저장하는 인덱스
int storeIdx = min;
for(int i = min; i < max; i++)
{
if (arr[i] < pivotVal)
{
// 현재 값이 피벗보다 작으면 해당값을 storeIdx 값과 교환
Swap(arr, i, storeIdx);
storeIdx++;
}
}
Swap(arr, storeIdx, max);
return storeIdx;
}배열을 순회하며 피벗보다 작은 값을 찾아내고 피벗보다 큰 값은 서로 교환한다.
피벗의 왼쪽에는 피벗보다 작은 값들을 위치시키고
오른쪽에는 피벗보다 큰 값들을 위치시키며,
마지막으로 피벗을 올바른 위치로 이동시키고, 그 위치를 반환하는 메서드를 만들었다.
쉽게 말하면, 기준점인 피벗을 기준으로, 배열 안에있는 데이터를 하나씩 검사하면서
피벗의 값보다 작은 값이면, 그 값을 왼쪽(앞)으로, 크면 오른쪽(뒤)로 정렬시키고,
중앙 인덱스(피벗)를 반환하는 메서드다.
즉, 0부터 10의 예를 다시 가져오면,
0부터 10까지의 정수가 담긴 배열의 총 길이는 12로, 최대 인덱스의 값은 11이다.
그래서 중간인 5번째 인덱스를 기준으로, 왼쪽에는 5번째 인덱스에 저장되어있는 값 보다 작은 값을,
오른쪽에는 5번째 인덱스값보다 큰 값을 몰아넣고,
피벗 인덱스인 6을 반환하는 메서드다.
여기서 Swap 함수는 아래처럼 배열과 배열의 인덱스를 매개로 받아, 배열 내에 각 idx1을 인덱스로 갖는 값과 idx2를 인덱스로 갖는 값을 서로 바꾸는 메서드다.
void Swap(int[] arr, int idx1, int idx2)
{
int temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
그 후에는 재귀함수로, 배열을 순회하며 반복적으로 왼쪽 그룹과 오른쪽 그룹을 더 잘게 쪼개어 정렬하는 기능이다.
void QuickSortHelper(int[] items, int min, int max)
{
while (min < max)
{
int partitionIdx = Partition(items, min, max);
// 분할된 배열의 왼쪽 부분에 대해 재귀적으로 정렬 수행 (정복)
if((partitionIdx - min) < max - partitionIdx)
{
QuickSortHelper(items, min, partitionIdx - 1);
min = partitionIdx + 1;
}
else
{
QuickSortHelper(items, partitionIdx + 1, max);
max = partitionIdx - 1;
}
}
}
앞에서 만든 Partition 메서드를 통해 피벗 인덱스를 설정하고, 피벗보다 왼쪽에 있다면 왼쪽 그룹을 다시 분할해서 재귀함수를 호출하고, 오른쪽에 있다면 오른쪽 그룹으로 분할해서 재귀함수를 호출한다.
말로만 설명하니 상당히 어려워 보이기 때문에, 0부터 10의 예시를 들어보자
우선 0부터 10의 최소값인 0을 min으로, 최대값 10을 max로 이 함수에게 전달해주자.
그러면 Partition 메서드를 통해 나온 6을 피벗으로 설정하고, if문으로 들어간다.
이 때 min은 0으로, else가 아닌 if문으로 진입한다.
0은 왼쪽 그룹에 속하기 때문에, QuickSortHelper가 5번째 인덱스보다 작은 값으로만 이루어진 왼쪽 그룹을 만든다.
그렇게 되면 처음 호출 시에 0부터 11의 범위로 실행됐던 QuickSortHelper가 이번엔 0부터 5까지의 범위를 대상으로 다시 검사하게 된다.
0부터 5를 대상으로 다시 재귀호출된 QuickSortHelper는 또 0부터 검사를 시작하며, 이번에는 0부터 3으로 그룹을 나누어 다시 호출한다.
이렇게 잘게 쪼개지면, min과 max가 같아지는 시점이 온다.
예를 들면, 0부터 3으로 분할하고, 0부터 1로 분할하면, 정수 값에서 1/2는 0이기 때문에 min과 max가 서로 0으로 while문을 진입하지 않게되는 시점이 오게되는 것이다.
글로만 설명하니 여전히 어렵다. 숫자로 다시 설명해보겠다.
| 0 | 6 | 1 | 3 | 7 | 2 | 4 | 8 | 5 |
| 피벗 7 | ||||||||
| 0 | 6 | 1 | 3 | 2 | 4 | 5 | 7 피벗 | 8 |
| 오른쪽그룹 | 정복 | |||||||
| 0 | 6 | 1 | 3피벗 | 2 | 4 | 5 | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| 왼쪽그룹 | 정복 | |||||||
| 결합 | ||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
위와같이 하나의 수를 기준으로 두고, 그 수보다 작은 수는 왼쪽으로, 큰수는 오른쪽으로 몰아가며, 비교할 정수가 없을 때 까지 반복하여 정렬하면 완성되는 방식이다.
'C# 일기' 카테고리의 다른 글
| 27. 반복기(Iterator) (0) | 2024.03.13 |
|---|---|
| 26. List와 Linked List (0) | 2024.03.13 |
| 25. Queue (2) | 2024.03.12 |
| 24. Stack (0) | 2024.03.12 |
| 23. IEnumerable과 yield (0) | 2024.03.12 |