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

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