文字のマージソート

Question

私は15,000のポインタを持っています。

私はそのようなループ内でのソートマージ置く理由はアルファベット順ではなく、配列内の文字列内の各インデックス内の文字を並べ替えることで、コード

for (int x = 0; x < n;x++) 
{ 
    mergeSort(array[x],0,strlen(array[x]-1); 
} 

の小さなビットを持っています。

forループでマージソートを行うと効率が低下しますか？それは私にn log nの実行時間を失わせるだろうか？

Answer 1

kを文字の総数とすると、時刻はn*k/n*log(k/n) = k*log(k/n)になります。 1つの配列内のすべての文字を持っていて、それらをすべて並べ替える場合（それはk*log(k)）よりも速くなります。それを漸近的に良くする方法はありません。

実用的な観点から、あなたは別のソート方法を使用して

• を考慮することができます。漸近的には同等ですが、一部のメソッドは短い配列ではパフォーマンスが向上する可能性があります（メモリのローカリティが向上しているなどの理由から、ここにはhttps://www.youtube.com/watch?v=fHNmRkzxHWs&t=52m36sがあります）。
• マルチスレッドの使用。

Answer 2

マージソートは常にO(n * log_2(n))です。ここで、nはソートされている配列の長さです。この場合、それは文字列の長さです。それぞれの種類はO(n * log_2(n))になります。

しかし、あなたは、このように合計時間は、各弦のための時間の和である、文字列ごとに一回の並べ替えを繰り返している：

O(n1 * log_2(n1)) + O(n2 * log_2(n2)) + ... + O(nk * log_2(nk)) 

N1、N2、...、NKソートされているすべての文字列の長さです。

すべてのk文字列の長さがnであると仮定すると、このアルゴリズム全体がk * O(n * log_2(n))であると仮定します。

Answer 3

この場合、ある種の基数ソートを使ってO（n log n）を上回ることができます。例えば

、（文字列は本当に短い場合を除き）すべての文字を使用すると、次の操作を行うことができます1つのバイトであれば：

create an array of 256 ints 
for each string: 
    memset array to 0 (*) 
    loop through the bytes until zero is reached 
     for each byte increment the corresponding value in the array 
    loop through the array and write n characters with the value of current pos 
    (*) instead of memset, you could reset the values to zero in this loop 

これはまたに完全な文字列をスキャンしていstrlen()への呼び出しを排除長さを取得します。だからあなたはあなたの文字列を一回通過するような並べ替えをしています。

文字列には通常の文字と数字しか含まれていない場合は、より短い配列を使用できます。

文字列が実際には短い場合、上記と他のソートアルゴリズムにはオーバーヘッドがあります。代わりに、bubblesortでテストを行うことができます（はい） - 私はどこかで項目の数が少ない場合、バーストートを高速化することができます（数は6程度だと思います）。

もちろん、文字列がUnicodeの場合は、もう少し作業をする必要があります（ただし、例のコードを見るとそうは見えません）。