非再帰的マージソート
https://stackoverflow.com/questions/1557894
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
誰かが非再帰的マージソートの動作を行う方法を英語で説明できますか？
おかげ
解決
要素をループと2を交換によってソート両者のすべての隣接するグループを作るときに必要な
さて、二つのグループのグループを扱う（任意の2、最も可能性の高い隣接するグループがありますが、最初と最後のグループを使用することができます）、すべての4つの要素があるまで繰り返し、各グループからの最低の価値の要素を選択することが1つのグループにそれらをマージ今4のグループにマージ、あなたは4のグループが、何もプラスの可能な残りを持っていません。一つだけのグループがあるまで、以前のロジックの周りにループを使用して、4のグループで、このタイムの仕事を除いて、再びそれをすべて行うこのループが実行されます。
他のヒント
非再帰的マージソート入力配列上1,2,4,8,16..2 ^ n個のウィンドウサイズを考慮することによって動作します。各ウィンドウ（下記のコードで「K」）は、Windowsのすべての隣接する対は、アレイに戻し、一時領域にマージされます。
ここに私の単一の関数、Cベース、非再帰的マージソートです。 入力と出力が「A」です。 「B」で一時的な記憶。 ある日、私は、インプレースたバージョンを持っているしたいと思います：
float a[50000000],b[50000000];
void mergesort (long num)
{
int rght, wid, rend;
int i,j,m,t;
for (int k=1; k < num; k *= 2 ) {
for (int left=0; left+k < num; left += k*2 ) {
rght = left + k;
rend = rght + k;
if (rend > num) rend = num;
m = left; i = left; j = rght;
while (i < rght && j < rend) {
if (a[i] <= a[j]) {
b[m] = a[i]; i++;
} else {
b[m] = a[j]; j++;
}
m++;
}
while (i < rght) {
b[m]=a[i];
i++; m++;
}
while (j < rend) {
b[m]=a[j];
j++; m++;
}
for (m=left; m < rend; m++) {
a[m] = b[m];
}
}
}
}
ところで、O（n個のnを記録）であることを証明するためにも非常に簡単です。ウィンドウサイズを超える外側のループは2の累乗として成長するので、kはログN回の反復を有します。内側ループによって覆わ多くのウィンドウが存在するが、一緒になって、与えられたkについての全てのウィンドウが正確に入力されたアレイを覆うので、内部ループはO（N）です。 O（N）* O（ログn）= O（Nログn）
：内側と外側のループを組み合わせますAlgorithmistするから引用
ボトムアップがソートされマージ マージの非再帰的バリアント 配列がソートされている並べ替え、 パスのシーケンス。それぞれの間に 渡し、アレイは、ブロックに分割され サイズののM の。 （最初は、 M = 1 ）。 すべての隣接する二つのブロックがマージされます （通常のマージソートのように）、および 次のパスは2倍で作られています のM の
の値
再帰と非再帰両方マージソートO（nlog（n））を同一の時間複雑性を有します。両方のアプローチは、1つまたは他の方法でスタックを使用するからである。
非再帰的なアプローチで ユーザー/プログラマが定義し、スタックを使用します。
再帰的アプローチスタックに再帰的に呼び出される関数のリターンアドレスを格納するためにシステムによって内部で使用される
あなたは非再帰的マージソートを使用したいと思う主な理由は、再帰スタックオーバーフローを避けるためです。例えば、私は億件のレコードをソートしようとしています、英数字順に各レコードの長さ（= 100ギガバイト）で約1キロバイト、。それも、比較演算当たり0.1マイクロ秒で実行するために数十年かかるだろう。すなわち順（N ^ 2）のソートは、10 ^ 16の操作を取るだろう。オーダー（N（N）ログ）ソート同じ動作速度で実行するように時間未満10 ^ 10の操作以下になりますマージします。しかし、マージソートの再帰的バージョンでは100万人の要素は、ソートマージ〜50万人の再帰呼び出しになります（）。スタック再帰あたり数百バイトで、このプロセスは簡単にヒープメモリ内に収まるにもかかわらず、再帰スタックをオーバーフロー。並べ替え私は上記ラマHoetzleinによって提供されたコードを使用していますが、私はヒープ上に動的に割り当てられたメモリを使用する代わりにstack--を使用していますheap--に動的に割り当てられたメモリを使用してマージをやって私は私の億件のレコードをソートすることができます非再帰的マージソートと私は、スタックオーバーフローしません。ウェブサイトのための適切な会話「スタックオーバーフロー」！
PS：コードのおかげで、ラマHoetzlein
PPS：ヒープ上の100ギガバイト!!？まあ、それはHadoopクラスタ上の仮想ヒープだ、とマージは、負荷を共有する複数のマシン上で並列に実行されます...
私はここに新しいです。 私はラマHoetzlein溶液（アイデアの感謝を）変更しました。私のマージソートは、最後のコピーバックループを使用していません。それに加えて挿入ソートにフォールバックします。私は私のラップトップ上でそれをベンチマークしているし、それが最速です。再帰的なバージョンよりもさらに良いです。ちなみにこれは、Javaにあり、昇順に降順から並べ替えます。そしてもちろん、それは反復的です。これは、マルチスレッドにすることができます。コードが複雑になってきました。誰も興味があれば、是非ご覧下さい。
コード：
int num = input_array.length;
int left = 0;
int right;
int temp;
int LIMIT = 16;
if (num <= LIMIT)
{
// Single Insertion Sort
right = 1;
while(right < num)
{
temp = input_array[right];
while(( left > (-1) ) && ( input_array[left] > temp ))
{
input_array[left+1] = input_array[left--];
}
input_array[left+1] = temp;
left = right;
right++;
}
}
else
{
int i;
int j;
//Fragmented Insertion Sort
right = LIMIT;
while (right <= num)
{
i = left + 1;
j = left;
while (i < right)
{
temp = input_array[i];
while(( j >= left ) && ( input_array[j] > temp ))
{
input_array[j+1] = input_array[j--];
}
input_array[j+1] = temp;
j = i;
i++;
}
left = right;
right = right + LIMIT;
}
// Remainder Insertion Sort
i = left + 1;
j = left;
while(i < num)
{
temp = input_array[i];
while(( j >= left ) && ( input_array[j] > temp ))
{
input_array[j+1] = input_array[j--];
}
input_array[j+1] = temp;
j = i;
i++;
}
// Rama Hoetzlein method
int[] temp_array = new int[num];
int[] swap;
int k = LIMIT;
while (k < num)
{
left = 0;
i = k;// The mid point
right = k << 1;
while (i < num)
{
if (right > num)
{
right = num;
}
temp = left;
j = i;
while ((left < i) && (j < right))
{
if (input_array[left] <= input_array[j])
{
temp_array[temp++] = input_array[left++];
}
else
{
temp_array[temp++] = input_array[j++];
}
}
while (left < i)
{
temp_array[temp++] = input_array[left++];
}
while (j < right)
{
temp_array[temp++] = input_array[j++];
}
// Do not copy back the elements to input_array
left = right;
i = left + k;
right = i + k;
}
// Instead of copying back in previous loop, copy remaining elements to temp_array, then swap the array pointers
while (left < num)
{
temp_array[left] = input_array[left++];
}
swap = input_array;
input_array = temp_array;
temp_array = swap;
k <<= 1;
}
}
return input_array;
念のために誰もがまだこのスレッドに潜んだ...私は、二重リンクリストをソートするために上記ラマHoetzleinの非再帰的マージソートアルゴリズムを適応してきました。この新しいソートは、その場で安定しており、他のリンクリストのマージソートの実装でのコードを割る時間高価なリストを回避できます。
// MergeSort.cpp
// Angus Johnson 2017
// License: Public Domain
#include "io.h"
#include "time.h"
#include "stdlib.h"
struct Node {
int data;
Node *next;
Node *prev;
Node *jump;
};
inline void Move2Before1(Node *n1, Node *n2)
{
Node *prev, *next;
//extricate n2 from linked-list ...
prev = n2->prev;
next = n2->next;
prev->next = next; //nb: prev is always assigned
if (next) next->prev = prev;
//insert n2 back into list ...
prev = n1->prev;
if (prev) prev->next = n2;
n1->prev = n2;
n2->prev = prev;
n2->next = n1;
}
void MergeSort(Node *&nodes)
{
Node *first, *second, *base, *tmp, *prev_base;
if (!nodes || !nodes->next) return;
int mul = 1;
for (;;) {
first = nodes;
prev_base = NULL;
//sort each successive mul group of nodes ...
while (first) {
if (mul == 1) {
second = first->next;
if (!second) {
first->jump = NULL;
break;
}
first->jump = second->next;
}
else
{
second = first->jump;
if (!second) break;
first->jump = second->jump;
}
base = first;
int cnt1 = mul, cnt2 = mul;
//the following 'if' condition marginally improves performance
//in an unsorted list but very significantly improves
//performance when the list is mostly sorted ...
if (second->data < second->prev->data)
while (cnt1 && cnt2) {
if (second->data < first->data) {
if (first == base) {
if (prev_base) prev_base->jump = second;
base = second;
base->jump = first->jump;
if (first == nodes) nodes = second;
}
tmp = second->next;
Move2Before1(first, second);
second = tmp;
if (!second) { first = NULL; break; }
--cnt2;
}
else
{
first = first->next;
--cnt1;
}
} //while (cnt1 && cnt2)
first = base->jump;
prev_base = base;
} //while (first)
if (!nodes->jump) break;
else mul <<= 1;
} //for (;;)
}
void InsertNewNode(Node *&head, int data)
{
Node *tmp = new Node;
tmp->data = data;
tmp->next = NULL;
tmp->prev = NULL;
tmp->jump = NULL;
if (head) {
tmp->next = head;
head->prev = tmp;
head = tmp;
}
else head = tmp;
}
void ClearNodes(Node *head)
{
if (!head) return;
while (head) {
Node *tmp = head;
head = head->next;
delete tmp;
}
}
int main()
{
srand(time(NULL));
Node *nodes = NULL, *n;
const int len = 1000000; //1 million nodes
for (int i = 0; i < len; i++)
InsertNewNode(nodes, rand() >> 4);
clock_t t = clock();
MergeSort(nodes); //~1/2 sec for 1 mill. nodes on Pentium i7.
t = clock() - t;
printf("Sort time: %d msec\n\n", t * 1000 / CLOCKS_PER_SEC);
n = nodes;
while (n)
{
if (n->prev && n->data < n->prev->data) {
printf("oops! sorting's broken\n");
break;
}
n = n->next;
}
ClearNodes(nodes);
printf("All done!\n\n");
getchar();
return 0;
}
2017年10月27日編集：奇数番号付きリストに影響を与えるバグを修正しました。
