#자료구조와 함께 배우는 알고리즘 입문 C언어편 - 7

06-3 단순 선택 정렬

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

void selection(int a[], int n)
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		int min = i;
		for (j = i + 1; j < n; j++)
		{
			if (a[j] < a[min])
			{
				min = j;
			}
		}
		swap(a[i], a[min]);
	}
}

 

06-4 단순 삽입 정렬

선택한 요소를 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘

장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빠르다.

단점 : 삽입할 위치가 멀리 떨어져있으면 이동(대입)해야 하는 횟수가 많아진다. (느리다)

void insertion(int a[], int n)
{
	int i, j;
	for (i = 1; i < n; i++)
	{
		int tmp = a[i];
		for (j = i; j > 0 && a[j - 1] > tmp; j--)
		{
			a[j] = a[j - 1];
		}
		a[j] = tmp;
	}
}

 

06-5 셸 정렬

정렬할 배열릐 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 알고리즘

void shell(int a[], int n)
{
	int i, j, h;
	for (h = n / 2; h > 0; h /= 2)
	{
		for (i = h; i < n; i++)
		{
			int tmp = a[i];
			for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
			{
				a[j + h] = a[j];
			}
			a[j + h] = tmp;
		}
		
	}
}

 

06-6 퀵 정렬

가장 빠른 정렬 알고리즘

#define swap(x, y) do { int t = x; x = y; y = t;}while(0)

void quick(int a[], int left, int right)
{
	int pl = left;
	int pr = right;
	int x = a[(pl + pr) / 2];
	do
	{
		while (a[pl] < x)
			pl++;
		while (a[pr] > x)
			pr--;
		if (pl <= pr)
		{
			swap(a[pl], a[pr]);
			pl++;
			pr--;
		}
	} while (pl <= pr);
	if (left < pr) quick(a, left, pr);
	if (right < pl) quick(a, pl, right);
}

 

06-7 병합 정렬

배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘

static int* buff;
static void _mergesort(int a[], int left, int right)
{
	if (left < right)
	{
		int center = (left + right) / 2;
		int p = 0;
		int i;
		int j = 0;
		int k = left;
		_mergesort(a, left, center); // 앞부분에 대한 병합 정렬
		_mergesort(a, center + 1, right); // 뒷부분에 대한 병합 정렬
		for (i = left; i <= center; i++)
		{
			buff[p++] = a[i];
		}
		while (i <= right && j < p)
			a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
		while (j < p)
			a[k++] = buff[j++];
	}
}

int mergesort(int a[], int n)
{
	if ((buff = (int*)calloc(n, sizeof(int))) == NULL)
	{
		return -1;
	}
	_mergesort(a, 0, n - 1); // 배열 전체를 병합 정렬
	free(buff);
	return 0;
}

 

06-8 힙 정렬

힙이란?

부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 이진트리 (부모의 값이 자식보다 항상 작아도 성립됨)

힙 정렬

가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘

static void downheap(int a[], int left, int right)
{
	int tmp = a[left]; // 루트
	int child;
	int parent;
	for (parent = left; parent < (right + 1) / 2; parent = child)
	{
		int cl = parent * 2 + 1; // 왼쪽 자식
		int cr = cl + 1; // 오른쪽 자식
		child = (cr <= right && a[cr] > a[cl]) ? cr : cl; // 큰 값은?
		if (tmp >= a[child])
			break;
		a[parent] = a[child];
	}
	a[parent] = tmp;
}

void heapsort(int a[], int n)
{
	int i;
	for (i = (n - 1) / 2; i >= 0; i--)
	{
		downheap(a, i, n - 1);
	}
	for (i = n - 1; i > 0; i--)
	{
		swap(a[0], a[i]);
		downheap(a, 0, i - 1);
	}
}

 

06-9 도수 정렬

요소의 대소 관계"를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘

void fsort(int a[], int n, int max)
{
	int i;
	int* f = (int*)calloc(max + 1, sizeof(int));
	int* b = (int*)calloc(n, sizeof(int));

	for(i = 0; i <= max; i++) f[i] = 0;
	for (i = 0; i < n; i++) f[a[i]]++;
	for (i = 1; i <= max; i++) f[i] += f[i - 1];
	for (i = n - 1; i >= 0; i--) b[--f[a[i]]] = a[i];
	for (i = 0; i < n; i++) a[i] = b[i];

	free(b);
	free(f);
}