挿入ソートのshell編ですが、Object思考でない言語の洗礼を受けた感じで非常に苦労させられました。
何が苦労したかというと、関数の受け渡し値が複数且つ、配列を含むと、うまくいかないことを思い知らされたのと、shell言語内で使用している変数は全てグローバル変数扱いとなってしまうので、変数名設計をしっかりしないといけないという事ですね。
少し長くなるプログラムでは、不具合が出た時に、原因究明と修正作業が非常に大変でしたね。
とりあえず、記事では、修正後の結果だけなので、あまり苦労が見えない形になっているのがもどかしいです。
ソースコード
#/bin/bash
function getConfirmLists(){
arr=()
for((j=0; j<${#numbers[@]}; j++)){
if [ $j -eq $1 ]; then
break
fi
#echo ${numbers[@]:$j:1}
arr[$j]=${numbers[@]:$j:1}
}
echo ${arr[@]}
}
function getInsertPlace(){
num=${#confirmLists[@]}
for((j=0; j<$num; j++)){
if [ $1 -lt ${confirmLists[@]:$j:1} ]; then
num=$j
break
fi
}
echo $num
}
function getLastLists(){
for((j=($1+1); j<${#numbers[@]}; j++)){
echo ${numbers[@]:$j:1}
}
}
function setInsert(){
arr=()
for((j=0; j<${#confirmLists[@]}; j++)){
if [ $j -eq $2 ];then
#arr=("${arr[@]}" $1)
arr+=( $1 )
fi
#arr=("${arr[@]}" ${confirmLists[p]:$j:1})
arr+=( ${confirmLists[@]:$j:1} )
}
if [ ${#confirmLists[@]} -eq ${#arr[@]} ];then
#arr=("${arr[@]}" $1)
arr+=( $1 )
fi
echo ${arr[@]}
}
# 受け渡し値の取得
numbers=($@)
# 数値配列を最初から順番に評価していく
for((i=1; i<(${#numbers[@]}); i++)){
# 対象の数値取得
targetNum=${numbers[@]:$i:1}
# 確定数値リストを取得
confirmLists=(`getConfirmLists $i`)
# 確定数値リストに対象getInsertPlace数値が挿入される位置を取得する
replaceNum=`getInsertPlace $targetNum`
# 対象外の数値リストを取得
lastLists=(`getLastLists $i`)
# 確定数値リストに挿入数値の挿入
firstLists=(`setInsert $targetNum $replaceNum`)
# リストの結合
numbers=(${firstLists[@]} ${lastLists[@]})
}
echo ${numbers[@]}
解説
配列に値を追加
他の言語ではpushとかappendとなるところが、shellでは、下記のような書き方で配列の値追加を行うことができます。
特定の基本関数があるわけではなく、意外とアナログな書き方にビックリしました。
# 書き方その１
arr=(1 2 3)
arr+=(4)
> 1 2 3 4
# 書き方その２
arr=(1 2 3)
arr=(${arr[@]} 4)
> 1 2 3 4
２つの配列どうしの結合
numbers=(${firstLists[@]} ${lastLists[@]})
この箇所ですが、値の追加とやり方が似ているので、さほど説明はいらないでしょう。
関数の戻り値を配列で受け取る
confirmLists=(`getConfirmLists $i`)
()で囲って上げるだけ内部でechoされた個数に応じて配列として受け取ることができます。
関数について
関数のルールはいくつかあることに気が付きました。
まず、関数はあまり階層的にしないほうがよく、階層は1階層で並列にした方がいいという事です。
理由としては、変数受け渡しがうまくできないので、ほぼグローバル変数で行うため、あまり関数に落とし込む意味が無いことと、グローバル変数を汚さないようにしなければいけないためですね。
そして、関数定義はプログラムファイル冒頭で行い、処理実行は関数定義のあとで行わなければいけないということですね。
Javascriptでも同じ事が起こりえますが、実行するときにメモリに関数が定義されていないとエラーになるからですね。
実行
$ sh insertSort.sh 10 2 12 7 16 8 13
2 7 8 10 12 13 16
今回は配列をコマンド実行時に直接入れるようにして汎用性を持たせてある。
数は任意で半角スペース区切りで実行できるのですが、上限値は検証していません。
有志の人がいれば、端末スペックと上限値などを調べてもらえると助かります。
関連リンク
いろいろなプログラム言語でアルゴリズム学習
0 件のコメント:
コメントを投稿