Ruby - 自作ソート(再帰)

初めてのプログラミング 第2版
Chris Pine (著) 長尾 高弘 (訳)

開発環境

• OS X Lion - Apple(OS)
• BBEdit - Bare Bones Software, Inc.(Text Editor)
• Script言語:Ruby

『初めてのプログラミング 第2版』(Chris Pine　著、長尾 高弘　訳、オライリー・ジャパン、2010年、ISBN978-4-87311-469-9)の 10章(章全部で復習), 10.2(通過儀礼としてのソート)再帰 を解いてみる。

その他参考書籍

• 『プログラミング言語 Ruby』David Flanagan, まつもと ゆきひろ　著 、卜部 昌平　監訳、長尾 高弘　訳、オライリー・ジャパン、2009年、ISBN978-4-87311-394-4)
• Rubyクックブック ―エキスパートのための応用レシピ集

再帰

コード(BBEdit)

sample.rb

#!/usr/bin/env ruby1.9
#-*- coding: utf-8 -*-

def sort some_array
  recursive_sort some_array, []
end

def recursive_sort unsorted_array, sorted_array
  a = unsorted_array[0, unsorted_array.length]
  return sorted_array if a.length == 0
  min = a.pop
  tmp = []
  a.each do |item|
    if item.to_s < min.to_s
      tmp.push min
      min = item
    else
      tmp.push item
    end
  end
  sorted_array.push min
  recursive_sort tmp, sorted_array
end

a = ['e','a','d','b','c', 5, 1, 4, 2, 3]
sorted_a = sort a
puts "ソート前: #{a}"
puts "ソート後: #{sorted_a}"

入出力結果(Terminal)

$ ./sample.rb
ソート前: ["e", "a", "d", "b", "c", 5, 1, 4, 2, 3]
ソート後: [1, 2, 3, 4, 5, "a", "b", "c", "d", "e"]
$

ちなみにJavaScriptの場合。

コード(BBEdit)

function sort(a){
    return recursive_sort(a, []);
}
function recursive_sort( unsorted_a, sorted_a){
    var a = unsorted_a.slice(0);
    if ( a.length == 0 ){
        return sorted_a;
    }
    var min,
        tmp,
        i,
        max;
    min = a.pop();
    tmp = [];
    for(i = 0, max = a.length; i < max; i += 1){
        if ( (a[i]).toString() < (min).toString()){
            tmp.push(min);
            min = a[i];
        } else {
            tmp.push( a[i] );
        }
    }
    sorted_a.push( min );
    return recursive_sort( tmp, sorted_a);
}
var a = ['e', 'a', 'd', 'b', 'c', 5, 1, 4, 2, 3];
var sorted_a = sort( a );
var result = "ソート前: " + a.join(" ") + "\n" +
    "ソート後: " + sorted_a.join(" ") + "\n";
$('#pre0').text(result);

pythonの場合。

sample.py

コード(BBEdit)

#!/usr/bin/env python3.3
#-*- coding: utf-8 -*-

def sort( some_list ):
    return recursive_sort( some_list, [])


def recursive_sort(unsorted_list, sorted_list):
    l = unsorted_list[0:]
    if len(l) == 0:
        return sorted_list
    min = l.pop()
    tmp = []
    for item in l:
        if str( item ) < str( min ):
            tmp.append( min )
            min = item
        else:
            tmp.append( item )
    sorted_list.append(min)
    return recursive_sort( tmp, sorted_list )

l = ['e','a','d','b','c', 5, 1, 4, 2, 3]
sorted_l = sort( l )
print("ソート前: {0}".format( l ))
print("ソート後: {0}".format(sorted_l))

入出力結果(Terminal)

$ ./sample.py
ソート前: ['e', 'a', 'd', 'b', 'c', 5, 1, 4, 2, 3]
ソート後: [1, 2, 3, 4, 5, 'a', 'b', 'c', 'd', 'e']
$

perlの場合。

sample.pl

コード(BBEdit)

#!/usr/bin/env perl
use strict;
use warnings;
use utf8;
use 5.016;
binmode STDIN, ":utf8";
binmode STDOUT, ":utf8";

sub my_sort{
  my $a = shift;
  recursive_sort( $a, []);
}

sub recursive_sort{
  my($unsorted_a, $sorted_a) = @_;
  my @a = @$unsorted_a;
  return $sorted_a if  @a == 0;
  my $min = pop @a;
  my @tmp = ();
  for ( @a ){
    if ( $_ le $min ){
      push @tmp, $min;
      $min = $_;
    } else {
      push @tmp, $_;
    }
  }
  push @$sorted_a, $min;
  recursive_sort( \@tmp, $sorted_a);
}

my @a = (5, 1, 4, 2, 3, 'e', 'a', 'd','b','c');
my $sorted_a = my_sort( \@a );
print "ソート前: @a\n";
print "ソート後: @$sorted_a\n";

入出力結果(Terminal)

$ ./sample.pl
ソート前: 5 1 4 2 3 e a d b c
ソート後: 1 2 3 4 5 a b c d e
$