[アルゴリズム] 挿入ソートの実装(Shell編)

2017年1月26日

Shell テクノロジー プログラミング 特集

挿入ソートの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では、下記のような書き方で配列の値追加を行うことができます。 特定の基本関数があるわけではなく、意外とアナログな書き方にビックリしました。 # 書き方その1 arr=(1 2 3) arr+=(4) > 1 2 3 4 # 書き方その2 arr=(1 2 3) arr=(${arr[@]} 4) > 1 2 3 4

2つの配列どうしの結合

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 今回は配列をコマンド実行時に直接入れるようにして汎用性を持たせてある。 数は任意で半角スペース区切りで実行できるのですが、上限値は検証していません。 有志の人がいれば、端末スペックと上限値などを調べてもらえると助かります。

関連リンク

いろいろなプログラム言語でアルゴリズム学習

このブログを検索

ごあいさつ

このWebサイトは、独自思考で我が道を行くユゲタの少し尖った思考のTechブログです。 毎日興味がどんどん切り替わるので、テーマはマルチになっています。 もしかしたらアイデアに困っている人の助けになるかもしれません。