[アルゴリズム] マージソートのプログラミング(Shell編)

2017年3月16日

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

予想通りShellでの配列操作は非常に難関です。 今回行ったマージソートは、部分的に切り取った配列を渡して渡した配列をソートして返すという関数が重要な要素なので、なるべくフローを変えない為に、渡すデータは配列ではなく、「,(カンマ)」区切りの文字列でCSV形式で行うようにしました。 すると、意外とグローバル変数を意識せずに行うようにできたので、非常にオススメです。 ただし、注意点として、グローバル変数として存在するので、常に変数を上書きする、上書きしない時は、リセットするようにclearするようにコーディングしましょう。 そして、この影響で今までと違っている点として、実行コマンドで受け渡す値も、カンマ区切りデータにしています。 個人的にはこれでかなりオブジェクト指向対応ができるので、今までのソースも書き直したい感じです。

ソースコード

#!/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[@]}

実行

$ bash mergeSort.sh 10,2,12,7,16,8,13 2,7,8,10,12,13,16

解説

shellの配列操作いろいろ

# 空配列の定義 arr=() # 配列の追加(後ろに追加) arr+=( 1 ) # 配列の先頭を削除(破壊的操作)※1の値は先頭から○番目 arr=(${arr[@]:1}) # 配列の特定範囲を取り出す(slice)※2番めから3つ分 arr=(${arr[@]:2:3}) # 文字列をsplit処理「,(カンマ)区切り」 str=( `echo arr | tr -s ',' ' '`) # 配列をjoin「,(カンマ)区切り」にする arr=(`echo str | tr -s ',' ' '`)

四捨五入

num=`echo "(21 / 2) + 0.5" | bc -l | perl -ne 'print int($_)'` > 11

while文の複数条件

## AND while [ (条件文1) ] && [ (条件文2) ];do ... done ## OR while [ (条件文1) ] || [ (条件文2) ];do ... done

関連記事

たくさんのプログラム言語でアルゴリズム学習

このブログを検索

ごあいさつ

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