버블 정렬(Bubble Sort)
인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식
정렬순서상 위치가 바뀌어야 하면 두 데이터의 위치를 바꿔나간다.
오름차순으로 정렬할 경우엔 정렬의 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보낸다.
코드 구현
#include <stdio.h>
void BubbleSort(int arr[], int n)
{
int i, j;
int temp;
for(i=0; i<n-1; i++)
{
for(j=0; j<(n-i)-1; j++)
{
if(arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main(void)
{
int arr[4] = {3, 2, 4, 1};
int i;
BubbleSort(arr, sizeof(arr)/sizeof(int));
for(i=0; i<4; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}1 2 3 4
선택 정렬(Selection Sort)
정렬순서에 맞게 하나씩 선택해서 옮기고, 그러면서 정렬이 되게 하는 알고리즘
정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다.
코드 구현
#include <stdio.h>
void SetSort(int arr[], int n)
{
int i, j;
int maxIdx;
int temp;
for(i=0; i<n-1; i++)
{
maxIdx = i;
for(j=i+1; j<n; j++)
{
if(arr[j] < arr[maxIdx])
maxIdx = j;
}
temp = arr[i];
arr[i] = arr[maxIdx];
arr[maxIdx] = temp;
}
}
int main(void)
{
int arr[4] = {3, 4, 2, 1};
int i;
SetSort(arr, sizeof(arr) / sizeof(int));
for(i = 0; i < 4; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}1 2 3 4
삽입 정렬(Insertion Sort)
정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬대상
삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다.
대부분이 이미 정렬되어 있는 경우 매우 빠르게 동작
코드 구현
#include <stdio.h>
void InsertSort(int arr[], int n)
{
int i, j;
int insData;
for(i = 1; i < n; i++)
{
insData = arr[i];
for(j = i - 1; j >= 0; j--)
{
if(arr[j] > insData)
arr[j+1] = arr[j];
else
break;
}
arr[j+1] = insData;
}
}
int main(void)
{
int arr[5] = {5, 3, 2, 4, 1};
int i;
InsertSort(arr, sizeof(arr) / sizeof(int));
for(i = 0; i < 5; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}1 2 3 4 5
힙 정렬(Heap Sort)
힙의 루프 노드에 저장된 값이 정렬순서상 가장 앞선다는 것을 활용하여 정렬
코드 구현
#include "UsefulHeap.h"
#include <stdio.h>
int PriComp(int n1, int n2)
{
return n2 - n1;
}
void HeapSort(int arr[], int n, PriorityComp pc)
{
Heap heap;
int i;
HeapInit(&heap, pc);
// 정렬대상을 가지고 힙 구성
for(i = 0; i < n; i++)
HInsert(&heap, arr[i]);
// 순서대로 하나씩 꺼내서 정렬 완성
for(i = 0; i < n; i++)
arr[i] = HDelete(&heap);
}
int main(void)
{
int arr[4] = {3, 4, 2, 1};
int i;
HeapSort(arr, sizeof(arr) / sizeof(int), PriComp);
for(i = 0; i < 4; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}1 2 3 4
병합 정렬(Merge Sort)
분할 정복(divide and conquer)이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법
1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할
2단계 정복(Conquer) - 해결이 용이한 수준까지 분할된 문제를 해결
3단계 결합(Combine) - 분할해서 해결한 결과를 결합하여 마무리
기본 원리는 "8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고, 또 이를 각각 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다"
코드 구현
#include <stdio.h>
#include <stdlib.h>
void MergeTwoArea(int arr[], int left, int mid, int right)
{
int fIdx = left;
int rIdx = mid+1;
int i;
int * sortArr = (int*)malloc(sizeof(int)*(right+1));
int sIdx = left;
while(fIdx <= mid && rIdx <= right)
{
if(arr[fIdx] <= arr[rIdx])
sortArr[sIdx] = arr[fIdx++];
else
sortArr[sIdx] = arr[rIdx++];
sIdx++;
}
if(fIdx > mid)
{
for(i = rIdx; i <= right; i++, sIdx++)
sortArr[sIdx] = arr[i];
}
else
{
for(i = fIdx; i <= mid; i++, sIdx++)
sortArr[sIdx] = arr[i];
}
for(i = left; i <= right; i++)
arr[i] = sortArr[i];
free(sortArr);
}
void MergeSort(int arr[], int left, int right)
{
int mid;
if(left < right)
{
// 중간 지점을 계산
mid = (left+right) / 2;
// 둘로 나눠서 각각을 정렬
MergeSort(arr, left, mid);
MergeSort(arr, mid+1, right);
// 정렬된 두 배열 병합
MergeTwoArea(arr, left, mid, right);
}
}
int main(void)
{
int arr[8] = {3, 2, 4, 1, 7, 6, 5};
int i;
// 배열 arr의 전체 영역 정렬
MergeSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
for(i = 0; i < 7; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}0 1 2 3 4 5 6 7
퀵 정렬(Quick Sort)
코드 구현
#include <stdio.h>
void Swap(int arr[], int idx1, int idx2)
{
int temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
int Partition(int arr[], int left, int right)
{
int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽!
int low = left + 1;
int high = right;
while (low <= high) // 교차되지 않을 때까지 반복
{
while (pivot > arr[low])
low++;
while (pivot < arr[high])
high--;
/*
while(pivot >= arr[low] && low <= right)
low++;
while(pivot <= arr[high] && high >= (left+1))
high--;
*/
if (low <= high) // 교차되지 않은 상태라면 Swap 실행
Swap(arr, low, high); // low와 high가 가리키는 대상 교환
}
Swap(arr, left, high); // 피벗과 high가 가리키는 대상 교환
return high; // 옮겨진 피벗의 위치 정보 반환
}
void QuickSort(int arr[], int left, int right)
{
if (left <= right)
{
int pivot = Partition(arr, left, right); // 둘로 나눠서
QuickSort(arr, left, pivot - 1); // 왼쪽 영역을 정렬
QuickSort(arr, pivot + 1, right); // 오른쪽 영역을 정렬
}
}
int main(void)
{
int arr[7] = {3, 2, 4, 1, 7, 6, 5};
int len = sizeof(arr) / sizeof(int);
int i;
QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
for(i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}1 2 3 4 5 6 7
기수 정렬
코드 구현
#include <stdio.h>
#include "ListBaseQueue.h"
#define BUCKET_NUM 10
// num은 정렬의 수
// maxLen은 정렬할 대상의 최대길이
void RadixSort(int arr[], int num, int maxLen)
{
// 매개변수 maxLen에는 정렬대상 중 가장 긴 데이터의 길이 정보가 전달
Queue buckets[BUCKET_NUM];
int bi;
int pos;
int di;
int divfac = 1;
int radix;
// 총 10개의 버킷 초기화
for (bi = 0; bi < BUCKET_NUM; bi++)
QueueInit(&buckets[bi]);
// 가장 긴 데이터의 길이만큼 반복
for (pos = 0; pos < maxLen; pos++)
{
// 정렬대상의 수만큼 반복
for (di = 0; di < num; di++)
{
// N번째 자리의 숫자 추출
radix = (arr[di] / divfac) % 10;
// 추출한 숫자를 근거로 버킷에 데이터 저장
Enqueue(&buckets[radix], arr[di]);
}
// 버킷 수만큼 반복
for (bi = 0, di = 0; bi < BUCKET_NUM; bi++)
{
// 버킷에 저장된 것 순서대로 다 꺼내서 다시 arr에 저장
while (!QIsEmpty(&buckets[bi]))
arr[di++] = Dequeue(&buckets[bi]);
}
// N번째 자리의 숫자 추출을 위한 피제수의 증가
divfac *= 10;
}
}
int main()
{
int arr[7] = {13, 212, 14, 7141, 10987, 6, 15};
int len = sizeof(arr) / sizeof(int);
int i;
RadixSort(arr, len, 5);
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
return 0;
}
댓글 없음:
댓글 쓰기