Sorting Algorithm

Bubble Sort

void BubbleSort(Data* datas, int length)
{
	for (int i = 0; i < length - 1; i++)
		for (int j = 0; j < length - i - 1; j++)
			if (datas[j].Score > datas[j + 1].Score)
				Swap(datas, j, j + 1);

• 직관적으로 이해하기에 쉽고 구현이 간단하지만 일반적으로 비효율적이다.
• pairwise 비교를 통한 정렬
• O(n^2)

Selecting Sort

void SelectingSort(Data* datas, int length)
{
	for (int i = 0; i < length - 1; i++)
	{
		int minIndex = i;
		for (int j = i + 1; j < length; j++)
			if (datas[j].Score > datas[minIndex].Score) minIndex = j;
		if (minIndex != i) Swap(datas, i, minIndex);
	}
}

• 최솟값을 반복적으로 탐색하여 정렬
• O(n^2)

Insertion Sort

void InsertionSort(Data* datas, int length)
{
	for (int i = 0; i < length - 1; i++)
	{
		if (datas[i - 1].Score > datas[i].Score) continue;
		Data current = datas[i];
		for (int j = 0; j < i; j++)
			if (datas[j].Score > current.Score)
			{
				memmove(&datas[j + 1], &datas[j], sizeof(datas[0]) * (i - j));
				datas[j] = current;
				break;
			}
	}
}

• 데이터의 삽입 위치를 탐색하면서 정렬
• O(n^2)
• 최선의 경우 O(n)

Merge sort

void Merge(Data* datas, int start, int middle, int end)
{
	int left = start;
	int right = middle + 1;
	int destIndex = 0;
	Data* dest = new Data[end - start + 1];
	// 왼쪽 부분 집합과 오른쪽 부분 집합에 대하여 순차적 비교
	while (left <= middle && right <= end)
	{
		if (datas[left].Score < datas[right].Score)
			dest[destIndex++] = datas[left++];
		else
			dest[destIndex++] = datas[right++];
	}
	// 나머지 데이터 그대로 이동
	while (left <= middle)
		dest[destIndex++] = datas[left++];
	//
	while (right <= end)
		dest[destIndex++] = datas[right++];
	//
	destIndex = 0;
	//
	for (int i = start; i <= end; ++i)
		datas[i] = dest[destIndex++];
	delete[] dest;
}
void MergeSort(Data* datas, int start, int end)
{
	if (end - start < 1)
		return;
	int middle = (start + end) / 2;
	MergeSort(datas, start, middle);
	MergeSort(datas, middle + 1, end);
	Merge(datas, start, middle, end);
}

• 데이터 균등 분할 후 합치면서 정렬
• O(n log n)
  
  
• 구현
  • 분할 : 데이터를 균등한 크기를 분할
  • 정복 : 부분 배열의 크기가 충분히 작지 않으면 다시 분할-정복
  • 결합 : 정렬된 부분 배열을 하나로 합친다.

Quick Sort

int Partition(Data* datas, int left, int right)
{
	UINT first = left;
	UINT pivot = datas[first].Score;
	//
	left++;
	while (left <= right)
	{
		while (datas[left].Score <= pivot && left < right)
			left++;
		while (datas[right].Score > pivot && left <= right)
			right--;
		//
		if (left < right)
			Swap(&datas[left], &datas[right]);
		else
			break;
	}
	//
	Swap(&datas[first], &datas[right]);
	//
	return right;
}
void QuickSort(Data* datas, int left, int right)
{
	if (left < right)
	{
		int index = Partition(datas, left, right);
		// 
		QuickSort(datas, left, index - 1);
		QuickSort(datas, index + 1, right);
	}
}

• pivot 을 기준으로 균등형 분할, 병합하며 정렬
• O(n log n)
• 이미 정렬된 데이터에 대해 O(n^2)
  
  
• 구현
  • 분할-정복
    pivot 을 정하여 pivot 보다 작은 데이터는 왼쪽.
    큰 데이터는 오른쪽으로 불균등 분할한다.
    부분 배열의 크기가 충분히 작지 않으면 다시 분할-정복 방법을 적용한다.
  • 결합
    정렬된 부분 배열을 하나로 합친다.