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

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