情報論理及び演習サンプルプログラム 2012年度後期第9回

BubbleSort.java

// コマンドラインに引数として与えた整数（文字列を入力）を
// 昇順にソート

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();
    }
}

BubbleSort.rb

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}"

QuickSort.java

// コマンドライン引数として与えた整数（文字列として入力）を照準にソート
// 途中経過も出力

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();
    }

}

QuickSort.rb

# 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}"

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