バッチファイルを使用してクイックソートを実装するにはどうすればよいですか?

Question

通常、常に仕事に適した言語を選択するのは良いことですが、まったく不適切な言語で何かをしようとすることが有益になる場合もあります。

1. 問題をより深く理解するのに役立ちます。たぶんあなたはそうしないでしょう 持っている 自分が思った通りに解決するために。
2. 言語をよりよく理解するのに役立ちます。もしかしたら、あなたが思っている以上に多くの機能をサポートしているかもしれません。

そして、このアイデアを非論理的な結論に押し進めると...バッチ ファイルでクイックソートを実装するにはどうすればよいでしょうか?それは可能ですか？

Answer 1

結局のところ、それはあなたが思っているほど難しくありません。構文は非常に醜いですが、バッチ構文は実際には、再帰、ローカル変数、驚くほど高度な文字列解析など、いくつかの驚くべき機能を備えています。誤解しないでください。これはひどい言語ですが、驚いたことに、完全に不自由になっているわけではありません。クイックソートについては何も学べなかったと思いますが、バッチ ファイルについては多くのことを学びました。

いずれにせよ、ここではバッチ ファイルでのクイックソートを示します。私が書いているときと同じように、この奇妙な構文を読みながら理解するのを楽しんでいただければ幸いです。:-)

@echo off
SETLOCAL ENABLEDELAYEDEXPANSION

call :qSort %*
for %%i in (%return%) do set results=!results! %%i
echo Sorted result: %results%
ENDLOCAL
goto :eof

:qSort
SETLOCAL
    set list=%*
    set size=0
    set less=
    set greater=
    for %%i in (%*) do set /a size=size+1
    if %size% LEQ 1 ENDLOCAL & set return=%list% & goto :eof
    for /f "tokens=2* delims== " %%i in ('set list') do set p=%%i & set body=%%j
    for %%x in (%body%) do (if %%x LEQ %p% (set less=%%x !less!) else (set greater=%%x !greater!))
    call :qSort %less%
    set sorted=%return%
    call :qSort %greater%
    set sorted=%sorted% %p% %return%
ENDLOCAL & set return=%sorted%
goto :eof

コマンドラインで並べ替える一連の数値をスペースで区切って指定して呼び出します。例：

C:\dev\sorting>qsort.bat 1 3 5 1 12 3 47 3
Sorted result:  1 1 3 3 3 5 12 47

コードを理解するのは少し面倒です。基本的には標準的なクイックソートです。重要な点は、数値を文字列 (貧乏人の配列) に格納していることです。2 番目の for ループは非常にわかりにくく、基本的に配列を先頭 (最初の要素) と末尾 (他のすべての要素) に分割します。Haskell はこれを x:xs という表記で実行しますが、バッチ ファイルでは /f スイッチを使用して呼び出される for ループで実行します。なぜ？なぜだめですか？

SETLOCAL 呼び出しと ENDLOCAL 呼び出しを使用すると、ローカル変数を実行できるようになります。SETLOCAL を使用すると、元の変数の完全なコピーが得られますが、ENDLOCAL を呼び出すとすべての変更が完全に消去されます。つまり、グローバルを使用して呼び出し元の関数と通信することさえできません。これは、ロジックがどのようなことを示すかに関係なく、実際には機能する醜い "ENDLOCAL & set return=%sorted%" 構文を説明しています。行が実行されるとき、その行はまだ実行されていないため、ソートされた変数はワイプされません。その後、行はすでに実行されているため、戻り値の変数はワイプされません。論理的です！

また、面白いことに、変数は変更できないため、基本的に for ループ内で変数を使用することはできません。これでは、for ループを使用する意味のほとんどが失われます。回避策は、ENABLEDELAYEDEXPANSION を設定することです。これは機能しますが、構文が通常よりもさらに醜くなります。ここでは、名前だけで参照される変数、1 つの % を先頭に付ける方法、2 つの % を先頭に付ける方法、% で囲む方法、または ! で囲む方法で参照される変数が混在していることに注目してください。そして、変数を参照するこれらのさまざまな方法は、ほぼ完全に互換性がありません。

それ以外は比較的わかりやすいと思います！

Answer 2

これは私が少し前に書いた、より読みやすいバージョンです。

@echo off

echo Sorting:  %*

set sorted=

:sort
:: If we've only got one left, we're done.
if "%2"=="" (
  set sorted=%sorted% %1
  :: We have to do this so that sorted gets actually set before we print it.
  goto :finalset
)
:: Check if it's in order.
if %1 LEQ %2 (
  :: Add the first value to sorted.
  set sorted=%sorted% %1
  shift /1
  goto :sort
)
:: Out of order.
:: Reverse them and recursively resort.
set redo=%sorted% %2 %1
set sorted=
shift /1
shift /1
:loop
if "%1"=="" goto :endloop
set redo=%redo% %1
shift /1
goto :loop
:endloop
call :sort %redo%
:: When we get here, we'll have already echod our result.
goto :eof

:finalset
echo Final Sort:  %sorted%
goto :eof

例：

C:\Path> sort 19 zebra blah 1 interesting 21 bleh 14 think 2 ninety figure it out

生成されるもの:

Sorting:  19 zebra blah 1 interesting 21 bleh 14 think 2 ninety figure it out
Final Sort:   1 2 14 19 21 blah bleh figure interesting it ninety out think zebra