Как реализовать быструю сортировку с помощью командного файла?

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

Код немного труден для понимания. Это в основном стандартная быстрая сортировка. Ключевыми моментами являются то, что мы храним числа в строке - массиве бедняков. Второй цикл for довольно неясен, он в основном разбивает массив на голову (первый элемент) и хвост (все остальные элементы). Haskell делает это с помощью обозначения x:xs, но пакетные файлы делают это с помощью цикла for, вызываемого с помощью ключа /f. Зачем? Почему бы и нет?

Вызовы SETLOCAL и ENDLOCAL позволяют нам делать локальные переменные - вроде. SETLOCAL дает нам полную копию исходных переменных, но все изменения полностью стираются, когда мы вызываем ENDLOCAL, что означает, что вы даже не можете общаться с вызывающей функцией, используя глобальные переменные. Это объясняет уродливый синтаксис "ENDLOCAL & set return=%sorted%", который на самом деле работает, несмотря на то, что указывает логика. Когда строка выполняется, отсортированная переменная не была стерта, потому что строка еще не была выполнена - затем возвращаемая переменная не стирается, потому что строка уже была выполнена. Логическое!

Кроме того, забавно, что вы в принципе не можете использовать переменные внутри цикла for, потому что они не могут изменяться - что устраняет большую часть смысла цикла for. Обходной путь должен установить ENABLEDELAYEDEXPANSION, который работает, но делает синтаксис даже более уродливым, чем обычно. Обратите внимание, что теперь у нас есть набор переменных, на которые ссылаются только по их имени, с префиксом их одним%, с префиксом двух%, с оберткой в% или с обручем! И эти разные способы обращения к переменным практически полностью НЕ взаимозаменяемы!

Кроме этого, это должно быть относительно легко понять!

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