Created
September 16, 2012 08:35
-
-
Save emergent/3731596 to your computer and use it in GitHub Desktop.
ソートアルゴリズムをJAVAで実装してみる練習
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class BubbleSort extends Sorter { | |
BubbleSort(boolean debug) { | |
super(debug); | |
} | |
public int[] sort(int[] arr, int start, int end) { | |
printArray(arr); | |
if (end > arr.length-1) { return null; } | |
for (int i=start; i < end; i++) { | |
int tmp; // for swap | |
for (int j=end; j>=i+1; j--) { | |
if (arr[j] < arr[j-1]) { | |
tmp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = tmp; | |
printArray(arr); | |
} | |
} | |
} | |
return arr; | |
} | |
/* このクラスのテスト用main */ | |
public static void main(String[] args) { | |
int[] arr1 = { 3, 7, 1, 2, 6, 4, 5, 0 }; | |
int[] arr2 = { 6, 1, 12, 3, 4 }; | |
BubbleSort bs = new BubbleSort(true); | |
bs.sort(arr1); | |
bs.clearCount(); | |
bs.sort(arr2); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
class Sorter { | |
private boolean debug = false; | |
Sorter(boolean debug) { | |
this.debug = debug; | |
} | |
Sorter() { | |
this(true); | |
} | |
/** | |
* これをオーバーライドすること | |
*/ | |
public int[] sort(int[] arr, int start, int end) { | |
printArray(arr); | |
// 仮のバブルソート実装 | |
if (end > arr.length-1) { return null; } | |
for (int i=start; i < end; i++) { | |
int tmp; // for swap | |
for (int j=end; j>=i+1; j--) { | |
if (arr[j] < arr[j-1]) { | |
tmp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = tmp; | |
printArray(arr); | |
} | |
} | |
} | |
return arr; | |
} | |
public int[] sort(int[] arr, int start) { | |
return this.sort(arr, start, arr.length-1); | |
} | |
public int[] sort(int[] arr) { | |
return this.sort(arr, 0); | |
} | |
protected static String a2s(int[] arr) { | |
return Arrays.toString(arr); | |
} | |
protected static void printArray(String prefix, int[] arr) { | |
System.out.println(prefix + a2s(arr)); | |
} | |
static int count = 0; | |
protected void printArray(int[] arr) { | |
if (debug) { | |
System.out.println("[step "+(count++)+"]\t"+ a2s(arr)); | |
} | |
} | |
protected void clearCount() { count = 0; } | |
public static void main(String[] args) { | |
int[] arr = {2,4,10,1,6,11,9}; | |
Sorter s = new Sorter(); | |
System.out.println("result => "+Arrays.toString(s.sort(arr))); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
bubble sort | |
bucket sort | |
radix sort | |
heap sort | |
quick sort | |
merge sort | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment