[アルゴリズム] クイックソートの実装（Shell編）

WEBサービスを作っているエンジニアをしている場合、どのくらいの割合でShellスクリプトをコーディングするかを少し考えてみたが、サーバーバッチを作る時以外はないだろうと考えた。 ただ、個人的には、LinuxOSでは必ず動作するこの言語を利用しない手はなく、ちゃんとした書き方をしておけば、サーバー間における汎用性は半端なく高いのではないかと考えられるので、かなり強力なスクリプト言語だと考えてます。 そうそう、MacOSXもUNIXベースなので、Linuxと同じと考えてもいいですね。

ソース

#!/bin/sh function mid(){ x=$1 y=$2 z=$3 if [ $x -lt $y ]; then if [ $y -lt $z ]; then echo $y return elif [ $z -lt $x ]; then echo $x return else echo $z return fi else if [ $z -lt $y ]; then echo $y return elif [ $x -lt $z ]; then echo $x return else echo $z return fi fi } function quickSort(){ if [ $1 -ne -1 -a $2 -ne -1 ];then if [ `expr $end - $begin` -le 1 ];then echo ${numbers[@]} return fi fi begin=$1 if [ $begin -lt 0 ]; then begin=0 fi end=$2 if [ $end -lt 0 ]; then end=${#numbers[@]} end=`expr $end - 1` fi if [ $begin -ge $end ];then echo ${numbers[@]} return fi left=$begin right=$end center=`expr $right / 2` x=${numbers[@]:$left:1} y=${numbers[@]:$center:1} z=${numbers[@]:$right:1} pivot=`mid $x $y $z` while [ true ];do while [ ${numbers[@]:$left:1} -lt $pivot ];do left=`expr $left + 1` done while [ ${numbers[@]:$right:1} -gt $pivot ];do right=`expr $right - 1` done if [ $left -ge $right ];then break fi tmp=${numbers[@]:$left:1} tmp2=${numbers[@]:$right:1} numbers[$left]=$tmp2 numbers[$right]=$tmp left=`expr $left + 1` right=`expr $right - 1` break done numbers=(`quickSort $begin $left`) numbers=(`quickSort $right $end`) echo ${numbers[@]} return } # 受け渡し値の取得 numbers=($@) res=(`quickSort -1 -1`) echo ${res[@]}

実行

$ sh quickSort.sh 10 2 12 7 16 8 13 2 8 12 7 10 13 16 今回も乱数の値はプラスの整数しか受け付けていません。

解説

今までのSortプログラムの中で一番苦労しました。 それは、Shell言語における関数の配列受け渡しやif文に非常に強い癖のある条件がいくつかあるため、かなり難航しました。 下記ポイントをクリアしてなんとか完了することができました。

dockerのshellでfunctionがエラーになる

バージョンを確認してみる # docker $ set | grep -ai version BASH_VERSION='4.3.46(1)-release' _=--version # mac $ set | grep -ai version BASH_VERSION='3.2.57(1)-release' TERM_PROGRAM_VERSION=388 あれ？dockerの方がバージョンが新しい・・・ 別の原因ぽいので調査・・・

実行エラーの対応

プログラムを実行した際に下記のようなエラーが出た時の対応をどうするかメモしておきます。 $ sh quickSort.sh 10 2 12 7 16 8 13 quickSort.sh: line 55: [: -gt: unary operator expected quickSort.sh: line 64: 10[0]=: command not found quickSort.sh: line 65: 10[7]=10: command not found quickSort.sh: line 55: numbers[@]: 7+1s: value too great for base (error token is "1s")

unary operator expected

このエラーの場合は、変数の型がstringになっているのに、数値として扱おうとしている事が原因であることが多いみたいです。 if文やwhile文の条件判定式で、$leftとなっているところを"$left"と文字列化してあげるとうまくいきます。 数値のはずの変数の中に意図しない文字列が入ってしまっていないかチェックしてみましょう。 ちなみに、今回のこのエラーは、「7+1s」となっているエラーの箇所で意図しない「s」という文字が混入していました。 凡ミス！！！！！

計算式の注意点

他の言語のようにインクリメントを使ったりできないshell言語は、計算式の時にも作法があり、下記のような書き方をします。 a=1 b=2 res=`expr $a + $b` exprコマンドを通さないとイケないので、慣れないとめんどくさくて仕方がないです。 また、$a + $bも、半角スペースを入れないとエラーになります。 しかし下記のようにする事で計算は実行できますのでどちらか好きな方を使うのが良いでしょう。 res=`expr $a+$b|bc -l`

if文の制限

Shellスクリプトのif文は&&で条件をつなげる箇所に制限があるようです。 例えばJSで以下のように３つの条件をANDで繋いだとしたら、Shellはどう書くかをメモしておきます。 if(a==1 && b==2 && c==3){...} if [ $a -eq 1 ];then if [ $b -eq 1 ];then if [ $c -eq 1 ];then ... fi fi fi # または... if [ $a -eq 1 -a $b -eq 1 ];then if [ $c -eq 1 ];then ... fi fi あと、shellのif文の書き方は何パターンかありますが、この書き方の場合は、[]の中にちゃんと半角スペースを入れることを忘れないようにしましょう。 エラーになりますよ。

関連記事

アルゴリズム学習

• 解説
• Javascript
• PHP
• Python
• Shell
• AWK
• C言語
• Go言語
• Ruby