Quick Sort / Merge Sort

[ Quick Sort ]

- 이미 정렬되어있는 경우 O(N^2) 알고리즘이 됨에 유의

#include <stdio.h>
#include <memory>
using namespace std;

void swap(int input[], int a, int b)
{
	int temp = input[a];
	input[a] = input[b];
	input[b] = temp;
}

int partition(int input[], int low, int high)
{
	int index = low;

	for (int i = low; i < high; i++) // 여기서 high를 일단 pivot으로 보고있으므로 high는 빠져야한다.
	{
		if (input[i] <= input[high])
		{
			swap(input, i, index);
			index++;
		}
	}

	swap(input, index, high);
	return index;
}

void qsort2(int input[], int low, int high)
{
	if (low >= high) return;

	int pivot = partition(input, low, high);

	qsort2(input, low, pivot - 1);
	qsort2(input, pivot + 1, high);
}

int main(void)
{
	int input[10];
	
	for (int i = 0; i < 10; i++) scanf("%d", &input[i]);

	qsort2(input, 0, 9);

	for (int i = 0; i < 10; i++) printf("%d\n", input[i]);

	return 0;
}

[ Merge Sort ]

- Stable Sort 정렬 알고리즘 중에 하나이다. 정렬할 배열의 원소가 같은 값을 갖는 경우 그 둘의 순서가 바뀌지 않는 경우 Stable Sort라고 한다.

#include <stdio.h>
#define MAX_DATA_SIZE 1000000

int data[MAX_DATA_SIZE] = { 0 };
int tempData[MAX_DATA_SIZE] = { 0 };

void merge(int start, int end)
{
	register int i = start;
	register int mid = (start + end) / 2;
	register int j = mid + 1;
	register int k = 0;

	while (i <= mid && j <= end)
	{
		if (data[i] <= data[j]) tempData[k++] = data[i++];
		else tempData[k++] = data[j++];
	}

	while (i <= mid) tempData[k++] = data[i++];
	while (j <= end) tempData[k++] = data[j++];

	for (register int i = start; i <= end; i++)
		data[i] = tempData[i - start];
}

void mergeSort(int start, int end)
{
	if (start == end) return;
	int mid = (start + end) / 2;
	mergeSort(start, mid);
	mergeSort(mid + 1, end);
	merge(start, end);
}

int main(void)
{
	int N;
	scanf("%d", &N);

	for (register int i = 0; i < N; i++) scanf("%d", &data[i]);
	mergeSort(0, N - 1);
	for (register int i = 0; i < N; i++) printf("%d\n", data[i]);

	return 0;
}