Como posso implementar quicksort usando um arquivo de lote?

Question

Enquanto normalmente é bom sempre escolher a linguagem certa para o trabalho, às vezes pode ser instrutivo para tentar fazer algo em uma língua que é descontroladamente impróprio.

1. Pode ajudá-lo a entender melhor o problema. Talvez você não Have para resolvê-lo da maneira que você pensou que você fez.
2. Pode ajudar você a entender melhor a língua. Talvez ele suporta mais recursos do que você realizou.

E empurrando essa idéia para a sua conclusão ilógica ... como é que você implementar quicksort em um arquivo de lote? Será que é mesmo possível?

Answer 1

Acontece, não é tão duro como você poderia pensar. A sintaxe é feio como o inferno, mas a sintaxe lote é realmente capaz de algumas coisas surpreendentes, incluindo recursão, variáveis ??locais, e alguns de análise surpreendentemente sofisticada de cordas. Não me interpretem mal, é uma linguagem terrível, mas para minha surpresa, ele não está completamente incapacitada. Eu não acho que eu aprendi alguma coisa sobre quicksort, mas eu aprendi muito sobre arquivos em lote!

Em qualquer caso, aqui está quicksort em um arquivo de lote - e eu espero que você se divirta tanto tentando entender a sintaxe bizarra enquanto lê-lo como eu fiz ao escrevê-lo. : -)

@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

Chamá-lo, dando-lhe um conjunto de números para classificar na linha de comando, separados por espaços. Exemplo:

C:\dev\sorting>qsort.bat 1 3 5 1 12 3 47 3
Sorted result:  1 1 3 3 3 5 12 47

O código é um pouco de dor de entender. É basicamente quicksort padrão. bits da chave são que nós estamos armazenando números em uma string - variedade do homem pobre. O segundo circuito é para bastante obscuro, é basicamente dividir a matriz em uma cabeça (o primeiro elemento) e uma cauda (todos os outros elementos). Haskell fá-lo com a notação x: xs, mas arquivos em lote fazê-lo com um loop for chamado com o / f switch. Por quê? Por que não?

O SETLOCAL e chamadas ENDLOCAL façamos variáveis ??locais - mais ou menos. SETLOCAL dá-nos uma cópia completa das variáveis ??originais, mas todas as alterações são completamente dizimado quando chamamos ENDLOCAL, o que significa que você não pode se comunicar mesmo com a função de chamada usando globals. Isso explica o feio "ENDLOCAL & conjunto de retorno =% ordenada%" sintaxe, que realmente funciona, apesar do que a lógica indicaria. Quando a linha é executada a variável ordenada não foi apagado porque a linha não foi executado ainda - então depois a variável de retorno não é apagado porque a linha já foi executado. ! Lógico

Além disso, divertidamente, basicamente você não pode usar variáveis ??dentro de um loop for porque eles não podem mudar - o que remove a maior parte do ponto de ter um loop. A solução é ENABLEDELAYEDEXPANSION conjunto que funciona, mas faz a sintaxe ainda mais feia do que o normal. Observe que agora temos uma mistura de variáveis ??referenciados apenas pelo seu nome, prefixando-los com um simples%, prefixando-os com dois%, por envolvê-los em%, ou envolvê-los em!. E essas diferentes formas de referenciar variáveis ??são quase completamente NÃO intercambiáveis!

Além disso, deve ser relativamente fácil de entender!

Answer 2

Aqui está uma versão mais legível que eu escrevi há algum tempo atrás:

@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

Exemplo:

C:\Path> sort 19 zebra blah 1 interesting 21 bleh 14 think 2 ninety figure it out

produz:

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