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

Ответ 1

Оказывается, это не так сложно, как вы думаете. Синтаксис уродливый, но пакетный синтаксис действительно способен на некоторые удивительные вещи, включая рекурсию, локальные переменные и некоторые удивительно сложные синтаксические разборки строк. Не поймите меня неправильно, это ужасный язык, но, к моему удивлению, он не полностью искалечен. Я не думаю, что узнал что-нибудь о quicksort, но я много узнал о пакетных файлах.

В любом случае, здесь quicksort в пакетном файле - и я надеюсь, что у вас будет так много удовольствия, пытаясь понять причудливый синтаксис, читая его, как я это делал при написании.: -)

@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

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

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

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

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

Ответ 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 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