開発環境
- OS X Lion - Apple(OS)
- TextWrangler(Text Editor) (BBEditの機能制限無料版、light版)
- Script言語:Ruby
『初めてのプログラミング 第2版』(Chris Pine 著、長尾 高弘 訳、オライリー・ジャパン、2010年、ISBN978-4-87311-469-9)の 10章(章全部で復習), 10.2(通過儀礼としてのソート)再帰 を解いてみる。
その他参考書籍
- 『プログラミング言語 Ruby』David Flanagan, まつもと ゆきひろ 著 、卜部 昌平 監訳、長尾 高弘 訳、オライリー・ジャパン、2009年、ISBN978-4-87311-394-4)
- Rubyクックブック ―エキスパートのための応用レシピ集
再帰
コード(TextWrangler)
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 = Array.new(unsorted_array)
return sorted_array if unsorted_array.length == 0
min = a.pop
tmp = []
a.each do |item|
if min.to_s < item.to_s # 数値と文字列を比較できるように文字列で統一
tmp.push(item)
else
tmp.push(min)
min = item
end
end
sorted_array.push(min)
recursive_sort tmp, sorted_array
end
a1 = [5,1,4,2,3]
a2 = %w[e a d b c]
a3 = [5, 'e', 1, 'a', 4, 'd', 2, 'b', 3, 'c']
[a1, a2, a3].each do |a|
sorted_a = sort a
puts "ソート前: #{a}"
puts "ソート後: #{sorted_a}"
end
入出力結果(Terminal)
$ ./sample.rb ソート前: [5, 1, 4, 2, 3] ソート後: [1, 2, 3, 4, 5] ソート前: ["e", "a", "d", "b", "c"] ソート後: ["a", "b", "c", "d", "e"] ソート前: [5, "e", 1, "a", 4, "d", 2, "b", 3, "c"] ソート後: [1, 2, 3, 4, 5, "a", "b", "c", "d", "e"] $
ちなみにJavaScriptの場合。
コード(TextWrangler)
var result = "";
function sort(some_array){
return recursive_sort(some_array, []);
}
function recursive_sort(unsorted_array, sorted_array){
// sliceにしてみたけど上手くいかなかったのでfor loopを使ってた元に戻す
var a = [];
for(var i = 0; i < unsorted_array.length; i++){
a[i] = unsorted_array[i];
}
if(unsorted_array.length === 0){
return sorted_array;
}
// sliceに変更
/* したら上手くいかなかった
var a = unsorted_array.slice();
*/
var min = a.pop();
var tmp = [];
for(var i = 0; i < a.length; i++){
if((new String(min)) < (new String(a[i]))){
tmp.push(a[i]);
} else {
tmp.push(min);
min = a[i];
}
}
sorted_array.push(min);
return recursive_sort(tmp, sorted_array);
}
var a1 = [5,1,4,2,3];
var a2 = "eadbc".split("");
var a3 = [5, 'e', 1, 'a', 4, 'd', 2, 'b', 3, 'c'];
var a = [a1, a2, a3];
for(var i = 0; i < a.length; i++){
var sorted_a = sort(a[i]);
result += "ソート前: " + a[i] + "\n" +
"ソート後: " + sorted_a + "\n";
}
$('#pre0').text(result);
pythonの場合。
sample.py
コード(TextWrangler)
#!/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[:]
if len(unsorted_list) == 0:
return sorted_list
min = l.pop()
tmp = []
for x in l:
if str(min) < str(x):
tmp.append(x)
else:
tmp.append(min)
min = x
sorted_list.append(min)
return recursive_sort(tmp, sorted_list)
l1 = [5,1,4,2,3]
l2 = ['e','a','d','b','c']
l3 = [5, 'e', 1, 'a', 4, 'd', 2, 'b', 3, 'c']
for l in [l1,l2,l3]:
sorted_l = sort(l)
print("ソート前: {0}".format(l))
print("ソート後: {0}".format(sorted_l))
入出力結果(Terminal)
$ ./sample.py ソート前: [5, 1, 4, 2, 3] ソート後: [1, 2, 3, 4, 5] ソート前: ['e', 'a', 'd', 'b', 'c'] ソート後: ['a', 'b', 'c', 'd', 'e'] ソート前: [5, 'e', 1, 'a', 4, 'd', 2, 'b', 3, 'c'] ソート後: [1, 2, 3, 4, 5, 'a', 'b', 'c', 'd', 'e'] $
perlの場合。
sample.pl
コード(TextWrangler)
#!/usr/bin/env perl
use strict;
use warnings;
use utf8;
use 5.016;
binmode STDIN, ":utf8";
binmode STDOUT, ":utf8";
sub sort{
my $some_array = shift;
my @unsorted_array = ();
recursive_sort($some_array, \@unsorted_array);
}
sub recursive_sort{
my($unsorted_array, $sorted_array) = @_;
my $a = @$unsorted_array;
return @$sorted_array if length $unsorted_array == 0;
my $min = pop @$unsorted_array;
my @tmp = ();
for(@$a){
if($min < $_){
push @tmp, $_;
} else {
push @tmp, $min;
$min = $_;
}
}
push @$sorted_array, $min;
recursive_sort(\@tmp, $sorted_array);
}
my @a1 = (5,1,4,2,3);
my @a2 = qw(e a d b c);
my @a3 = (5, 'e', 1, 'a', 4, 'd', 2, 'b', 3, 'c');
for(\@a1, \@a2, \@a3){
my @sorted_a = sort @$_;
print "ソート前: @$_\n";
print "ソート後: @sorted_a\n"
}
入出力結果(Terminal)
$ ./sample.pl ソート前: 5 1 4 2 3 ソート後: 1 2 3 4 5 ソート前: e a d b c ソート後: a b c d e ソート前: 5 e 1 a 4 d 2 b 3 c ソート後: 1 2 3 4 5 a b c d e $
0 コメント:
コメントを投稿