# [資料結構] CH14. Merge, Quick & Radix Sorts

* 續上一次的排序法，這一次要講其他三種比較進階的排序法。

## Merge Sort
* 合併排序法在不同的情形下都擁有非常好的速度，但須要多一倍的空間(buffer)來暫存資料。
* 大致上可以分為三個步驟：
* Divide: 把長度為 n 的 array 分成兩半。
* Conquer: 把左半邊 array 及右半邊 array 分別以 Merge Sort 進行 sorting。 (recursive)
* Combine: merge 左半邊及右半邊 sorted array。
* 也就是將資料分成小資料，並在重組時進行排序的動作。
* 示意圖：
* 
### 範例

digraph merge {
	node[shape=record]
	
    array [label="<f0>39|<f1>9|<f2>81|<f3>45|<f4>90|<f5>27|<f6>72|<f7>18"];
    
}

* 先將資料對半分割至最小。

digraph merge {
	node[shape=record]
	
    array1 [label="<f0>39|<f1>9|<f2>81|<f3>45|<f4>90|<f5>27|<f6>72|<f7>18"];
    array2 [label="<f0>39|<f1>9|<f2>81|<f3>45"];
    array3 [label="<f4>90|<f5>27|<f6>72|<f7>18"];
    array4 [label="<f0>39|<f1>9"];
    array5 [label="<f6>81|<f7>45"];
    array6 [label="<f4>90|<f5>27"];
    array7 [label="<f6>72|<f7>18"];
    
    array1->array2;
    array1->array3;
    array2->array4;
    array2->array5;
    array3->array6;
    array3->array7;
    array4:f0->39;
    array4:f1->9;
    array5:f6->81;
    array5:f7->45;
    array6:f4->90;
    array6:f5->27;
    array7:f6->72;
    array7:f7->18;
}

* 兩個兩個一組合併，合併時進行排序。

digraph merge {
	node[shape=record]
	
    array4 [label="<f0>9|<f1>39"];
    array5 [label="<f6>45|<f7>81"];
    array6 [label="<f4>27|<f5>90"];
    array7 [label="<f6>18|<f7>72"];
    39->array4;
    9->array4;
    81->array5;
    45->array5;
    90->array6;
    27->array6;
    72->array7;
    18->array7;
}

* 一直重覆到合併完所有陣列。

digraph merge {
	node[shape=record]
	array1 [label="<f0>9|<f1>18|<f2>27|<f3>39|<f4>45|<f5>72|<f6>81|<f7>90"];
    array2 [label="<f0>9|<f1>39|<f2>45|<f3>81"];
    array3 [label="<f4>18|<f5>27|<f6>72|<f7>90"];
    array4 [label="<f0>9|<f1>39"];
    array5 [label="<f6>45|<f7>81"];
    array6 [label="<f4>27|<f5>90"];
    array7 [label="<f6>18|<f7>72"];
    array4->array2;
    array5->array2;
    array6->array3;
    array7->array3;
    array2->array1;
    array3->array1;
}

### 如何合併且排序？
* 當你要把A和B兩堆資料合併時，你需要：
* 先開一個新的陣列暫存資料，大小為size(A)+size(B)。
* 宣告兩個計數用變數`countA`、`countB`。
* 用一個forloop跑新的陣列，當`A[countA] > B[countB]`時，將`A[countA]`放入陣列中，並`countA++`；反則對B動作。
* 如果`countA`超過A的範圍了，那就不停放入B的資料；反則放入A。

### 參考用Code

void Merge(int *arr, int begin, int mid, int end, int size)
{
	int *temp = new int[end - begin + 1];
	int i = begin, j = mid + 1;
	for (int index = 0; index < end - begin + 1; index++)
	{
		if (i > mid)
		{
			temp[index] = arr[j];
			j++;
		}
		else if (j > end)
		{
			temp[index] = arr[i];
			i++;
		}
		else if (arr[i] > arr[j])
		{
			temp[index] = arr[j];
			j++;
		}
		else
		{
			temp[index] = arr[i];
			i++;
		}
	}
	for (int i = 0; i < end - begin + 1; i++)
	{
		arr[begin + i] = temp[i];
	}
	delete temp[]; 
}

void MergeSort(int *arr, int begin, int end, int size)
{
	if (begin < end)
	{
		int mid = (begin + end) / 2;
		MergeSort(arr, begin, mid, size);
		MergeSort(arr, mid + 1, end, size);
		Merge(arr, begin, mid, end, size);
	}
}

## Quick Sort
* 快速排序法是相當常見的排序法，雖然某些情況會比Merge Sort差，但不需浪費空間去暫存。
* 其演算法較為複雜，如果看不懂我在打什麼可以看看其他文章XD。
* 步驟大概為：
* 隨便選一個元素當作中心(pivot)。
* 經過神奇演算，可以讓pivot到它排序後應該在哪個位置，並且它左邊的值都比它小，右邊都比它大(但是左右還沒排序完畢)。
* 遞迴處理pivot左邊的和右邊的，直到所有數字都排列完畢。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD>9</TD>
        <TD>4</TD>
        <TD>1</TD>
        <TD>6</TD>
        <TD>7</TD>
        <TD>3</TD>
        <TD>8</TD>
        <TD>2</TD>
        <TD><FONT COLOR="red">5</FONT></TD>
	</TR>
    </TABLE>>];
}

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD>4</TD>
        <TD>1</TD>
        <TD>3</TD>
        <TD>2</TD>
        <TD><FONT COLOR="red">5</FONT></TD>
        <TD>9</TD>
        <TD>8</TD>
        <TD>6</TD>
        <TD>7</TD>
	</TR>
    </TABLE>>];
}

* 示意圖：
* 

### 神奇演算到底做了啥
* 用下面這個當作例子，我們選擇`27`當作`pivot`(用紅色標註)。
* 先在最前面和最後面分別用`left`和`right`紀錄。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD><FONT COLOR="red">27<br/>left</FONT></TD>
        <TD>10</TD>
        <TD>36</TD>
        <TD>18</TD>
        <TD>25</TD>
        <TD>45<br/>right</TD>
	</TR>
    </TABLE>>];
}

* 從`right`開始往左邊掃描，如果`pivot`比`right`小，`right`就往左一格。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD><FONT COLOR="red">27<br/>left</FONT></TD>
        <TD>10</TD>
        <TD>36</TD>
        <TD>18</TD>
        <TD>25<br/>right</TD>
        <TD>45</TD>
	</TR>
    </TABLE>>];
}

* 如果`pivot`比`right`大，就把`pivot`和`right`的值交換。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD>25<br/>left</TD>
        <TD>10</TD>
        <TD>36</TD>
        <TD>18</TD>
        <TD><FONT COLOR="red">27<br/>right</FONT></TD>
        <TD>45</TD>
	</TR>
    </TABLE>>];
}

* 因為剛剛交換了，現在變成從`left`往右邊掃；如果`pivot`大於`left`，`left`就往右邊移一格。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD>25</TD>
        <TD>10</TD>
        <TD>36<br/>left</TD>
        <TD>18</TD>
        <TD><FONT COLOR="red">27<br/>right</FONT></TD>
        <TD>45</TD>
	</TR>
    </TABLE>>];
}

* `pivot`小於`left`，那就和剛剛一樣交換。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD>25</TD>
        <TD>10</TD>
        <TD><FONT COLOR="red">27<br/>left</FONT></TD>
        <TD>18</TD>
        <TD>36<br/>right</TD>
        <TD>45</TD>
	</TR>
    </TABLE>>];
}

* 直接跳到最後結果。一直做到`right`和`left`撞在一起就結束了。
* 你會發現`27`的位置是對的，且左邊都小於`27`，右邊都大於`27`。

digraph structs {
    node [shape=plaintext];

    struct1 [label=<<TABLE>
	<TR>
	    <TD>25</TD>
        <TD>10</TD>
        <TD>18</TD>
        <TD><FONT COLOR="red">27<br/>left<br/>right</FONT></TD>
        <TD>36</TD>
        <TD>45</TD>
	</TR>
    </TABLE>>];
}

### 參考用code

void Partition(int *arr, int begin, int end, int &location)
{
	bool compareR = true;
	while (begin != end)
	{
		if (compareR)
		{
			for (; end > begin; end--)
			{
				if (arr[location] > arr[end])
				{
					compareR = false;
					int temp = arr[end];
					arr[end] = arr[location];
					arr[location] = temp;

					location = end;
					break;
				}
			}
		}
		else
		{
			for (; begin < end; begin++)
			{
				if (arr[location] < arr[begin])
				{
					compareR = true;
					int temp = arr[begin];
					arr[begin] = arr[location];
					arr[location] = temp;

					location = begin;
					break;
				}
			}
		}
	}
}

void QuickSort(int *arr, int begin, int end, int size)
{
	if (begin < end)
	{
		int location = begin;
		Partition(arr, begin, end, location);
		QuickSort(arr, begin, location - 1, size);
		QuickSort(arr, location + 1, end, size);
	}
}

## Radix Sorts
* 基數排序法是將數字根據位數切割成不同的數字，從最低位往上排序，最後就可以得到一個有序數列。
* 沒有示意圖了 ㄎㄎ。
### 不囉嗦上範例
* 利用Radix Sort排序`345` `654` `924` `123` `567` `472`。
* 先只看**個位數**做排序：
* 如果等於就照原本的數列順序。
* 第一次排序結果：`472` `123` `654` `924` `345` `567`。
* 再來只看**十位數**：
* 第二次排序結果：`123` `924` `345` `654` `567` `472`。
* 最後就**百位數**：
* 最後結果：`123` `345` `472` `567` `654` `924`。

### 參考用code
* 這個真的就是參考用，因為這用了太多不必要的東西，效率超慢的XD。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int n;
	int dig = 0;
	string *arr;
	cin >> n;    //共有n個數字
	arr = new string[n];
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		if (arr[i].length() > dig)dig = arr[i].length();
	}
	for (int i = 0; i < n; i++)
	{
		reverse(arr[i].begin(), arr[i].end());

		while (arr[i].length() < dig)
			arr[i].push_back('0');
	}
	for (int i = 0; i < dig; i++)
	{
		if (i != 0)cout << endl;
		vector<string> v[10];
		for (int j = 0; j < n; j++)
		{
			v[arr[j][i]-'0'].push_back(arr[j]);
		}
		int count = 0;
		for (int j = 0; j < 10; j++)
		{
			for (int k = 0; k < v[j].size(); k++)
			{
				arr[count] = v[j][k];
				count++;
			}
		}
		for (int j = 0; j < n; j++)
		{
			if (j != 0)cout << " ";
			string temp = arr[j];
			reverse(temp.begin(), temp.end());
			cout << stoi(temp);
		}
	}
	return 0;
}

###### tags: `DS` `note`