정렬 알고리즘 (sorting algorithms)

Selection Sort

#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

void selection_sort(int list[], int n) {
	int i, j, least, temp;
	for(i=0; i<n-1; i++) {
		least = i;
		for(j=i+1; j<n; j++)
			if(list[j] < list[least]) least = j;
		SWAP(list[i], list[least], temp);
	}
}

Insertion Sort

void insertion_sort(int list[], int n) {
	int i, j, key;
	for(i=1; i<n; i++) {
		key = list[i];
		for(j=i-1; j>=0 && list[j]>key; j--)
			list[j+1] = list[j];
		list[j+1] = key;
	}
}

Bubble Sort

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])
				SWAP(list[j], list[j+1], temp);
	}
}

Shell Sort

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];
		for(j=i-gap; j>=first && key<list[j]; j=j-gap)
			list[j+gap] = list[j];
		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++;
		for(i=0; i<gap; i++)
			inc_insertion_sort(list, i, n-1, gap);
	}
}

Merge Sort

int sorted[MAX_SIZE];

void merge(int list[], int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = left;
	int l;

	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];

	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;
		merge_sort(list, left, mid);
		mefge_sort(list, mid+1, right);
		merge(list, left, mid, right);
	}
}

Quick Sort

Time complexity: O(nlog₂n) / Worst case(O(n²))

R code

qs <- function(x) {
	if(length(x) <= 1) return(x)
	pivot <- x[1]
	therest <- x[-1]
	sv1 <- therest[therest < pivot]
	sv2 <- therest[therest >= pivot]
	sv1 <- qs(sv1)
	sv2 <- qs(sv2)
	return (c(sv1,pivot,sv2))
}

C code

#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

void quick_sort(int list[], int left, int right) {
	if(left < right) {
		int q = partition(list, left, right);
		quick_sort(list, left, q-1);
		quick_sort(list, q+1, right);
	}
}

int partition(int list[], int left, int right) {
	int pivot, temp;
	int low, high;

	low = left;
	high = right + 1;
	pivot = list[left];

	do {
		do
			low++;
		while(low <= right && list[low] < pivot);

		do
			high--;
		while(high >= left && list[high] > pivot);

		if(low < high)
			SWAP(list[low], list[high], temp);
	} while(low < high);

	SWAP(list[left], list[high], temp);

	return high;
}

Heap Sort

code

Radix Sort

// 기수 정렬 알고리즘

// LSD(least significant digit): 가장 낮은 자리수

// MSD(most significant digit): 가장 높은 자리수

Radix_Sort(list, n);

for d ← LSD의 위치 to MSD의 위치 do {

d번째 자리수에 따라 0번부터 9번 bucket에 집어놓는다.

bucket에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다.

d++;

}

#define BUCKETS 10
#define DIGITS 4

void radix_sort(int list[], int n) {
	int i, b, d, factor = 1;
	QueueType queues[BUCKETS];

	for(b=0; b<BUCKETS; b++)
		init(&queues[b]);

	for(d=0; d<DIGITS; d++) {
		for(i=0; i<n; i++)
			enqueue(&queues[(list[i]/factor) % 10], list[i]);

		for(b=i=0; b<BUCKETS; b++)
			while(!is_empty(&queues[b]))
				list[i++] = dequeue(&queues[b]);
		factor *= 10;
	}
}

References

• http://moogi.new21.org/src5.htm