Sorting

這篇的主題主要是針對多筆資料的同時排序。
這樣說也許不太確切吧，比方說，現在有五十個人分別從1編到50號，並給每個人的身長，求以高矮順序排列的座號。
這時候該怎麼寫？

由於C的qsort和C++的sort都只能排一個一維陣列，像這種排序的同時要保留其他資訊的位置時^[?]，也許有人的做法是建立兩個陣列，一個放身高，另一個放座號，然後自己寫一個sorting function。
不過這樣好像有點麻煩，因為quick sort實在是很煩，bubble有夠慢，而且又有現成的函式可用，像這種問題要怎麼解決？

其實用簡單的資料結構就可以漂亮地解決。
以上述問題為例：

// C version:
typedef struct Prop
{
 double height;
 unsigned int index;
}Prop;
typedef struct Array
{
 Prop *content;
 unsigned int size;
}Array;
// C++ version:
struct Prop
{
 double height;
 unsigned int index;
};
struct Array
{
 Prop *content;
 unsigned int size;
};

先建立一個結構，內容是每個人的資料，也就是double的height^[?]和unsigned int的index^[?]。然後再建立一個Array的結構把它包起來。
我為什麼不直接就用Prop這個結構去建立陣列呢？其實只是我個人的喜好而已，因為與其另外再宣告一個變數放陣列目前長度，不如直接用結構把它跟陣列本身綁起來，對我來說比較好懂。
使用動態陣列存也只是我個人的喜好，各位高興也可以換成固定陣列。
由於是動態陣列，所以要先建立出陣列空間^[?]：

Array people;
// C version:
people.content = (Prop*)malloc( sizeof( Prop ) * people.size );
// C++ version:
people.content = new Prop[people.size];

到了這步，我假設你已把資料全部正確的放進陣列裡了。
好了，問題來了，qsort和sort都不認得這個結構的大小判斷，compiler會很直接的發給你一張好人卡，那接下來要怎麼辦？
注意到，sort其實可以放第三個argument，也就是compare function的address，而qsort則是一定要放入compare function。要動手腳的地方就在這裡。

// C version:
int compare( const void *a, const void *b )
{
 return ( ( Prop* )a )->height > ( ( Prop* )b )->height;
}
qsort( people.content, people.size, sizeof( Prop ), compare );
// C++ version:
bool compare( Prop a, Prop b )
{
 return a.height < b.height;
}
sort( people.content, people.content + people.size, compare );

也就是說，其實可以藉由自訂compare function的方式來自訂要用哪個元素排序。
注意，C的qsort和C++的sort排序的條件不同，qsort是當compare為true時做swap，sort則是當compare為false時做swap，當發現sort出來的結果怪怪的時候，請檢查compare function。
最後請記得，有多少個malloc就要有多少個free，有多少個new就要有多少個delete，有借有還，再借不難唄:P

// C version:
free( ( void* )people.content );
// C++ version:
delete[] people.content;