10. 정렬

※ 해당 글은 C언어에 대한 이해를 필요로 합니다. C 언어에 대해 알고 싶으신 분들은 다음 글을 참고하세요

https://ward.tistory.com/category/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20%EC%96%B8%EC%96%B4/C

'프로그래밍 언어/C' 카테고리의 글 목록

(1) 단순한 정렬 알고리즘

 

* 버블 정렬

버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행한다. 비교를 통해 가장 큰 데이터를 배열의 가장 뒤에 위치시키고 해당 과정을 나머지에 대해서 반복한다.

버블 정렬의 구현

void BubbleSort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

버블 정렬의 성능: O(n²)

 

* 선택 정렬

가장 작은 데이터를 찾은 뒤 배열의 첫 번째 요소와 바꾼다. 이 과정을 배열의 나머지에 대해서 해당 과정을 반복한다.

선택 정렬의 구현

void SelSort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int max = i;
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < arr[max])
				max = j;
		}
		int tmp = arr[i];
		arr[i] = arr[max];
		arr[max] = tmp;
	}
}

선택 정렬의 성능: O(n²)

 

* 삽입 정렬

삽입 정렬은 배열을 두 부분으로 나눠서, 정렬 안된 부분의 데이터를 정렬된 부분의 알맞은 위치에 삽입해 가면서 정렬을 진행한다. 이 과정에서 데이트를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾는다.

삽입 정렬의 구현

void InserSort(int arr[], int n) {
	for (int i = 1; i < n; i++) {
		int data = arr[i];
		for (int j = i - 1; j >= 0; j--) {
			if (arr[j] > data) 
				arr[j + 1] = arr[j];
			else {
				arr[j + 1] = data;
				break;
			}
		}
	}
}

선택 정렬의 성능: O(n²)

 

(2) 복잡하지만 효율적인 정렬 알고리즘

 

* 힙 정렬

힙의 루트 노드에 저장된 값이 최댓값인 maxheap의 특성을 이용해서 정렬을 진행한다.

힙 정렬의 구현

#include "Heap.h"

void HeapSort(int arr[], int n, PriorityComp pc)
{
	Heap heap;
	HeapInit(&heap, pc);
    
	for (int i = 0; i < n; i++)
		HInsert(&heap, arr[i]);
	for (int i = 0; i < n; i++)
		arr[i] = HDelete(&heap);
}

힙 정렬의 성능: O(nlogn)

※ 힙에 대한 이해가 부족하신 분들을 다음 글을 참고하세요.

https://ward.tistory.com/33

 

* 병합 정렬

병합 정렬은 분할 정복이라는 알고리즘에 근거하여 만들어진 정렬 방법이다. 배열을 분할한 후 배열을 두 개씩 합치는 과정에서 정렬을 진행한다.

병합 정렬의 구현

#include <stdlib.h>

void Merge(int arr[], int left, int mid, int right) {
	int fIdx = left;
	int rIdx = right;
	int sIdx = left;
	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));

	while (fIdx <= mid && rIdx <= right) {
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];
		sIdx++;
	}
	if (fIdx > mid) {
		for (int i = rIdx; i <= right; i++ + , sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else {
		for (int i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	for (int i = left; i <= right; i++)
		arr[i] = sortArr[i];
	free(sortArr);
}

void MergeSort(int arr[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);
		Merge(arr, left, mid, right);
	}
}

병합 정렬의 성능: O(nlogn)

 

* 퀵 정렬

퀵 정렬

퀵 정렬의 구현

void Swap(int arr[], int idx1, int idx2) {
	int tmp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = tmp;
}

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--;
		if (low <= high)
			Swap(arr, low, high);
	}
	Swap(arr, left, 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);
	}
}

퀵 정렬의 성능: O(nlogn)

 

* 기수 정렬

기수 정렬

0~9 까지의 버킷(큐)에 가장 낮은 자릿수를 보고 데이터를 넣는다. 그 후 버킷에서 데이터를 차례대로 빼고 다음 자릿수에 대해 이 과정을 반복한다.

기수 정렬의 구현

#include "ListBaseQueue.h"

#define BUCKET_NUM 10

void RadixSort(int arr[], int num, int maxLen) {
	Queue buckets[BUCKET_NUM];
	for (int i = 0; i < BUCKET_NUM; i++)
		QueueInit(&buckets[i]);

	for (int i = 0; i < maxLen; i++) {
		int divfac = 1;
		int radix;
		for (int j = 0; j < num; j++) {
			radix = (arr[j] / divfac) % 10;
			Enqueue(&buckets[radix], arr[j]);
		}
		for (int j = 0; j < BUCKET_NUM; j++) {
			int k = 0;
			while (!QIsEmpty(&buckets[j]))
				arr[k++] = Dequeue(&buckets[j]);
		}
		divfac *= 10;
	}
}

기수 정렬의 성능: O(n)

※ 큐에 대한 이해가 부족하신 분들은 다음 글을 참고하세요.

https://ward.tistory.com/22?category=1009919 

 

참조문헌: 윤성우의 열혈 자료구조