【Batch】スターリンソートという流行に乗り遅れた

#概要
粛清するソートが流行っていたようなので混ざりたかったけど、バッチファイルで作ろうとしたのがそもそもの間違いだった。
ただただ、変数の扱いが面倒くさかった。

バッチファイルで実装するのはこれ

ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる

— やんぎん (@4116You) July 28, 2019

#ソースコード

stalinsort.bat

@setlocal enabledelayedexpansion
@echo off
REM stalinsort.bat

set idx=0
set prev=0
for %%i in (%*) do (
  call :numchk %%i
  if errorlevel 1 (
    if !idx! gtr 0 (
      if %%i geq !prev! (
        set /a res[!idx!]=%%i
        set /a prev=%%i
        set /a idx=!idx!+1
      )
    ) else (
      set /a res[!idx!]=%%i
      set /a prev=%%i
      set /a idx=!idx!+1
    )
  )
)
for /l %%i in (0,1,%idx%) do (
  echo|set /p=!res[%%i]! 
)
goto :EOF

:numchk
set chknum=%1
if defined chknum set chknum=%chknum:0x=%
if defined chknum set chknum=%chknum:0X=%
if defined chknum set chknum=%chknum:0=%
if defined chknum set chknum=%chknum:1=%
if defined chknum set chknum=%chknum:2=%
if defined chknum set chknum=%chknum:3=%
if defined chknum set chknum=%chknum:4=%
if defined chknum set chknum=%chknum:5=%
if defined chknum set chknum=%chknum:6=%
if defined chknum set chknum=%chknum:7=%
if defined chknum set chknum=%chknum:8=%
if defined chknum set chknum=%chknum:9=%
if defined chknum set chknum=%chknum:-=%
if defined chknum (
  set /a tmpnum=%1
  if not !tmpnum!==0 (
    exit /b 1
  )
  exit /b 0
) else (
  exit /b 1
)

#実行結果

> stalinsort.bat 1 2 3 4 5
  1 2 3 4 5
> stalinsort.bat 5 4 3 2 1
  5
> stalinsort.bat 3 1 4 1 5 9 2
  3 4 5 9
> stalinsort.bat -4 -3 -1 -2 0 2 1 4 3 7 6 5
  -4 -3 -1 0 2 4 7
> stalinsort.bat 1 2 hoge 3 4 fuga 0x20 0377 0xff 0x1f 0x1FF
  1 2 3 4 32 255 255 511
(追記)
> stalinsort.bat -0xff -1 0x00 00 0X0 1 2 hoge 3 4 fuga 0x20 0377 0xff 0x1f 0x1FF
  -255 -1 0 0 0 1 2 3 4 32 255 255 511

#動作確認
Windows10 (バージョン1607)

#感想
感想と愚痴まじりの説明を少し書いておきますね。
内容はとてもネタな流れだけども一応は技術ネタ…のつもりではあるので

もっと効率の良い方法を指摘してくださる方がいるかもしれないですし

まず、バッチファイルの仕様上扱える数値は8進数、10進数、16進数で32bitの-2147483648～2147483647
文字列を弾きたかったのでset /aで変数に数値として入れようとしたところでドハマリ開始
set /a 式の動作がネックで、式内の数値以外の文字列は環境変数文字列として処理される。
そして、未定義の環境変数は0として処理される。
なので、文字列が入った瞬間にそれは数値じゃなかろうが0になってしまう

> stalinsort hoge fuga
  0 0

こんな結果が返ってきてしまうのである。
違う…こんなのは期待していない

だけどそもそも文字列なのか数値なのかを判断するようなコマンドはない。ないはず。。。

仕方がないので、最初に引数文字列から数値かそうじゃないかを判定するために関数もどきで文字列置換を使用して強引に判定処理
バッチファイルに関数はないけどラベルとcallでそれっぽいことはできるので

有効数値判定

:numchk
set chknum=%1
if defined chknum set chknum=%chknum:0x=%
if defined chknum set chknum=%chknum:0X=%
if defined chknum set chknum=%chknum:0=%
if defined chknum set chknum=%chknum:1=%
if defined chknum set chknum=%chknum:2=%
if defined chknum set chknum=%chknum:3=%
if defined chknum set chknum=%chknum:4=%
if defined chknum set chknum=%chknum:5=%
if defined chknum set chknum=%chknum:6=%
if defined chknum set chknum=%chknum:7=%
if defined chknum set chknum=%chknum:8=%
if defined chknum set chknum=%chknum:9=%
if defined chknum set chknum=%chknum:-=%
if defined chknum (
  set /a tmpnum=%1
  if not !tmpnum!==0 (
    exit /b 1
  )
  exit /b 0
) else (
  exit /b 1
)

やってるのは最初に引数に入ってきた文字列をchknumに代入
変数が空になると変数が未定義扱いになるのを利用して、definedで定義状態だったら数値を1つずつ除去
%chknum:0=%で0を''(空)に置換
最後に符号も除去して変数が未定義だったら数値のはず…
なんだけども、8進数や16進数を考えなきゃいけないので、set /a tmpnum=%1で0以外に変換できるかチェック~~(ただこれって0x00とか00が使えない問題があるんだけど解決できなかった)~~
(追記)0xや0Xを同様に置換することで0x00や0X00でも0扱いできました

文字列が全部削除できたらあとは前の要素と比較して順番になってなかったら捨てる。というか、前の要素以上の数値だけ配列もどきに代入
最後に配列もどきを出力して終わり。

1行ずつ出力していないのは最後に空文字が入っちゃってECHO は <OFF> です。って出力されちゃうから…
なので、プロンプト表示を使って1行に表示してます。

スターリンソート祭に参加しつつ久々にバッチファイルで書いてみようと思っただけにしては、非常に面倒でした。

結論として、こういうのは無理してバッチファイルで書く必要はないと思いました。
初版で変数の遅延展開のミスがあって変数展開に失敗しているの見落としてました。
実行結果がどうみても間違えてるのに文字列弾くのに集中してしまって思い切り見逃しました。

ちなみにバッチファイル以外でvimスクリプトで書いてみたのはブログの方に書きました(解説とか書きようもないのと…面倒臭さは変わらなかった)
スターリンソートっていうのが流行っていたらしい - 沖の雑記帳

#参照
計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell