Aritalab:Lecture/Algorithm/Sorting
Contents |
概要
ここでは種々の整列(ソーティング)アルゴリズムを紹介します。 アルゴリズムの理解が目的のため、プログラムは整数配列を入力として受け取り、配列の中身を整列させるものとします。 プログラム言語はJavaを想定しており、 また配列の要素 i, j を交換するサブルーチンを
static public void swap(int[] A, int i, int j) { int t = A[i]; A[i] = A[j]; A[j] = t; }
と書きます。
実用にならないアルゴリズム
Selection Sort 選択ソート
左から右へ順にスキャンして、�i 番目のスキャンにおける最小値を配列の i 番目に格納します。
static public void selectionSort(int[] A) { for(int i=0; i < A.length; i++) { int min = i; for (int j=i+1; j < A.length; j++) if (A[j] < A[min]) min = j; swap(A, min, i); } }
計算量は常に N2/2 で、何の工夫も無いアルゴリズムです。
Insertion Sort 挿入ソート
人間がトランプのカードを並べて揃えるときに利用する方法に近いソートです。配列がほとんど整列されている場合に限り、配列長に比例する時間で終了します。
static public void insertionSort(int[] A) { for(int i=1; i < A.length; i++) { int v = A[i]; int j = i; while (j > 0 && A[j-1] > v) { A[j] = A[j-1]; j--; } A[j] = v; } }
最悪計算量は n2/2 で、配列が逆順にソートされている場合に生じます。
Bubble Sort バブルソート
ファイルを先頭からスキャンし、隣り合う数の大小が狂っていたら交換します。
static public void bubbleSort(int[] A) { for(int i=A.length; i > 0; i--) for(int j=1; j < i; j++) if (A[j-1] > A[j]) swap(j-1, j); }
最悪計算量は n2/2 で、配列が逆順にソートされている場合に生じます。
実用アルゴリズム
Shell Sort シェルソート
挿入ソート法は常に隣どうしだけをみて挿入位置を決めたため、効率が悪くなりました。Shellは数個とびに挿入ソート法をかけて大雑把にソートしてから、次第に間隔をせばめて完全にソートする手法を考案しました。 類似の手法がコムソート (Comb Sort) として世の中に出回っていますが、「コムソートは(後述する)クイックソートより速い」といった議論は、計算量の観点からすると不毛です。
static public void shellSort(int[] A) { int N = A.length; int h; for(h = 1; h < N/9; h = 3*h + 1);// スキップ幅決定 for(; h > 0; h /= 3) for(int i = h; i < N; i++) { //幅hの挿入ソート int v = A[i]; int j = i; while (j > (h-1) && A[j-h] > v) { A[j] = A[j-h]; j -= h; } A[j] = v; } }
ここではスキップ幅に増分列...,1093,364,121,40,13,4,1を利用しています。 最悪計算量は挿入ソートに同じで O(n2) になります。
Quick Sort クイックソート
Hoareによって考案された分割統治法によるアルゴリズムです。 実用上最速といわれます。名前は種々の解析がなされる前にHoare自身がつけました。
static public void quickSort(int[] A) { quickSort(A, 0, A.length-1); } static public void quickSort(int[] A, int left, int right) { if (left >= right) return; int i = partition(A, left, right); quickSort(A, left, i-1); quickSort(A, i+1, right); } static public void partition(int[] A, int left, int right) { swap(A, left, (left+right)/2); int p = left; //A[left] ... A[p-1]にp未満の値、 //A[p+1] ... A[right]にp以上の値をいれる for(int i = left + 1; i <= right; i++) if (A[i] < A[left]) swap(A, ++p, i); swap(A, left, p); return p; }
平均計算量は O(n log n)、最悪計算量は O( n2 ) になります。
Merge Sort マージソート
クイックソートと同じく分割統治法に基づきます。クイックソート がトップダウンに分けていくのに対してボトムアップにマージします。 ソートする配列と同サイズの配列スペースを要しますが、並び順を変えないstableソートで有用です。 外部記憶を用いたソートによく用いられます。
public static void mergeSort(int[] A) { int[] tmp = new int[A.length]; mergeSort(A, tmp, 0, A.length); } public static void mergeSort(int[] A, int[] tmp, int left, int right) { if (left >= right) return; int p = (left + right)/2; mergeSort(A, tmp, left, p); mergeSort(A, tmp, p+1, right); merge(A, tmp, left, p+1, right); } public static void merge(int[] A, int[] tmp, int left, int p, int right) { int siz = right - left + 1; int left_end = p - 1; int t = left; while ((left <= left_end) && (p <= right)) tmp[t] : A[p] = A[left] = A[p) A[right] = tmp[right++]; }
}