Skip to content

Instantly share code, notes, and snippets.

@incheon incheon/BubbleSort.java
Last active Aug 29, 2015

Embed
What would you like to do?
情報論理及び演習サンプルプログラム 2012年度後期第9回
// コマンドラインに引数として与えた整数(文字列を入力)を
// 昇順にソート
public class BubbleSort {
public static void main(String[] args) {
int[] ary = new int[args.length];
convert(args, ary);
printAry(ary);
bubbleSort(ary);
printAry(ary);
}
public static void bubbleSort(int[] ary) {
for (int i=0; i < ary.length-1; i++) {
for (int j=ary.length-1; j>i; j--) {
if(ary[j-1]>ary[j])
swap(ary, j-1, j);
}
}
}
// ary[m]とary[n]を交換
public static void swap(int[] ary, int m, int n) {
int tmp = ary[n];
ary[n] = ary[m];
ary[m] = tmp;
}
public static void convert(String[] args, int[] ary) {
for (int i=0; i<args.length; i++) {
ary[i] = Integer.parseInt(args[i]);
}
}
public static void printAry(int[] ary) {
for (int i=0; i<ary.length; i++) {
System.out.println(" " + ary[i]);
}
System.out.println();
}
}
def bubbleSort(ary)
lim = ary.length-1 # 配列の上限
0.upto(lim) do |i|
lim.downto(i+1) do |j|
# rubyでは多重代入ができるのでswapメソッドを定義しなくてもよい
ary[j-1], ary[j] = ary[j], ary[j-1] if ary[j-1] > ary[j]
end
end
end
# 引数の明示的な型変換は一行で処理できるのでconvertメソッドを定義しなくてもよい
int_argv = ARGV.collect {|i| i.to_i}
puts "before".center(20, "*")
puts "#{int_argv.to_s}"
bubbleSort int_argv
puts "after".center(20, "*")
puts "#{int_argv.to_s}"
// コマンドライン引数として与えた整数(文字列として入力)を照準にソート
// 途中経過も出力
public class QuickSort {
public static void main(String[] args) {
int[] ary = new int[args.length];
convert(args, ary);
printAry(ary);
quickSort(ary);
printAry(ary);
}
// クイックソート
public static void quickSort(int[] ary) {
int left, right;
left = 0;
right = ary.length - 1;
quickSort(ary, left, right);
}
public static void quickSort(int[] ary, int left, int right) {
System.out.println("left = " + left + " right = " + right);
int tmpL = left; // tmpLの初期値
int tmpR = right; // tmpRの初期値
int pivot = ary[(left + right)/2]; // 枢軸(pivot)の設定
System.out.println("pivot = " + pivot);
while (tmpL <= tmpR) {
while(ary[tmpL] < pivot) tmpL++;
while(ary[tmpR] > pivot) tmpR--;
if(tmpL <= tmpR) {
swap(ary, tmpL, tmpR); // データの交換
tmpL++;
tmpR--;
}
}
printAry(ary);
printAry(ary);
if(left < tmpR) quickSort(ary, left, tmpR); // メソッドquickSortの再帰呼び出し
if(tmpL < right) quickSort(ary, tmpL, right); // メソッドquickSortの再帰呼び出し
}
// ary[m]とary[n]を交換
public static void swap(int[] ary, int m, int n) {
System.out.println("ary[" + m + "]=" + ary[m] + "とary[" + n + "]=" + ary[n] + "を交換");
int tmp = ary[n];
ary[n] = ary[m];
ary[m] = tmp;
}
public static void convert(String[] args, int[] ary) {
for (int i=0; i<args.length; i++) {
ary[i] = Integer.parseInt(args[i]);
}
}
public static void printAry(int[] ary) {
for (int i=0; i<ary.length; i++) {
System.out.println(" " + ary[i]);
}
System.out.println();
}
}
# rubyではオーバーロードが使えない
# def quickSort(ary)
# left = 0
# right = ary.length-1
# quickSort(ary, left, right)
# end
# よってここでは引数がひとつのquickSortメソッドのみを定義する
def quickSort(ary, left=0, right=ary.length-1)
tmpL, tmpR, pivot = left, right, ary[(left+right)/2]
puts "left=#{left} right=#{right} pivot=#{pivot}"
while tmpL <= tmpR
while ary[tmpL]<pivot do tmpL+=1 end
while ary[tmpR]>pivot do tmpR-=1 end
if tmpL <= tmpR
ary[tmpL], ary[tmpR] = ary[tmpR], ary[tmpL]
tmpL+=1
tmpR-=1
end
end
quickSort(ary, left, tmpR) if left<tmpR
quickSort(ary, tmpL, right) if tmpL<right
end
# 引数の明示的な型変換は一行で処理できるのでconvertメソッドを定義しなくてもよい
int_argv = ARGV.collect {|i| i.to_i}
puts "before".center(20, "*")
puts "#{int_argv.to_s}"
puts "calc".center(20, "*")
quickSort int_argv
puts "after".center(20, "*")
puts "#{int_argv.to_s}"
@incheon

This comment has been minimized.

Copy link
Owner Author

commented Apr 21, 2014

バブルソート、クイックソートのいずれでもrubyだと 記述量が半分 で済んでいるのが分かります。
ただしrubyではオーバーロードがサポートされていないので、スクリプト言語によくある デフォルト値の指定 などを使って代用します。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.