- バブルソート...隣接するデータを比較して順番が正しくない場合入れ替えるのを端まで繰り返す。一周ごとに要素が一つ確定する。O(n^2)
- 挿入ソート...あるデータとソートされた領域の要素を順番に比較し、正しい位置に挿入するのを端まで繰り返す。O(n^2)
- 選択ソート...データの最小値を特定し先頭と入れ替える。それ以降の要素から最小値を検索し先頭と入れ替えるのを全データ配置まで繰り返す。O(n^2)
- クイックソート...データをある値以上とそれ未満に分ける、分離し他グループでそれぞれ繰り返しグループの要素が1になるまで繰り返す。O(n log n)
- シェルソート...一定間隔おきの要素を整列する。幅が1になるまで狭めながら繰り返す。O(n log n)
- ヒープソート...ヒープ木の根を最後に格納し、ヒープ木を再構成し根をその前に格納するのをすべての要素が格納されるまで繰り返す
ソートアルゴリズムを実装する
バブルソート
package sort;
public class sort {
private static int order;
private static int reference;
private static void print() {
System.out.println("order: "+order+" reference: "+reference);
}
private static void reset() {
order=0;
reference=0;
}
public static void bubblesort(int[] data) {
reset();
for(int i=0;i<data.length;i++) {
for(int j=i;j<data.length;j++) {
if(data[i] > data[j]) {
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
order++;
}
reference++;
}
}
print();
reset();
}
}
package sort;
public class main {
public static void main(String[] args) {
int[] data = {62,2,91,34,55,19,83,7,41,68,99,13,47,26,74,5,88,30,52,79,11,94,4,60,22,86,37,1,71,44,100,58,25,82,16,49,9,66,93,28,77,3,54,39,85,6,64,15,42,20,97,33,70,51,8,46,90,12,75,23,61,31,96,50,17,81,36,65,43,10,59,24,84,69,40,92,27,57,14,73,48,21,95,32,78,56,80,35,63,98,45,18,72,29,53,87,38,67,76,89};
sort.bubblesort(data);
for(int i:data) {
System.out.print(i+" ");
}
System.out.println();
}
}
出力
データが整列状態に違いほど処理回数は減少しますが、参照回数は一定です
order: 2250 reference: 5050
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
挿入ソート
public static ArrayList<Integer> insertsort(int[] data) {
reset();
ArrayList<Integer> sorteddata = new ArrayList<Integer>();
sorteddata.add(data[0]);
for(int i=1;i<data.length;i++) {
int length=sorteddata.size();
for(int j=0;j<length;j++) {
if(data[i] < sorteddata.get(j)) {
sorteddata.add(j, data[i]);
break;
}else if(j==length-1) {
sorteddata.add(data[i]);
}
order++;
reference++;
}
}
print();
reset();
return sorteddata;
}
package sort;
public class main {
public static void main(String[] args) {
int[] data = {62,2,91,34,55,19,83,7,41,68,99,13,47,26,74,5,88,30,52,79,11,94,4,60,22,86,37,1,71,44,100,58,25,82,16,49,9,66,93,28,77,3,54,39,85,6,64,15,42,20,97,33,70,51,8,46,90,12,75,23,61,31,96,50,17,81,36,65,43,10,59,24,84,69,40,92,27,57,14,73,48,21,95,32,78,56,80,35,63,98,45,18,72,29,53,87,38,67,76,89};
for(int i:sort.insertsort(data)) {
System.out.print(i+" ");
}
System.out.println();
}
}
出力
挿入ソートでは正しい位置にのみ挿入を行うので変更回数はnとなりますが、参照回数は多いです
order: 99 reference: 2700
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
選択ソート
public static void selectionsort(int[] data) {
reset();
for(int i=0;i<data.length;i++) {
int minnumber=i;
for(int j=i;j<data.length;j++) {
if(data[minnumber]>data[j]) {
minnumber=j;
}
reference++;
}
int tmp=data[i];
data[i] = data[minnumber];
data[minnumber] = tmp;
order++;
}
print();
reset();
}
package sort;
public class main {
public static void main(String[] args) {
int[] data = {62,2,91,34,55,19,83,7,41,68,99,13,47,26,74,5,88,30,52,79,11,94,4,60,22,86,37,1,71,44,100,58,25,82,16,49,9,66,93,28,77,3,54,39,85,6,64,15,42,20,97,33,70,51,8,46,90,12,75,23,61,31,96,50,17,81,36,65,43,10,59,24,84,69,40,92,27,57,14,73,48,21,95,32,78,56,80,35,63,98,45,18,72,29,53,87,38,67,76,89};
sort.selectionsort(data);
for(int i:data) {
System.out.print(i+" ");
}
System.out.println();
}
}
出力
同様に変更回数はnですが、参照回数はバブルソートと同じです
order: 100 reference: 5050
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
クイックソート
public static void quicksort(int[] data) {
reset();
quicksortfunction(data,0,data.length-1);
print();
reset();
}
private static void quicksortfunction(int[] data,int left,int right) {
//終了条件
if(left>=right) {
return;
}
int pivotindex=left;
int pivot=data[right];
//pivotでの分割
for(int i=left;i<right;i++) {
if(data[i]<pivot) {
int tmp=data[pivotindex];
data[pivotindex]=data[i];
data[i]=tmp;
pivotindex++;
order++;
}
reference++;
}
data[right] = data[pivotindex];
data[pivotindex] = pivot;
//次の分割の呼び出し
quicksortfunction(data,left,pivotindex-1);
quicksortfunction(data,pivotindex,right);
}
package sort;
public class main {
public static void main(String[] args) {
int[] data = {62,2,91,34,55,19,83,7,41,68,99,13,47,26,74,5,88,30,52,79,11,94,4,60,22,86,37,1,71,44,100,58,25,82,16,49,9,66,93,28,77,3,54,39,85,6,64,15,42,20,97,33,70,51,8,46,90,12,75,23,61,31,96,50,17,81,36,65,43,10,59,24,84,69,40,92,27,57,14,73,48,21,95,32,78,56,80,35,63,98,45,18,72,29,53,87,38,67,76,89};
sort.quicksort(data);
for(int i:data) {
System.out.print(i+" ");
}
System.out.println();
}
}
出力
変更回数は増えますが、参照回数を大幅に短縮できます
order: 558 reference: 768
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
シェルソート
public static void shellsort(int[] data) {
reset();
for(int range=data.length/2;range>0;range--) {
for(int i=0;i+range<data.length;i++) {
if(data[i]>data[i+range]){
int tmp=data[i];
data[i]=data[i+range];
data[i+range]=tmp;
order++;
}
reference++;
}
}
print();
reset();
}
package sort;
public class main {
public static void main(String[] args) {
int[] data = {62,2,91,34,55,19,83,7,41,68,99,13,47,26,74,5,88,30,52,79,11,94,4,60,22,86,37,1,71,44,100,58,25,82,16,49,9,66,93,28,77,3,54,39,85,6,64,15,42,20,97,33,70,51,8,46,90,12,75,23,61,31,96,50,17,81,36,65,43,10,59,24,84,69,40,92,27,57,14,73,48,21,95,32,78,56,80,35,63,98,45,18,72,29,53,87,38,67,76,89};
sort.shellsort(data);
for(int i:data) {
System.out.print(i+" ");
}
System.out.println();
}
}
出力
バブルソートと似たような処理を行っていますが、バブルソートに比べて変更、参照回数を削減できます
order: 474 reference: 3725
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
ヒープソート
実装が面倒そうなのでやる気出たらやります