정렬 알고리즘은 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다.
대표적으로 버블소트, 힙소트, 머지소트, 퀵소트, 선택 소트,삽입소트,기수 정렬이 있다.
선택 정렬(selection Sort)
현재 값을 기준으로 뒤에 값들을 비교해서 뒷 값이 더 작으면 Swap하는 방식(오름차순 기준)
.
void selectionSort(int *list, const int n)
{
int i, j, indexMin, temp;
for (i = 0; i < n - 1; i++)
{
indexMin = i;
for (j = i + 1; j < n; j++)
{
if (list[j] < list[indexMin])
{
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}
시간 복잡도는 O(n^2)이다. 공간 복잡도는 O(n)
삽입 정렬(Insert Sort)
첫 숫자는 놔두고, 두 번째 자리 숫자부터 뽑아 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣는 정렬
void insertion_sort ( int *data, int n )
{
int i, j, remember;
for ( i = 1; i < n; i++ )
{
remember = data[(j=i)];
while ( --j >= 0 && remember < data[j] ){
data[j+1] = data[j];
data[j] = remember;
}
}
}
void insertion_sort ( int *data, int n )
{
int i, j, remember;
i = n-1;
while ( i-- > 0 )
{
remember = data[(j=i)];
while ( ++j < n && remember > data[j] );
if ( --j == i ) continue;
memcpy ( data+i, data+i+1, sizeof(*data) * (j-i) );
data[j] = remember;
}
}
정렬되는 자료가 단순 데이터일 경우에 memcpy()를 이용하여 자료를 밀어내는 예제이다. memcpy()는 자료를 당겨야하므로 비교를 역순으로 수행한다. 위의 코드보다 25~30% 가량 빠르게 처리된다.
시간 복잡도 O(n^2) ,공간복잡도 O(n)이다. 작은 수에서만 유리하다.
버블소트
매번 연속된 두개의 인덱스를 비교하여 정한 기준의 해당 하는 값을 뒤로 넘기는 방식을 사용한다.
전체 비교를 진행하기에 시간 복잡도는 O(n^2)이다.
int* bubble_sort(int arr[], int n) {
int i, j, temp;
for (i=n-1; i>0; i--) {
for (j=0; j<i; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
힙소트
최대 힙이나 최소 힙을 구성해 정렬하는 방식으로 내림 차순 혹은 오름 차순으로 정렬한다..
이진 트리 방식을 사용하기 때문에 정렬 시에 (n*logn)이 걸린다.
void downheap(int cur, int k)
{
int left, right, p;
while(cur < k) {
left = cur * 2 + 1;
right = cur * 2 + 2;
if (left >= k && right >= k) break;
p = cur;
if (left < k && data[p] < data[left]) {
p = left;
}
if (right < k && data[p] < data[right]) {
p = right;
}
if (p == cur) break;
swap(&data[cur],&data[p]);
cur=p;
}
}
void heapify(int n)
{
int i,p;
for(i = (n-1)/2; i >= 0; i--){
downheap(i,n);
}
//for(i=0;i<size;++i)printf("%d ",data[i]);
//printf("\n");
}
void heap()
{
int k;
heapify(size);
for(k = size-1; k > 0; ){
swap(&data[0],&data[k]);
//k--;
downheap(0,k);
k--;
}
}
머지소트
분할 하여 정복하여 해결 하는 알고리즘의 하나이다.(분할 정복에 대해서는 다른 게시글에서 다시 다루겠다.)
- 분할정복: 문제를 작은 2개의 문제로 분리하고 해결 한 다음 결과를 모아서(Merge) 문제를 해결하는 방법이다.
- 배열을 반으로 분할한다.
- 분할 된 배열을 정렬한다. 만일, 충분히 작지 않으면 재귀를 사용하여 분할한다.
- 정렬된 배열들을 합병한다.
시간 복잡도는 O(n*logn)이다.
/// merge sort range : [low ~ high]
void mergeSort(int A[], int low, int high, int B[]){
// 1. base condition
if(low >= high) return;
// 2. divide
int mid = (low + high) / 2;
// 3. conquer
mergeSort(A, low, mid, B);
mergeSort(A, mid+1, high, B);
// 4. combine
int i=low, j=mid+1, k=low;
for(;k<=high;++k){
if(j > high ) B[k] = A[i++];
else if(i > mid) B[k] = A[j++];
else if(A[i] <= A[j]) B[k] = A[i++];
else B[k] = A[j++];
}
// 5. copy
for(i=low;i<=high;++i) A[i] = B[i];
}
퀵 정렬
피벗이라는 기준 값으로 왼편과 오른 편을 나눠서 정렬한다. 오름 차순을 예로 들면, 왼쪽은 작은 값은 오른 쪽은 큰 값을 배치한다.
퀵 정렬은 자세하게 과정을 살펴보자.(오름 차순 정렬이다.)
해당 상황에서, 왼쪽 끝 지점 , 오른 쪽 끝 지점을 시작으로 각각 왼쪽(피벗 보다 큰),오른쪽( 피벗보다 작은 수)를 찾고 교환 한다.)
왼쪽에서는 9가 발견 되었지만 오른쪽엔 없다 이때는 9와 2를 교환한다. 이로서 2의 자리까지는 확정이다. 피벗을 2 다음 숫자로 바꾸자.
평균적으로 O(n*logn)의 성능을 보이며 O(n*logn)상황 중에서 가장 빠르다. 하지만 최악의 경우O(n^2)까지 나온다.
//퀵정렬
int n,cnt, quick[10000001];
void quickSort(int i, int j)
{
if(i>=j) return;
int pivot = quick[(i+j)/2];
int left = i;
int right = j;
while(left<=right)
{
while(quick[left]<pivot) left++;
while(quick[right]>pivot) right--;
if(left<=right)
{
swap(quick[left],quick[right]);
left++; right--;
}
}
quickSort(i,right);
quickSort(left,j);
}
기수 정렬(radix sort)
자리수를 비교해서 정렬하는 방식. 예시로 파악하는 게 낫다.
우선 0~9까지 queue를 만든다.
[354, 151, 3, 0, 31, 42, 99, 84]
이를 배열로 변환
[0,31,151,42,3,84,354,99]
이를 배열로 변환
[0,3,31,42,151,354,84,99]
이를 배열로 변환
[0,3,31,42,84,99,151,354]
시간 복잡도는 O(dn)이다. 즉, d는 가장 큰 자릿수이다.(여기서는 3)
/**
* @data 정수 배열
* @size data의 정수들의 개수
* @p 숫자의 최대 자리수
* @k 기수(10진법을 사용한다면 10)
*/
void rxSort(int *data, int size, int p, int k) {
int *counts, // 특정 자리에서 숫자들의 카운트
*temp; // 정렬된 배열을 담을 임시 장소
int index, pval, i, j, n;
// 메모리 할당
if ( (counts = (int*) malloc(k * sizeof(int))) == NULL )
return;
if ( (temp = (int*) malloc(size * sizeof(int))) == NULL )
return;
for (n=0; n<p; n++) { // 1의 자리, 10의자리, 100의 자리 순으로 진행
for (i=0; i<k; i++)
counts[i] = 0; // 초기화
// 위치값 계산.
// n:0 => 1, 1 => 10, 2 => 100
pval = (int)pow((double)k, (double)n);
// 각 숫자의 발생횟수를 센다.
for (j=0; j<size; j++) {
// 253이라는 숫자라면
// n:0 => 3, 1 => 5, 2 => 2
index = (int)(data[j] / pval) % k;
counts[index] = counts[index] + 1;
}
// 카운트 누적합을 구한다. 계수정렬을 위해서.
for (i=1; i<k; i++) {
counts[i] = counts[i] + counts[i-1];
}
// 카운트를 사용해 각 항목의 위치를 결정한다.
// 계수정렬 방식
for (j=size-1; j>=0; j--) { // 뒤에서부터 시작
index = (int)(data[j] / pval) % k;
temp[counts[index] -1] = data[j];
counts[index] = counts[index] - 1; // 해당 숫자 카운트를 1 감소
}
// 임시 데이터 복사
memcpy(data, temp, size * sizeof(int));
}
free(counts);
free(temp);
}//적용안됨
전체 시간 복잡도
'Tech.log > 알고리즘' 카테고리의 다른 글
| [Fibonacci에서의 세 가지(Recursion, Dynamic Programming,Bottom-Up Approach] (0) | 2021.05.30 |
|---|---|
| [DFS와 BFS의 차이] (0) | 2021.05.30 |
| [Stable Sort(안정 정렬) vs Unstable Sort(불안정 정렬)] (0) | 2021.05.29 |
| [꼬리 재귀(Tail Recursion)] (0) | 2021.05.18 |
| [BigO표기법이란] (0) | 2021.05.11 |
댓글