[ C# ] 정렬 _ 1
우리는 원하는 데이터를 빠르게 탐색할 때, 정렬을 사용한다.
만약 데이터가 정렬되지 않았다면 일일히 순차적으로 탐색해야 하지만
정렬된 데이터의 경우 이진 트리 탐색 알고리즘을 이용하여 쉽게 탐색할 수 있다.
이진 트리 탐색
비교하고자 하는 값보다 크면 오른쪽, 작으면 왼쪽으로 이동하며 원하는 값이 나타날때까지 탐색하는 방식
정렬 알고리즘_기초편
1. 버블 정렬
가장 쉽지만 최악의 효율성을 가지고 있는 알고리즘.
전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목의 위치를 교환한다.
(인접한 두개의 항목을 비교)
도중에 정렬이 완료되었어도 모든 배열을 순회할때까지 종료되지 않는다.
구현 형식
int[] BubbleSort(int[] array)
{
//배열의 모든 요소를 탐색
for(int i=0; i<array.Length; i++)
{
//각 반복에서 가장 큰 요소가 맨뒤에 이동하므로
//끝 인덱스는 감소하여 반복 횟수를 줄임
for(int k=0; k<array.Length-1-i;k++)
{
//현재 요소와 다음 요소를 비교하여 정렬이 필요한 경우
if(array[k] > array[k+1])
{
//두 요소의 위치를 교환
Swap(array,k,k+1);
}
}
}
return array;
}2. 선택 정렬
가장 작은(큰) 항목을 찾은 뒤 현재의 위치와 교환하는 정렬 방식.
(교환이 완료되면 다음 위치로 이동한다.)
버블 정렬보다 상대적으로 빠르지만 다른 알고리즘에 비하면 느려서 많이 사용되지 않는다.
구현 형식
int[] SelectionSort(int[] array)
{
for(int i=0; i<array.Length; i++)
{
//최솟값의 인덱스를 저장하는 변수
int min = i;
//현재 인덱스(i)부터 배열 끝까지의 요소를 비교하여 최솟값을 찾음
for(int k=i+1; k<array.Length; k++)
{
//최솟값을 찾았을 때 해당 인덱스를 min에 저장
if(array[k] < array[min])
{
min = k;
}
}
//현재 인덱스와 최솟값의 인덱스가 다르면 둘의 위치를 교환
if( i != min)
{
Swap(array, i, i+1);
}
}
return array;
}3. 삽입 정렬
모든 항목들을 앞에서부터 비교하여 자신의 위치를 찾아 삽입하는 정렬 방식
(오름차순 정렬)
자료의 수가 적거나 이미 정렬되어 있는 경우에 매우 효율적이지만
교환이 아닌 리코드들을 이동시켜 정렬하는 방식이기 때문에 데이터의 양이 방대한 경우에 적합하지 않다.
구현 방식
int[] InsertSort(int[] array)
{
for(int i=0; i<array.Length; i++)
{
//비교할 인덱스
int compareIndex = i;
//해당 인덱스를 기준으로 0으로 내려가며 크기를 비교
for(int k=i-1; k>=0; k--)
{
//비교 인덱스가 더 작으면 둘의 위치를 교환한다.
if(array[comapreIndex] < array[k])
{
Swap(array, compareIndex, k);
{
}
}
return array
}정렬 알고리즘_ 분할 정복
큰 문제를 작은 하위 문제들로 분할하여 각각의 문제를 해결하고 그 결과들을 모아 본래의 문제 해결 방식을 얻는 방법.
알고리즘 순서
1. 분할 : 원래의 문제를 작은 하위 문제들로 분할
ㄴ> 보통 재귀적인 방법으로 이루어지고 원래의 문제를 해결하기 위하여 여러 하위 문제로 분할된다.
(재귀 함수를 사용하여 구현한다.)
2. 정복 : 각 하위의 문제들을 재귀적으로 해결
ㄴ> 하위 문제들의 크기가 충분히 작아서 직접 해결할 수 있는 경우에 해당된다.
3. 결합 : 각 하위 문제의 해답을 결합하여 원래 문제의 해답을 얻는다.
ㄴ> 이 단계에서는 분할된 하위 문제들의 해답을 조합하여 전체 문제의 해답을 생성한다.
구현 알고리즘
- 퀵 정렬
- 힙 정렬
- 병합 정렬 등등...
1. 퀵 정렬
주어진 배열을 특정 pivot 값을 기준으로 두개의 서브 배열로 분할하고,
각 서브 배열을 재귀적으로 정렬하여 최종적으로 정렬된 배열을 얻는 알고리즘
- 퀵 정렬의 핵심은 주어진 pivot 값을 기준으로 작은 값은 왼쪽, 큰값은 오른쪽으로 나누어 정렬하는 방식이다.
void QuickSort(int[] arr)
{
//배열의 전체 범위를 대상으로 퀵 정렬
QuickSortHelper(arr,0,arr.Length-1);
}
void QuickSortHelper(int[] arr, int left, int right)
{
while(left < right)
{
//배열을 분할하고 분할 인덱스를 반환받음
int partitionIndex = Partition(arr,left,right);
//분할된 배열의 왼쪽 부분에 대해 재귀적으로 정렬 수행
if(partitionIndex - left < right - partitionIndex)
{
QuickSortHelper(arr, left, partitionIndex -1);
left = partitionIndex +1;
}
else
{
QuickSortHelper(arr, partitionIndex +1, right);
right = partitionIndex -1;
}
}
}
//배열을 분할하고 분할 인덱스를 반환하는 녀석
int Partition(int[] arr, int left, int right)
{
//중간값을 피벗으로 설정
int piviotIndex = (left+right)/2;
int piviotValue = arr[piviotIndex];
/*
배열을 순회하면서 피벗보다 작은 값을 찾아내고 피벗보다 큰값을 교환
피벗의 왼쪽에는 피벗보다 작은 값들이, 오른쪽에는 피벗보다 큰 값이 위치
마지막으로 피벗을 올바른 위치로 이동시키고 그 위치를 리턴
*/
//피벗의 값을 가장 오른쪽에 있는 값과 위치 교환
Swap(arr, piviotIndex, right);
//배열을 순회하며 피벗보다 작은 값들을 저장할 인덱스
int storeIndex = left;
for(int i=left; i<right; i++)
{
//현재 값이 피벗의 값보다 작으면 해당 값을 storeIndex에 위치한 값과 교환
if(arr[i] < piviotValue)
{
Swap(arr, i, storeIndex);
}
}
//본래 피벗의 값을 올바른 위치로 이동
Swap(arr, storeIndex, right);
return storeIndex;
}나머지 정렬들은 다음 페이지에서 다루도록 하겠다.