逆転を狙う工大生の日々

絶賛留年中の落ちこぼれがなんとか頑張ろうとしている日記です

Javaで色んなソート-1-

ようやく半分のソートを実装しました・・・忙しくて更新出来ないかと思ったよ・・・

今回は、「バブルソート」「選択ソート」「挿入ソート」「シェルソート」「クイックソート」の5つを実装しました。

 

~各種ソートを取り揃えたクラス~

public class Sort {
	//配列をプリントする
	private static void print(int[] a){
		for(int i=0; i < a.length; i++){
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	//バブルソート
	public static void bubbleSort(int[] a){
		for(int i = 0; i < a.length-1; i++){
			print(a);
			for(int j = a.length-1; j > i; j--){
				if(a[j-1] > a[j]){
					int temp = a[j];
					a[j] = a[j-1];
					a[j-1] = temp;
				}
			}
		}
	}
	
	//選択ソート
	public static void serectionSort(int a[]){
		for(int i=0; i < a.length-1; i++){
			print(a);
			int min = a[i];
			int minkey = i;
			for(int j=i+1; j < a.length; j++){
				if(a[j] < min){
					min = a[j];
					minkey = j;
				}
			}
			int temp = a[i];
			a[i] = a[minkey];
			a[minkey] = temp;
		}

	}
    
	//挿入ソート
	public static void insertionSort(int[] a){
		print(a);
		for(int i=1; i < a.length; i++){
			int j=i;
			while(j >= 1 && a[j-1] > a[j]){
				int temp = a[j];
				a[j] = a[j-1];
				a[j-1] = temp;
				j--;
			}
			print(a);
		}

	}
	
	//シェルソート
	public static void shellSort(int[] a){
		print(a);
		int h=1; //hだけ離れた要素同士をソートする
		
		while(h < a.length){
			h = 3 * h + 1;
		}
		
		for(; h > 0; h /= 3){
			for(int i=h; i < a.length; i++){
				int j=i;
				while(j >= h && a[j-h] > a[j]){
					int temp = a[j];
					a[j] = a[j-1];
					a[j-1] = temp;
					j--;
				}				
			}
			print(a);
		}

	}
	
	//クイックソート用
	private static int partition(int[] a, int l, int r){
		int i = l-1;
		int j= r;
		
		int pivot = a[r];
		
		while(true){
			while(a[++i] < pivot)
				;
			while(pivot < a[j] && i < --j)
				;
			
			if(i >= j) break;
			
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		int temp = a[i];
		a[i] = a[r];
		a[r] = temp;
		return i;
	}
	
	//クイックソートを行う
	public static void quickSort(int[] a,int l,int r){
		if(l >= r) return;
			
		int v = partition(a,l,r);
		
		quickSort(a,l,v-1);
		quickSort(a,v+1,r);
	}
}

やはり上3つはコードも非常に単純明快ですね。シェルソートも原理は挿入ソートみたいなものだしそんなに難しくなかったですが、クイックソートはやはり難しいですね。再帰嫌い。 まだまだソートアルゴリズムいっぱいある上にどんどん重たいアルゴリズムになっていくので、今後は1つずつとかになりそうです。

~実行結果~


public class Main {
	public static void main(String[] args) {
		System.out.println("-------バブルソートの実行-------");
		int[] a = {7,5,8,3,2,9,1,10,4,6};
		Sort.bubbleSort(a);
		System.out.println("-----------ソート完了----------");
		
		System.out.println();
		
		System.out.println("--------選択ソートの実行--------");
		int[] b = {7,5,8,3,2,9,1,10,4,6};
		Sort.serectionSort(b);
		System.out.println("------------ソート完了-----------");
		
		System.out.println();
		
		int[] c = {7,5,8,3,2,9,1,10,4,6};
		System.out.println("--------挿入ソートの実行--------");
		Sort.insertionSort(c);
		System.out.println("------------ソート完了-----------");
		
		System.out.println();
		
		int[] d = {7,5,8,3,2,9,1,10,4,6};
		System.out.println("--------シェルソートの実行--------");
		Sort.shellSort(d);
		System.out.println("------------ソート完了-----------");
		
		System.out.println();
		
		int[] e = {7,5,8,3,2,9,1,10,4,6};
		Sort.quickSort(e, 0, e.length-1);
		System.out.println("--------クイックソートの実行--------");
		for(int i=0; i < a.length; i++){
			System.out.print(a[i] + " ");
		}
		System.out.println();	
		System.out.println("------------ソート完了-----------");
	}

クイックソートだけ表示がうまく出来なかった・・・まだ理解しきれてないね・・・

f:id:ikuth:20140518233653p:plain

ソートは出来てますね。クイックソートもう一度頭冷やして見直します。