Algorithm Step
Algorithm
연산이라는 사전적 의미를 갖는 알고리즘은 문제를 해결하기 위한 과정, 논리적인 절차에 따라 구성한 일련의 단계이며, 알고리즘에 따라 입력값으로 원하는 결과가 도출되도록 만들 수 있다.
컴퓨터는 스스로 판단하는 것이 불가능하기에, 사용자가 논리적인 절차인 알고리즘을 컴퓨터에 적용시켰을때 입력값에 따라 출력값을 조정할 수 있도록 해야한다.
알고리즘 설계
원하는 출력값을 얻기 위해서는 그에 맞는 알고리즘을 적용시킬 필요가 있다. 이때 필요한 알고리즘을 구상하는 단계를 알고리즘 설계라고 하며, 설계의 최우선 목표는 정확도, 그 다음이 효율성(Big-O)이다.
설계를 할 때는 바로 코드를 치는 것보다는 의사코드(pseudo code) 혹은 흐름도를 먼저 그리는 것이 좋다. 의사 코드의 틀은 없으며 개개인에 따라 추상적이고 세분화가 가능하다.
알고리즘 구현, 검증, 업데이트
필요한 알고리즘을 제작했다면 사전에 만들어 둔 테스트 케이스를 통해 검증을 진행해야한다. 이후 정확성이 입증되었다고 하더라도, 더 효율적으로 보완할 여지가 있는지 확인하는 과정을 거쳐 하나의 알고리즘을 완성시키는 것이다.
Algorithm Type
정렬 알고리즘
특정 배열이나 콜렉션의 요소들을 오름차순이나 내림차 순으로 정렬시킬 때 사용하는 알고리즘이다. 정렬 별로 Big-O 값이 다르며, 구현방식과 최적화 수준에 따라 성능이 다르다. 따라서 우리는 다양한 알고리즘을 익히고 적재적소에 잘 활용할 필요가 있다.
선택 정렬 : 데이터 중 가장 작은 값부터 하나씩 선택하여 정렬
public static void SelectSort(int[] array)
{
for(int i = 0; i < array.Length - 1; i++)
{
int temp = i;
for (int j = i + 1; j < array.Length; j++)
{
if (array[temp] > array[j])
{
temp = j;
}
}
Swap(array,i,temp);
}
}선택 정렬은 가장 작은 데이터의 인덱스를 보관하고 있다가, 특정 인덱스에 집어넣어 정렬을 시키는 구조이다. 따라서 필요한 논리구조는 가장 작은 데이터를 보관하기 위한 temp 와 for-if 조건문, 인덱스 temp의 요소를 앞에서부터 채워나가는 로직이다.
삽입 정렬 : 데이터를 하나씩 꺼내어 정렬된 자료 중 적합한 위치에 삽입하여 정렬
public static void InsertSort(int[] array)
{
for(int i = 1; i < array.Length; i++)
{
for(int j = i; j > 0; j--)
{
if (array[j] < array[j - 1])
{
Swap(array,j - 1,j);
}
}
}
}삽입 정렬은 이미 정렬된 앞부분과 비교하여, 맞는 위치에 삽입하는 구조로 되어있다. 따라서 필요한 논리구조는 정렬된 앞부분과 비교하는 for-if구문과 값을 교환하는 Swap이다.
버블 정렬 : 인접한 데이터 2개를 비교해서 교체하여 정렬
public static void BubbleSort(int[] array)
{
for (int j = 0; j < array.Length; j++)
{
for (int i = 0; i < array.Length - 1; i++)
{
if (array[i] > array[i + 1])
{
Swap(array,i,i+1);
}
}
}
}버블 정렬은 인덱스 순서에 따라 앞의 데이터와 비교하는 과정을 반복하여 정렬하는 구조로 되어있다. 따라서 필요한 논리구조는 앞의 데이터와 비교하는 if 조건문과 스왑으로 쉽게 구현이 가능하다.
병합 정렬 : 데이터를 2분할하여 정렬 후 병합
By.소현
public static void MergeSort(int[] array)
=> MergeSort(array, 0, array.Length - 1);
public static void MergeSort(int[] array, int start, int end)
{
if(start == end) return;
int mid = (start + end) / 2;
MergeSort(array, start, mid);
MergeSort(array, mid + 1, end);
Merge(array, start, mid, end);
}
public static void Merge(int[] array, int start, int mid, int end)
{
List<int> sortedList = new();
int leftIndex = start;
int rightIndex = mid + 1;
while (leftIndex <= mid && rightIndex <= end)
{
if (array[leftIndex] > array[rightIndex])
{
sortedList.Add(array[rightIndex]);
rightIndex++;
}
else
{
sortedList.Add(array[leftIndex]);
leftIndex++;
}
}
if (rightIndex > end)
{
for (int i = leftIndex; i <= mid; i ++)
{
sortedList.Add(array[i]);
}
}
if (leftIndex > mid)
{
for (int i = rightIndex; i <= end; i ++)
{
sortedList.Add(array[i]);
}
}
for (int i = 0; i<sortedList.Count; i++)
{
array[start + i] = sortedList[i];
}
}병합 정렬은 배열을 절반의 크기로 나누어 각각을 정렬시키고 병합하는 것을 반복하는 구조로 되어있다. 따라서 필요한 논리구조는 배열의 분리, 정렬, 병합이다. 배열의 분리는 MergeSort 함수 내의 재귀구조로 만들고, 정렬과 병합은 Merge 함수에서 구현한다. 정렬은 비교와 함께 List에 옮겨담는 것으로, 병합은 List에서 Array로의 변환과정을 통해 구현했다.
퀵 정렬 : 하나의 기준(피벗)으로 작은 값과 큰 값을 2분할하여 정렬
public static void QuickSort(int[] array) => QuickSort(array, 0, array.Length - 1);
public static void QuickSort(int[] array, int start, int end)
{
if (start >= end) return;
int pivot = start;
int left = pivot + 1;
int right = end;
while(left <= right)
{
while(array[left]<=array[pivot] && left < right)
{
left++;
}
while(array[right]>array[pivot] && left <= right)
{
right--;
}
if(left < right)
{
Swap(array,left,right);
}
else
{
Swap(array,pivot,right);
break;
}
}
QuickSort(array,start,right - 1);
QuickSort(array, right + 1, end);
}퀵 정렬은 배열의 요소를 하나 정해서 기준(피벗)으로 삼고 작은 크기의 요소를 앞쪽으로 큰 크기의 요소를 배열의 뒤쪽으로 배치하여, 피벗을 그 사이에 놓아 다시 앞뒤로 같은 로직을 반복하는 구조로 되어있다. 따라서 필요한 논리 구조는 피벗 설정 및 배치, 피벗을 제외한 양끝 인덱스를 저장하는 것과, 양끝 인덱스를 통해 피벗 기준으로 앙 옆에 데이터를 정렬하는 로직이다.
힙 정렬 : 힙을 이용하여 우선순위가 가장 높은 요소가 가장 마지막 요소와 교체된 후 제거되는 방법을 이용
정렬 알고리즘 비교
| 정렬 종류 | 시간 복잡도(평균) | 시간 복잡도(최악) | 공간 복잡도 | 안정 |
|---|---|---|---|---|
| 선택 정렬 | O(n²) | O(n²) | O(1) | X |
| 버블 정렬 | O(n²) | O(n²) | O(1) | O |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | O |
| 합병 정렬 | O(nlog(n)) | O(nlog(n)) | O(n) | O |
| 퀵 정렬 | O(nlog(n)) | O(n²) | O(log(n)) | X |
| 힙 정렬 | O(nlog(n)) | O(nlog(n)) | O(1) | X |
