Last active
August 29, 2015 14:00
-
-
Save incheon/11130299 to your computer and use it in GitHub Desktop.
情報論理及び演習サンプルプログラム 2012年度後期第9回
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
// コマンドラインに引数として与えた整数(文字列を入力)を | |
// 昇順にソート | |
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(); | |
} | |
} |
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
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}" |
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
// コマンドライン引数として与えた整数(文字列として入力)を照準にソート | |
// 途中経過も出力 | |
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(); | |
} | |
} |
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
# 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}" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
バブルソート、クイックソートのいずれでもrubyだと 記述量が半分 で済んでいるのが分かります。
ただしrubyではオーバーロードがサポートされていないので、スクリプト言語によくある デフォルト値の指定 などを使って代用します。