버블 정렬(Bubble Sort)
- 서로 인접한 두 원소를 검사하여 정렬
- 인접한 2개가 순서대로 되어 있지 않으면 교환.
- 인접한 2개가 순서대로 되어 있지 않으면 교환.
void bubble_sort(int list[], int n)
{
int i, j, temp;
for(i = n - 1; i > 0; i --)
{
for(j = 0; j < i; j++)
{
if(list[j]>list[j+1])
{
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}선택 정렬(Selection Sort)
- 제자리 정렬(in-place sorting) 알고리즘
- 입력 배열 이외 다른 추가 메모리를 요구하지 않음
- 주어진 배열에서 최솟값을 선택, 그 값과 맨 앞의 위치 값과 교체한다.
- 교체된 맨 앞의 위치를 제외한 뒷 부분의 배열도 1번과 같은 처리를 반복한다.
- 하나의 원소만 남게 되면 종료한다.
void selection_sort(int list[], int n)
{
int i, j, least;
for(i = 0; i < n-1; i++) //마지막 숫자는 자동정렬
{
least = i;
for(j = i + 1; j < n; j++)
{
if(list[j]<list[least])
least = j;
}
if(i != least) //최솟값이 자기 자신이면 이동 X
{
swap(list[i], list[least]);
}
}
}삽입 정렬(Insertion Sort)
- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입
- 두 번째 원소부터 시작하여 그 앞 원소들과 비교하여 삽입할 위치를 지정.
- 두번째라면 첫번째자료와 비교
- 세번째라면 두번째, 첫번째와 비교
- 네번째라면 세번째, 두번째, 첫번째와 비교
- ...
- 원소가 삽입될 위치를 찾았다면 그 위치 확보를 위해 원소의 위치를 한 칸씩 뒤로 이동
- 처음 Key값은 두번째 자료부터 시작 (첫번째는 의미가 없음)
장점
- 안정한 정렬 방법
- 레코드 수가 적을 경우 유리
- 대부분의 레코드가 이미 정렬된 경우 효율적
단점
- 비교적 많은 레코드들의 이동
- 레코드 크기가 클 경우 부적합
void insertion_sort(int list[], int n){
int i, j, key;
// 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
for(i=1; i<n; i++){
key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
// 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
// j 값은 음수가 아니어야 되고
// key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
for(j=i-1; j>=0 && list[j]>key; j--){
list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
}
list[j+1] = key;
}
}
셸 정렬(Shell Sort)
- 삽입 정렬 보완 알고리즘
- 삽입 정렬이 이미 어느정도 정렬된 배열에 대해서는 효율적인 것에서 착안
- 삽입 정렬 문제: 요소들이 삽입될 때, 이웃한 위치로만 이동
- 셸 정렬의 차이: 전체의 리스트를 한 번에 정렬하지 않는다.
- 정렬해야 할 리스트를 특정 기준에 따라 분류
- 비연속적인 여러 개의 부분 리스트 생성
- 각 부분 리스트를 삽입 정렬을 통해 정렬
- 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후 알고리즘 반복
- 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복
구체적 개념
- 정렬해야 할 리스트의 k번째 요소를 추출하여 부분 리스트 생성
- k: 간격(gap)
- k의 초기값: (정렬할 원소 수)/2
- 생성된 부분 리스트의 개수는 gap과 같다
- 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다.
- 간격은 홀수로 하는 것이 좋다.
- 간격을 절반으로 줄일 때 짝수가 나오면 +1 을 해서 홀수로 만든다.
- 간격 k가 1이 될 때까지 반복
// gap만큼 떨어진 요소들을 삽입 정렬
// 정렬의 범위는 first에서 last까지
void inc_insertion_sort(int list[], int first, int last, int gap){
int i, j, key;
for(i=first+gap; i<=last; i=i+gap){
key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
// 현재 정렬된 배열은 i-gap까지이므로 i-gap번째부터 역순으로 조사한다.
// j 값은 first 이상이어야 하고
// key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+gap번째로 이동
for(j=i-gap; j>=first && list[j]>key; j=j-gap){
list[j+gap] = list[j]; // 레코드를 gap만큼 오른쪽으로 이동
}
list[j+gap] = key;
}
}
// 셸 정렬
void shell_sort(int list[], int n){
int i, gap;
for(gap=n/2; gap>0; gap=gap/2){
if((gap%2) == 0)(
gap++; // gap을 홀수로 만든다.
)
// 부분 리스트의 개수는 gap과 같다.
for(i=0; i<gap; i++){
// 부분 리스트에 대한 삽입 정렬 수행
inc_insertion_sort(list, i, n-1, gap);
}
}
}
퀵 정렬(Quick Sort)
- 불안정 정렬
- 비교 정렬(다른 원소와의 비교만으로 정렬 수행)
- 분할 정복 알고리즘
- 매우 빠른 수행 속도
- 피벗(pivot) 요소를 선택한다.
- 피벗을 기준으로 피벗보다 작으면 왼쪽 / 피벗보다 크면 오른쪽 이동
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬
- 분할된 부분 리스트에 대하여 순환 호출을 이용하여 정렬을 반복
- 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
- 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
- 리스트의 크기가 0이나 1이 될 때까지 반복
Divde -> Conquer -> Combine
- Divide: 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할
- Conquer: 부분 배열을 정렬, 부분 배열의 크기가 충분히 작지 않으면 순환 호출
- Combine: 정렬된 부분 배열들을 하나의 배열에 합병
순환 호출이 한 번 진행될 때마다 최소한 하나의 원소(피벗)은 최종적으로 위치가 정해지므로 이 알고리즘은 반드시 끝난다는 것을 보장 가능
장점
- 속도가 빠르다
- 추가 메모리 공간을 필요로 하지 않는다.
단점
- 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 걸린다.
- 피벗을 선택할 때 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.
int partition(int[] list, int left, int right)
{
int pivot, temp;
int low, high;
low = left;
high = right;
pivot = list[left];
while (low < high)
{
while (low <= right && list[low] < pivot)
{
low++;
}
while (high >= left && list[high] > pivot)
{
high--;
}
if (low < high)
{
temp = list[low];
list[low] = list[high];
list[high] = temp;
if (list[low] == list[high])
high--;
}
}
return high;
}
void quickSort(int[] list, int left, int right)
{
if(left < right)
{
int q = partition(list, left, right);
quickSort(list, left, q - 1);
quickSort(list, q + 1, right);
}
}
병합 정렬(Merge Sort)
- 안정 정렬
- 분할 정복
- 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
- 그게 아니라면 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
- 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
- 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
Divide -> Conquer -> Combine
- Divide : 입력 배열을 같은 크기의 2개 부분 배열로 분할
- Conquer: 부분 배열을 정렬한다. 부분 배열 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 방법을 적용.
- Combine: 정렬된 부분 배열들을 하나의 배열에 합병
장점
- 안정적인 정렬 방법
- 데이터의 분포에 영향을 덜 받는다.
- 레코드가 연결 리스트라면 데이터의 이동이 작아진다. (제자리 정렬로 구현 가능)
단점
- 레코드를 배열로 구성하면 임시 배열이 필요하다. (not 제자리 정렬)
// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
/* (실제로 숫자들이 정렬되는 과정) */
void merge(int list[], int left, int mid, int right){
int i, j, k, l;
i = left;
j = mid+1;
k = left;
/* 분할 정렬된 list의 합병 */
while(i<=mid && j<=right){
if(list[i]<=list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
// 남아 있는 값들을 일괄 복사
if(i>mid){
for(l=j; l<=right; l++)
sorted[k++] = list[l];
}
// 남아 있는 값들을 일괄 복사
else{
for(l=i; l<=mid; l++)
sorted[k++] = list[l];
}
// 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
for(l=left; l<=right; l++){
list[l] = sorted[l];
}
}
// 합병 정렬
void merge_sort(int list[], int left, int right){
int mid;
if(left<right){
mid = (left+right)/2 // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
merge_sort(list, mid+1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
}
}
힙 정렬(Heap Sort)
- 최대 힙 트리나 최소 힙 트리를 구성해 정렬
- 내림차순 정렬: 최대 힙
- 오름차순 정렬: 최소 힙
- 정렬해야 할 n개의 요소들로 완전 이진 트리 형태를 만든다.
- 그 다음 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장
- 삭제되는 요소들은 값이 감소되는 순서로 정렬되게 된다.
장점
- 시간 복잡도가 좋은 편
- 가장 큰 값 몇개만 필요할 때 유용
static void heapSort(int[] arr) {
int i, temp, length = arr.Length;
for(i=length/2-1; i>=0; i--) heapHeapify(arr, length, i);
for(i=length-1; i>=0; i--) {
temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
heapHeapify(arr, i, 0);
}
}
static void heapHeapify(int[] arr, int length, int i) {
int left = 2*i + 1, right = 2*i + 2;
int temp, largest = i;
if( left<length && arr[left]>arr[largest]) largest = left;
if( right<length && arr[right]>arr[largest]) largest = right;
if( largest != i ) {
temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
heapHeapify(arr, length, largest);
}
}기수 정렬(Radix Sort)
- 기수 별로 비교 없이 수행하는 정렬 알고리즘
- 버킷 정렬
계수 정렬(Count Sort)
- 정렬되지 않은 배열의 수들이 몇 번 나왔는지 적어둔다.
- 몇 번 나왔는지 기록한 배열의 앞으로 순회하여 자신이 정렬된 배열에서 몇 번째에 나와야 하는지 기록(count)
- 몇 번째에 나와야 하는지 기록한 배열의 맨 마지막 값부터 순회하여 정렬 배열에 값을 써둔다.(sum)
- 값을 쓸 때, count 배열과 sum 배열의 값을 하나씩 줄이고 0이 될 때까지 반복
static int[] CountSort(int[] list, int n)
{
int[] cnt = new int[10001];
int[] ans = new int[10001];
for (int i = 0; i < n; i++) cnt[list[i]]++;
for (int i = 1; i <= 10000; i++) cnt[i] += cnt[i - 1];
for(int i = n-1; i >= 0; i--)
{
int target = list[i];
ans[cnt[target] - 1] = target;
cnt[target]--;
}
return ans;
}
정렬탈트붕괴
Reference
heejeong Kwon
위키백과
곰을 좋아합니다. <a href = "https://github.com/RudinP">github</a>