[アルゴリズム] マージソートのプログラミング（Shell編）
予想通りShellでの配列操作は非常に難関です。
今回行ったマージソートは、部分的に切り取った配列を渡して渡した配列をソートして返すという関数が重要な要素なので、
なるべくフローを変えない為に、渡すデータは配列ではなく、「,（カンマ）」区切りの文字列でCSV形式で行うようにしました。
すると、意外とグローバル変数を意識せずに行うようにできたので、非常にオススメです。
ただし、注意点として、グローバル変数として存在するので、常に変数を上書きする、上書きしない時は、リセットするようにclearするようにコーディングしましょう。
そして、この影響で今までと違っている点として、実行コマンドで受け渡す値も、カンマ区切りデータにしています。
個人的にはこれでかなりオブジェクト指向対応ができるので、今までのソースも書き直したい感じです。
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#!/bin/bash function midPoint(){ # 引き渡し文字列のsplit処理 numbers=( `echo $1 | tr -s ',' ' '`) # 四捨五入 num=`echo "(${#numbers[@]} / 2) + 0.5" | bc -l | perl -ne 'print int($_)'` echo $num } function setMerge(){ arr1=(`echo $1 | tr -s ',' ' '`) arr2=(`echo $2 | tr -s ',' ' '`) arr=() while [ ${#arr1[@]} -gt 0 ] || [ ${#arr2[@]} -gt 0 ];do if [ ${#arr1[@]} -eq 0 ];then arr+=( ${arr2[0]} ) arr2=(${arr2[@]:1}) elif [ ${#arr2[@]} -eq 0 ];then arr+=( ${arr1[0]} ) arr1=(${arr1[@]:1}) elif [ ${arr1[0]} -gt ${arr2[0]} ];then arr+=( ${arr2[0]} ) arr2=(${arr2[@]:1}) else arr+=( ${arr1[0]} ) arr1=(${arr1[@]:1}) fi done echo `echo ${arr[@]} | tr -s ' ' ','` } function mergeSort(){ # 引き渡し文字列のsplit処理 numbers=(`echo $1 | tr -s ',' ' '`) if [ ${#numbers[@]} -eq 0 ];then echo "" elif [ ${#numbers[@]} -eq 1 ];then echo `echo ${numbers[@]} | tr -s ' ' ','` elif [ ${#numbers[@]} -eq 2 ];then if [ ${numbers[@]:0:1} -gt ${numbers[@]:1:1} ];then tmp=${numbers[0]} numbers[0]=${numbers[1]} numbers[1]=${tmp} fi echo `echo ${numbers[@]} | tr -s ' ' ','` else num=`midPoint $1` # 配列を区切りポイントを元に2分割 arr1=(${numbers[@]:0:$num}) arr2=(${numbers[@]:$num}) # 配列の結合処理（文字列に変換） str1=`echo ${arr1[@]} | tr -s ' ' ','` str2=`echo ${arr2[@]} | tr -s ' ' ','` # 再帰的にマージソート処理 str1=`mergeSort $str1` str2=`mergeSort $str2` #echo $str1" - "$str2 # 2つの配列を結合 echo `setMerge $str1 $str2` fi } # 引数は,カンマ区切りの文字列で行う res=(`mergeSort $1`) echo ${res[@]} |
実行
|
1 2 |
$ bash mergeSort.sh 10,2,12,7,16,8,13 2,7,8,10,12,13,16 |
解説
shellの配列操作いろいろ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# 空配列の定義 arr=() # 配列の追加（後ろに追加） arr+=( 1 ) # 配列の先頭を削除（破壊的操作）※1の値は先頭から○番目 arr=(${arr[@]:1}) # 配列の特定範囲を取り出す（slice）※2番めから３つ分 arr=(${arr[@]:2:3}) # 文字列をsplit処理「,（カンマ）区切り」 str=( `echo arr | tr -s ',' ' '`) # 配列をjoin「,（カンマ）区切り」にする arr=(`echo str | tr -s ',' ' '`) |
四捨五入
|
1 2 |
num=`echo "(21 / 2) + 0.5" | bc -l | perl -ne 'print int($_)'` > 11 |
while文の複数条件
|
1 2 3 4 5 6 7 8 9 |
## AND while [ (条件文1) ] && [ （条件文2） ];do ... done ## OR while [ (条件文1) ] || [ （条件文2） ];do ... done |
リンク
マージソート記事
解説
JavaScript
PHP
Python
Shell