並べ替えアルゴリズム学習ノート(sorting algorithms)
8282 ワード
メモの前に書いたら、ノートに使用する方法はアルゴリズム第四版から提供されたstdlib.jarの中にあります.ここに注文して、公式サイトにダウンロードしてもいいです.もしjarパッケージを導入しても、引用できない場合は、ホームページの一番下のQ&Aを参考にして、stdlib-package.jarをクリックしてから案内してください.
ソートアルゴリズムテンプレート(template for sorting algorithms)
並べ替えの原理を選択
名前の通り、最小値を選択するたびに前に置いてください.配列【1、4、2、3、7、5】をStep 1に並べ替えます.最初のピットから配列を巡回し、最小値1を選んで、最初のピットの中にStep 2を入れます.2番目のピットから配列を遍歴し、最小値2を選択して、2番目のピットの中に入れます.Step 5:5番目のピットから配列を遍歴して、最小値5を選んで、5番目のピットの中に入れます.
アルゴリズムの実装
コードを下記のように整理します.
並べ替えの原理を挿入
配列を秩序化と無秩序の二つの部分に分けて,秩序化部分の適切な位置に順次,無秩序部分の要素を挿入した.配列【1、4、2、3、7、5】を例にとってStep 1:順序部分の無秩序部分は「/」で【1/4、2、3、7、5】を分割し、無秩序部分の最初の要素は4、4を順序部分の適切な位置すなわち1の後に配置し、並べ替え後の配列は【1、4、2、7、5】step 2:秩序部分の無秩序部分は‘3、【4/5】で分割されます.無秩序部分の最初の要素は2であり、2を秩序部分の適切な位置、すなわち1と4の間に置いて、並べ替え後の配列は【1、2、4、3、7、5】である.Step 6:秩序部分の無秩序部分は「/」で【1、2、4、7/5】を分割し、無秩序部分の最初の要素は5であり、順序部分の適切な位置、すなわち3と7の間に5を並べ替えて配列とする.【1、2、4、3、5、7】
アルゴリズムの実装
Insertion類
並べ替えアルゴリズムの性能を研究する時に、実験用の例を書いて実験をすることができます.以下はアルゴリズムの第四版SortCompre類を参照して書いた方法です.自分でNを調整することができます.Tの大きさを何度も検証します.私のコンピュータで並べ替えを選ぶ速度は大体挿入順序の1.7倍です.具体的な並べ替えアルゴリズムは上のテンプレートによって自分で書き出すことができます.
ソートアルゴリズムテンプレート(template for sorting algorithms)
， ， ， ， ， ， ， ， ， ， ， ， 。
//
Public static boolean less(Comparable c1, Comparable c2){
return c1.compareTo(c2) < 0;
}
//
Public static void exec(Comparable[] c,int I, int j){
Comparable c1 = c[i];
c[i] = c[j];
c[j] = c1;
}
//
Public static boolean isSorted(Comparable[] c){
for(int I = 0; I < c.length; i++){
if(less(c[i+1],c[i])) return false;
}
return true;
}
//
Public static void show(Comparable[] c){
for(int I = 0; I < c.length; i++)
// StdOut ，
StdOut.print(a[i] + “”);
StdOu.println();
}
//main
Public static void main(String[] args){
c；
sort(c);
// ，
assert isSorted(c);
show(c);
}
並べ替えの原理を選択
名前の通り、最小値を選択するたびに前に置いてください.配列【1、4、2、3、7、5】をStep 1に並べ替えます.最初のピットから配列を巡回し、最小値1を選んで、最初のピットの中にStep 2を入れます.2番目のピットから配列を遍歴し、最小値2を選択して、2番目のピットの中に入れます.Step 5:5番目のピットから配列を遍歴して、最小値5を選んで、5番目のピットの中に入れます.
アルゴリズムの実装
コードを下記のように整理します.
Selection
```
package sort;
/*
* ， ，
*/
public class Selection {
public static void sort(Comparable[] c) {
SortBasicClass sbc = new SortBasicClass();
for (int i = 0; i < c.length -1; i++) {
int min = i;
for (int j = i + 1; j < c.length; j++) {
//less ，
if (sbc.less(c[j], c[min])) {
min = j;
}
}
//exec ，
sbc.exec(c, i, min);
}
}
}
```
SortBasicClass （ ， ， ）
```
package sort;
import edu.princeton.cs.introcs.StdOut;
public class SortBasicClass {
// less ，
public static boolean less(Comparable c1, Comparable c2) {
return c1.compareTo(c2) < 0;
}
// exec ，
public static void exec(Comparable[] c, int i, int j) {
Comparable c1 = c[i];
c[i] = c[j];
c[j] = c1;
}
// isSorted ， ，
public static boolean isSorted(Comparable[] c) {
for (int i = 0; i < c.length; i++) {
for (int j = i + 1; j < c.length; j++) {
if (less(c[j], c[i]))
return false;
}
}
return true;
}
// show ，
public static void show(Comparable[] c) {
for (int i = 0; i < c.length; i++)
StdOut.print(c[i] + ",");
StdOut.println();
}
}
```
SortTestClass （ ，main ）
```
package sort;
import java.util.Random;
import java.util.Scanner;
import edu.princeton.cs.introcs.StdRandom;
public class SortTestClass {
public static void main(String args[]) {
SelectionTest();
}
// ，
public static void SelectionTest() {
System.out.println("please input...");
Scanner sc = new Scanner(System.in);
char[] ch = sc.nextLine().toCharArray();
Comparable[] c = new Comparable[ch.length];
for (int i = 0; i < ch.length; i++) {
c[i] = ch[i];
}
Selection.sort(c);
assert SortBasicClass.isSorted(c);
SortBasicClass.show(c);
}
}
```
並べ替えの原理を挿入
配列を秩序化と無秩序の二つの部分に分けて,秩序化部分の適切な位置に順次,無秩序部分の要素を挿入した.配列【1、4、2、3、7、5】を例にとってStep 1:順序部分の無秩序部分は「/」で【1/4、2、3、7、5】を分割し、無秩序部分の最初の要素は4、4を順序部分の適切な位置すなわち1の後に配置し、並べ替え後の配列は【1、4、2、7、5】step 2:秩序部分の無秩序部分は‘3、【4/5】で分割されます.無秩序部分の最初の要素は2であり、2を秩序部分の適切な位置、すなわち1と4の間に置いて、並べ替え後の配列は【1、2、4、3、7、5】である.Step 6:秩序部分の無秩序部分は「/」で【1、2、4、7/5】を分割し、無秩序部分の最初の要素は5であり、順序部分の適切な位置、すなわち3と7の間に5を並べ替えて配列とする.【1、2、4、3、5、7】
アルゴリズムの実装
Insertion類
```
package sort;
/*
* ，
*/
public class Insertion {
public static void sort(Comparable[] c){
for (int i = 0; i < c.length; i++) {
for (int j = i; j >0 && SortBasicClass.less(c[j], c[j-1]); j--)
SortBasicClass.exec(c, j, j-1);
}
}
}
```
```
package sort;
import java.util.Random;
import java.util.Scanner;
import edu.princeton.cs.introcs.StdRandom;
public class SortTestClass {
public static void main(String args[]) {
InsertionTest();
}
//
public static void InsertionTest() {
Comparable[] c = new Comparable[100];
for (int i = 0; i < 100; i++) {
c[i] = StdRandom.uniform(1, 100);
// c[i] = Math.random();
}
Insertion.sort(c);
assert SortBasicClass.isSorted(c);
SortBasicClass.show(c);
}
}
```
並べ替えアルゴリズムの性能を研究する時に、実験用の例を書いて実験をすることができます.以下はアルゴリズムの第四版SortCompre類を参照して書いた方法です.自分でNを調整することができます.Tの大きさを何度も検証します.私のコンピュータで並べ替えを選ぶ速度は大体挿入順序の1.7倍です.具体的な並べ替えアルゴリズムは上のテンプレートによって自分で書き出すことができます.
SortCompare ：
```
package sort;
import edu.princeton.cs.introcs.StdOut;
import edu.princeton.cs.introcs.StdRandom;
import edu.princeton.cs.introcs.Stopwatch;
//
public class SortCompare {
public static void main(String [] args){
double SelectionTime = TimeRandomInput("Selection",100,20000);
double InsertionTime = TimeRandomInput("Insertion",100,20000);
StdOut.println("Selection costs " + SelectionTime + " seconds");
StdOut.println("Selection costs " + InsertionTime + " seconds");
StdOut.printf("Selection divided by Insertion is %.2f", SelectionTime/InsertionTime);
}
//
public static double time(String alg,Double[] d){
Stopwatch timer = new Stopwatch();
if(alg.equals("Selection")) Selection.sort(d);
if(alg.equals("Insertion")) Insertion.sort(d);
return timer.elapsedTime();
}
// ，
public static double TimeRandomInput(String alg,int N,int T){
double total = 0.0;
Double[] d = new Double[N];
for (int i = 0; i < T; i++) {
for (int j = 0; j < d.length; j++) {
d[j] = StdRandom.uniform();
}
total += time(alg,d);
}
return total;
}
}
```