ソートアルゴリズムの概要とそのC実装
32518 ワード
作者:Vamei出典:http://www.cnblogs.com/vamei転載を歓迎します.この声明も残してください.ありがとう!
ソートアルゴリズム(Sorting Algorithm)はコンピュータアルゴリズムの構成部分である.ソートアルゴリズムは、1つのシーケンスをサイズ順に並べ替えることです.ソートは古いが依然として挑戦的な問題だ.Donald Knuthの古典的な「コンピュータプログラム設計芸術」(The Art of Computer Programming)の第3巻は、ソートと検索を議論するために使用されている.無秩序から秩序へ,統計物理の観点から,システムのエントロピー値を減少させ,システムの秩序度を増加させた.秩序化という特徴はシステムに関する非常に有用な先行知識である.従って、ソートアルゴリズムは、二分法が秩序化シーケンスに基づくルックアップアルゴリズムであるなど、他の高速アルゴリズムの基礎とすることができる.今日に至るまで、ソートアルゴリズムは依然としてコンピュータ科学が積極的に探求する方向である.
ここでは、最も一般的なソート方法をいくつかリストし、C言語で実装します.シーケンスは配列aとして表され、配列にはn個の要素がある.a[i]は配列内の要素であり、iは配列内の要素の位置(下付き)である.Cの規定により、配列の下付き文字は0から始まる.配列が左から右に並び、下に0と表示される要素が配列の一番左にあるとします.
シーケンスは最終的に小さい順に並べられます.次の関数のパラメータacは、配列内の要素の数、すなわちnである.
(C言語の配列名はすべてポインタに変換され、関数に渡されるので、配列中の要素の数acを関数に渡す必要があります.詳しくは「Expert C Programming:Deep C Secrets」という本を参照)
開始数列(unsorted)
秩序数列(sorted)
次のリンクでは、関連アルゴリズムのアニメーションの例があり、同時に読むことを強くお勧めします.
http://www.sorting-algorithms.com/
バブルソート(Bubble Sort)
シーケンスが小さいから大きいまで配列されている場合、任意の2つの隣接要素は、a[i−1]<=a[i]の関係を満たすべきである.バブルソートでは,右から左に配列を巡り,隣接する2つの要素を比較した.2つの要素の順序が間違っている場合は、この2つの要素を交換します.2つの要素の順序が正しい場合は、交換しません.1回の遍歴を経て、最小の元素(泡)が一番左の位置にあることを保証することができます.
1回の遍歴を経て、泡の並べ替えはすべての元素が小さいから大きいまで並べられていることを保証することはできません.したがって,配列要素を右から左に再遍歴し,バブルソートを行う必要がある.今回の遍歴では、左端の要素を考慮する必要はありません.その後、n−1回までの遍歴を継続する.
ある遍歴中に要素が交換されなかった場合、配列がソートされていることを示し、ソートの停止を中止できます.最悪の場合、開始配列で最大の要素が一番左にある場合、バブルアルゴリズムは、配列を事前に並べ替えることなくn−1回遍歴しなければならない.
ソートの挿入(Insertion Sort)
新入生が到着したとき、私たちは新入生を身長に合わせて列に並べます(つまりソート).もしこの時一人の学生が参加したら、私たちはその学生をチームの尾に参加します.この学生が前の学生より低い場合は、その学生と前の学生と位置を交換させます.この学生は最終的に位置を変える.これがソートを挿入する基本原理です.
初期配列については,最初は,最も左側の要素(i=0)である学生が秩序ある行列を構成していたと考えられる.
その後、2番目の学生(i=1)がチームに参加し、2番目の学生は位置を交換した.その後、3人目の学生がチームに参加し、3人目の学生が位置を交換する......n人の学生がチームに参加すると、私たちのソートが完了します.
選択ソート(Selection Sort)
ソートの最終結果:いずれの要素もその右側にある要素(a[i]<=a[j],if i<=j)より大きくない.したがって、秩序シーケンスでは、最小の要素が最も左の位置に、第2の小さな要素がi=1の位置に......最大の要素が最後に並ぶ.
選択ソートは、最初の配列の最小要素を見つけて、i=0に交換します.次に、残りの要素の最小の要素を探して、i=1の位置に交換します.2番目に大きい要素が見つかるまで、n-2の位置に交換します.このとき,配列全体の並べ替えが完了する.
ヒルソート(Shell Sort)
バブルソートでは,最悪の場合,大きな元素が配列の先頭に位置することに言及した.これらの配列の先頭にある大きな要素は、キューの末尾に交換するために何度も巡回する必要があります.このような要素をカメ(turtle)と呼ぶ.
亀元素の原因は,泡配列が常に隣接する2つの元素を比較し交換することにある.したがって、右から左に遍歴するたびに、大きな要素は右に1つしか移動できません.(小さな要素はチームの尾にあり、ウサギ(rabbit)要素と呼ばれ、すぐにチームの頭に交換することができます.)
ヒルソートは、エレメントをより大きな間隔で比較して交換することで、大きなエレメントは交換時に右に複数の位置を移動することができ、亀エレメントをより速く移動することができます.例えば、配列を4つのサブ配列(i=4 k,i=4 k+1,i=4 k+2,i=4 k+3)に分けて、各サブ配列をバブルソートすることができる.例えば、サブ配列i=0、4、8、12....このとき,交換毎の間隔は4である.
4つのサブ配列の並べ替えが完了すると,配列の順序が必ずしもうまく並ぶとは限らない.ヒルソートは間隔を小さくし、サブ配列を再形成し、サブ配列をバブルソートする......間隔を1に小さくすると、配列全体をバブルソートすることに相当します.その後、配列の順序が整います.
ヒルソートは泡ソートだけでなく、他のソート方法にも合わせて完了することができます.
Shell Sortingは間隔(step)の選択に依存する.一般的な選択肢は、今回の間隔を前回の間隔の1/1.3に設定することです.参考書を参照.
集計ソート(Merge Sort)
もし私たちがトランプを数字の大きさで並べ替えるなら.これまで2人がそれぞれその半分を順番に並べていた.では、小さなカードが上にあると仮定して、この2つのトランプを上に置くことができます.このとき、札の山の中で一番上の2枚の札が見えます.
私たちは2枚のカードの中の中の1枚を取って手に入れた.2つのデッキの中にまた2枚のカードが一番上に露出して、小さいのを取って手に入れ続けます......すべてのカードが手に入るまで、カード全体が順番に並んでいます.これが集計ソートです.
次のインプリメンテーションでは、再帰を使用します.
クイックソート(Quick Sort)
私たちは依然として身長によって学生に順位をつけることを考えています.クイックソートでは、その学生の身長を参考に、勝手に学生を選びました(pivot).そして、その学生より低い人をその学生の右側に立たせ、残りの人をその学生の左側に立たせます.
明らかに、すべての学生が2つのグループに分かれている.この学生の右側の学生の身長はいずれもその学生の左の学生の身長より大きい.
私たちは続けて、低身長の学生グループで勝手に1人の学生を選んで、低身長の学生を2つのグループに分けます(とても低いとそんなに低くありません).同様に、高学生グループも2つのグループ(それほど高くない)に分けられます.
このように、グループに学生が1人しかいないまで細分化を続けます.すべてのグループに学生が1人しかいない場合、ソートは完了します.
次のインプリメンテーションでは、再帰を使用します.
理想的なpivotは、パケット要素の中位数を採用することである.しかし、中位数を探すアルゴリズムは別途実現する必要がある.要素をpivotとしてランダムに選択することもでき、ランダム選択も別途実現する必要がある.簡単にするために、pivotとして中間位置の要素を毎回採用しています.
ヒープソート(Heap Sort)
スタック(heap)は一般的なデータ構造である.優先順位のあるキューです.最も一般的なスタックの実装は、限定された操作を有するComplete Binary Treeである.このComplete Binary Treeはスタックの特性を保持し,すなわち親ノード(parent)が子ノード(children)より大きい.したがって、スタックのルートノードは、すべてのスタック要素の中で最小です.スタック定義には、挿入ノードとルートノードの削除操作があり、両方の操作はスタックの特性を維持します.
無秩序配列をスタックに構成し,ルートノードを絶えず取り出し,最終的に秩序配列を構成することができる.
スタックの詳細については、参考書を参照してください.
次に、スタックのデータ構造と、ノードの挿入とルートノードの削除操作を示します.スタックを簡単に構築し、ルートノードを取り出して秩序配列を構成することができます.
まとめ
上記のアルゴリズムに加えて、Bucket Sorting、Radix Sortingなどがあります.私は将来関連アルゴリズムを実現した後、この文章に補充します.関連アルゴリズムの時間複雑度解析は書目を参照して見つけることができる.私自身もざらざらした分析をしました.ブログ園が数学の公式の表示をサポートできれば、私は自分の分析過程を貼って、玉を引くために使います.
上の各コードは私が自分で書いたもので、簡単なテストしかできませんでした.もし間違いがあったら、まずご指摘ありがとうございます.
最後に、上記で使用した交換関数は次のとおりです.
参考書目
Data Structures and Algorithm Analysis in C, Mark Allen Weiss
Algorithms in C, Robert Sedgewick
作者:Vamei出典:http://www.cnblogs.com/vamei転載を歓迎します.この声明も残してください.ありがとう!
ソートアルゴリズム(Sorting Algorithm)はコンピュータアルゴリズムの構成部分である.ソートアルゴリズムは、1つのシーケンスをサイズ順に並べ替えることです.ソートは古いが依然として挑戦的な問題だ.Donald Knuthの古典的な「コンピュータプログラム設計芸術」(The Art of Computer Programming)の第3巻は、ソートと検索を議論するために使用されている.無秩序から秩序へ,統計物理の観点から,システムのエントロピー値を減少させ,システムの秩序度を増加させた.秩序化という特徴はシステムに関する非常に有用な先行知識である.従って、ソートアルゴリズムは、二分法が秩序化シーケンスに基づくルックアップアルゴリズムであるなど、他の高速アルゴリズムの基礎とすることができる.今日に至るまで、ソートアルゴリズムは依然としてコンピュータ科学が積極的に探求する方向である.
ここでは、最も一般的なソート方法をいくつかリストし、C言語で実装します.シーケンスは配列aとして表され、配列にはn個の要素がある.a[i]は配列内の要素であり、iは配列内の要素の位置(下付き)である.Cの規定により、配列の下付き文字は0から始まる.配列が左から右に並び、下に0と表示される要素が配列の一番左にあるとします.
シーケンスは最終的に小さい順に並べられます.次の関数のパラメータacは、配列内の要素の数、すなわちnである.
(C言語の配列名はすべてポインタに変換され、関数に渡されるので、配列中の要素の数acを関数に渡す必要があります.詳しくは「Expert C Programming:Deep C Secrets」という本を参照)
開始数列(unsorted)
秩序数列(sorted)
次のリンクでは、関連アルゴリズムのアニメーションの例があり、同時に読むことを強くお勧めします.
http://www.sorting-algorithms.com/
バブルソート(Bubble Sort)
シーケンスが小さいから大きいまで配列されている場合、任意の2つの隣接要素は、a[i−1]<=a[i]の関係を満たすべきである.バブルソートでは,右から左に配列を巡り,隣接する2つの要素を比較した.2つの要素の順序が間違っている場合は、この2つの要素を交換します.2つの要素の順序が正しい場合は、交換しません.1回の遍歴を経て、最小の元素(泡)が一番左の位置にあることを保証することができます.
1回の遍歴を経て、泡の並べ替えはすべての元素が小さいから大きいまで並べられていることを保証することはできません.したがって,配列要素を右から左に再遍歴し,バブルソートを行う必要がある.今回の遍歴では、左端の要素を考慮する必要はありません.その後、n−1回までの遍歴を継続する.
ある遍歴中に要素が交換されなかった場合、配列がソートされていることを示し、ソートの停止を中止できます.最悪の場合、開始配列で最大の要素が一番左にある場合、バブルアルゴリズムは、配列を事前に並べ替えることなくn−1回遍歴しなければならない.
/*By Vamei*/
/*swap the neighbors if out of order*/
void bubble_sort(int a[], int ac)
{
/*use swap*/
int i,j;
int sign;
for (j = 0; j < ac-1; j++) {
sign = 0;
for(i = ac-1; i > j; i--)
{
if(a[i-1] > a[i]) {
sign = 1;
swap(a+i, a+i-1);
}
}
if (sign == 0) break;
}
}ソートの挿入(Insertion Sort)
新入生が到着したとき、私たちは新入生を身長に合わせて列に並べます(つまりソート).もしこの時一人の学生が参加したら、私たちはその学生をチームの尾に参加します.この学生が前の学生より低い場合は、その学生と前の学生と位置を交換させます.この学生は最終的に位置を変える.これがソートを挿入する基本原理です.
初期配列については,最初は,最も左側の要素(i=0)である学生が秩序ある行列を構成していたと考えられる.
その後、2番目の学生(i=1)がチームに参加し、2番目の学生は位置を交換した.その後、3人目の学生がチームに参加し、3人目の学生が位置を交換する......n人の学生がチームに参加すると、私たちのソートが完了します.
/*By Vamei*/
/*insert the next element into the sorted part*/
void insert_sort(int a[], int ac) { /*use swap*/
int i,j; for (j=1; j < ac; j++) { i = j-1; while((i>=0) && (a[i+1] < a[i])) { swap(a+i+1, a+i); i--; } } }選択ソート(Selection Sort)
ソートの最終結果:いずれの要素もその右側にある要素(a[i]<=a[j],if i<=j)より大きくない.したがって、秩序シーケンスでは、最小の要素が最も左の位置に、第2の小さな要素がi=1の位置に......最大の要素が最後に並ぶ.
選択ソートは、最初の配列の最小要素を見つけて、i=0に交換します.次に、残りの要素の最小の要素を探して、i=1の位置に交換します.2番目に大きい要素が見つかるまで、n-2の位置に交換します.このとき,配列全体の並べ替えが完了する.
/*By Vamei*/
/*find the smallest of the rest, then append to the sorted part*/
void select_sort(int a[], int ac) { /*use swap*/
int i,j; int min_idx; for (j = 0; j < ac-1; j++) { min_idx = j; for (i = j+1; i < ac; i++) { if (a[i] < a[min_idx]) { min_idx = i; } } swap(a+j, a+min_idx); } }ヒルソート(Shell Sort)
バブルソートでは,最悪の場合,大きな元素が配列の先頭に位置することに言及した.これらの配列の先頭にある大きな要素は、キューの末尾に交換するために何度も巡回する必要があります.このような要素をカメ(turtle)と呼ぶ.
亀元素の原因は,泡配列が常に隣接する2つの元素を比較し交換することにある.したがって、右から左に遍歴するたびに、大きな要素は右に1つしか移動できません.(小さな要素はチームの尾にあり、ウサギ(rabbit)要素と呼ばれ、すぐにチームの頭に交換することができます.)
ヒルソートは、エレメントをより大きな間隔で比較して交換することで、大きなエレメントは交換時に右に複数の位置を移動することができ、亀エレメントをより速く移動することができます.例えば、配列を4つのサブ配列(i=4 k,i=4 k+1,i=4 k+2,i=4 k+3)に分けて、各サブ配列をバブルソートすることができる.例えば、サブ配列i=0、4、8、12....このとき,交換毎の間隔は4である.
4つのサブ配列の並べ替えが完了すると,配列の順序が必ずしもうまく並ぶとは限らない.ヒルソートは間隔を小さくし、サブ配列を再形成し、サブ配列をバブルソートする......間隔を1に小さくすると、配列全体をバブルソートすることに相当します.その後、配列の順序が整います.
ヒルソートは泡ソートだけでなく、他のソート方法にも合わせて完了することができます.
/*By Vamei*/
/*quickly sort the turtles at the tail of the array*/
void shell_sort(int a[], int ac) { int step; int i,j; int nsub; int *sub; /* initialize step */ step = 1; while(step < ac) step = 3*step + 1; /* when step becomes 1, it's equivalent to the bubble sort*/
while(step > 1) { /* step will go down to 1 at most */ step = step/3 + 1; for(i=0; i<step; i++) { /* pick an element every step, and combine into a sub-array */ nsub = (ac - i - 1)/step + 1; sub = (int *) malloc(sizeof(int)*nsub); for(j=0; j<nsub; j++) { sub[j] = a[i+j*step]; } /* sort the sub-array by bubble sorting. It could be other sorting methods */ bubble_sort(sub, nsub); /* put back the sub-array*/
for(j=0; j<nsub; j++) { a[i+j*step] = sub[j]; } /* free sub-array */ free(sub); } } }Shell Sortingは間隔(step)の選択に依存する.一般的な選択肢は、今回の間隔を前回の間隔の1/1.3に設定することです.参考書を参照.
集計ソート(Merge Sort)
もし私たちがトランプを数字の大きさで並べ替えるなら.これまで2人がそれぞれその半分を順番に並べていた.では、小さなカードが上にあると仮定して、この2つのトランプを上に置くことができます.このとき、札の山の中で一番上の2枚の札が見えます.
私たちは2枚のカードの中の中の1枚を取って手に入れた.2つのデッキの中にまた2枚のカードが一番上に露出して、小さいのを取って手に入れ続けます......すべてのカードが手に入るまで、カード全体が順番に並んでいます.これが集計ソートです.
次のインプリメンテーションでは、再帰を使用します.
/*By Vamei*/
/*recursively merge two sorted arrays*/
void merge_sort(int *a, int ac) { int i, j, k; int ac1, ac2; int *ah1, *ah2; int *container; /*base case*/
if (ac <= 1) return; /*split the array into two*/ ac1 = ac/2; ac2 = ac - ac1; ah1 = a + 0; ah2 = a + ac1; /*recursion*/ merge_sort(ah1, ac1); merge_sort(ah2, ac2); /*merge*/ i = 0; j = 0; k = 0; container = (int *) malloc(sizeof(int)*ac); while(i<ac1 && j<ac2) { if (ah1[i] <= ah2[j]) { container[k++] = ah1[i++]; } else { container[k++] = ah2[j++]; } } while (i < ac1) { container[k++] = ah1[i++]; } while (j < ac2) { container[k++] = ah2[j++]; } /*copy back the sorted array*/
for(i=0; i<ac; i++) { a[i] = container[i]; } /*free space*/ free(container); }クイックソート(Quick Sort)
私たちは依然として身長によって学生に順位をつけることを考えています.クイックソートでは、その学生の身長を参考に、勝手に学生を選びました(pivot).そして、その学生より低い人をその学生の右側に立たせ、残りの人をその学生の左側に立たせます.
明らかに、すべての学生が2つのグループに分かれている.この学生の右側の学生の身長はいずれもその学生の左の学生の身長より大きい.
私たちは続けて、低身長の学生グループで勝手に1人の学生を選んで、低身長の学生を2つのグループに分けます(とても低いとそんなに低くありません).同様に、高学生グループも2つのグループ(それほど高くない)に分けられます.
このように、グループに学生が1人しかいないまで細分化を続けます.すべてのグループに学生が1人しかいない場合、ソートは完了します.
次のインプリメンテーションでは、再帰を使用します.
/*By Vamei*/
/*select pivot, put elements (<= pivot) to the left*/
void quick_sort(int a[], int ac) { /*use swap*/
/* pivot is a position, all the elements before pivot is smaller or equal to pvalue */
int pivot; /* the position of the element to be tested against pivot */
int sample; /* select a pvalue. Median is supposed to be a good choice, but that will itself take time. here, the pvalue is selected in a very simple wayi: a[ac/2] */
/* store pvalue at a[0] */ swap(a+0, a+ac/2); pivot = 1; /* test each element */
for (sample=1; sample<ac; sample++) { if (a[sample] < a[0]) { swap(a+pivot, a+sample); pivot++; } } /* swap an element (which <= pvalue) with a[0] */ swap(a+0,a+pivot-1); /* base case, if only two elements are in the array, the above pass has already sorted the array */
if (ac<=2) return; else { /* recursion */ quick_sort(a, pivot); quick_sort(a+pivot, ac-pivot); } }理想的なpivotは、パケット要素の中位数を採用することである.しかし、中位数を探すアルゴリズムは別途実現する必要がある.要素をpivotとしてランダムに選択することもでき、ランダム選択も別途実現する必要がある.簡単にするために、pivotとして中間位置の要素を毎回採用しています.
ヒープソート(Heap Sort)
スタック(heap)は一般的なデータ構造である.優先順位のあるキューです.最も一般的なスタックの実装は、限定された操作を有するComplete Binary Treeである.このComplete Binary Treeはスタックの特性を保持し,すなわち親ノード(parent)が子ノード(children)より大きい.したがって、スタックのルートノードは、すべてのスタック要素の中で最小です.スタック定義には、挿入ノードとルートノードの削除操作があり、両方の操作はスタックの特性を維持します.
無秩序配列をスタックに構成し,ルートノードを絶えず取り出し,最終的に秩序配列を構成することができる.
スタックの詳細については、参考書を参照してください.
次に、スタックのデータ構造と、ノードの挿入とルートノードの削除操作を示します.スタックを簡単に構築し、ルートノードを取り出して秩序配列を構成することができます.
/* By Vamei
Use an big array to implement heap
DECLARE: int heap[MAXSIZE] in calling function
heap[0] : total nodes in the heap
for a node i, its children are i*2 and i*2+1 (if exists)
its parent is i/2 */
void insert(int new, int heap[])
{
int childIdx, parentIdx;
heap[0] = heap[0] + 1;
heap[heap[0]] = new;
/* recover heap property */
percolate_up(heap);
}
static void percolate_up(int heap[]) {
int lightIdx, parentIdx;
lightIdx = heap[0];
parentIdx = lightIdx/2;
/* lightIdx is root? && swap? */
while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {
/* swap */
swap(heap + lightIdx, heap + parentIdx);
lightIdx = parentIdx;
parentIdx = lightIdx/2;
}
}
int delete_min(int heap[])
{
int min;
if (heap[0] < 1) {
/* delete element from an empty heap */
printf("Error: delete_min from an empty heap.");
exit(1);
}
/* delete root
move the last leaf to the root */
min = heap[1];
swap(heap + 1, heap + heap[0]);
heap[0] -= 1;
/* recover heap property */
percolate_down(heap);
return min;
}
static void percolate_down(int heap[]) {
int heavyIdx;
int childIdx1, childIdx2, minIdx;
int sign; /* state variable, 1: swap; 0: no swap */
heavyIdx = 1;
do {
sign = 0;
childIdx1 = heavyIdx*2;
childIdx2 = childIdx1 + 1;
if (childIdx1 > heap[0]) {
/* both children are null */
break;
}
else if (childIdx2 > heap[0]) {
/* right children is null */
minIdx = childIdx1;
}
else {
minIdx = (heap[childIdx1] < heap[childIdx2]) ?
childIdx1 : childIdx2;
}
if (heap[heavyIdx] > heap[minIdx]) {
/* swap with child */
swap(heap + heavyIdx, heap + minIdx);
heavyIdx = minIdx;
sign = 1;
}
} while(sign == 1);
}まとめ
上記のアルゴリズムに加えて、Bucket Sorting、Radix Sortingなどがあります.私は将来関連アルゴリズムを実現した後、この文章に補充します.関連アルゴリズムの時間複雑度解析は書目を参照して見つけることができる.私自身もざらざらした分析をしました.ブログ園が数学の公式の表示をサポートできれば、私は自分の分析過程を貼って、玉を引くために使います.
上の各コードは私が自分で書いたもので、簡単なテストしかできませんでした.もし間違いがあったら、まずご指摘ありがとうございます.
最後に、上記で使用した交換関数は次のとおりです.
/* By Vamei */
/* exchange the values pointed by pa and pb*/
void swap(int *pa, int *pb)
{
int tmp;
tmp = *pa;
*pa = *pb;
*pb = tmp;
}参考書目
Data Structures and Algorithm Analysis in C, Mark Allen Weiss
Algorithms in C, Robert Sedgewick
作者:Vamei出典:http://www.cnblogs.com/vamei転載を歓迎します.この声明も残してください.ありがとう!