Come posso implementare quicksort usando un file batch?

Question

Mentre di solito è bene scegliere sempre la lingua giusta per il lavoro, a volte può essere istruttivo provare a fare qualcosa in una lingua che è selvaggiamente inappropriata.

1. Può aiutarti a capire meglio il problema. Forse non devi risolverlo come pensavi di aver fatto.
2. Può aiutarti a capire meglio la lingua. Forse supporta più funzionalità di quelle che hai realizzato.

E spingendo questa idea alla sua conclusione illogica ... come implementeresti quicksort in un file batch? È anche possibile?

Answer 1

Si scopre che non è così difficile come potresti pensare. La sintassi è brutta come l'inferno, ma la sintassi batch è in realtà capace di alcune cose sorprendenti, tra cui ricorsione, variabili locali e analisi sorprendentemente sofisticate delle stringhe. Non fraintendetemi, è un linguaggio terribile, ma con mia sorpresa, non è completamente paralizzato. Non credo di aver imparato nulla su quicksort, ma ho imparato molto sui file batch!

In ogni caso, ecco quicksort in un file batch - e spero che ti diverta tanto a cercare di capire la bizzarra sintassi mentre la leggi come ho fatto durante la scrittura. : -)

@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

Chiamalo dandogli una serie di numeri da ordinare sulla riga di comando, separati da spazi. Esempio:

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

Il codice è un po 'difficile da capire. Fondamentalmente è quicksort standard. I bit chiave sono che stiamo memorizzando numeri in una stringa - array di poveri. Il secondo per loop è piuttosto oscuro, fondamentalmente si divide l'array in una testa (il primo elemento) e una coda (tutti gli altri elementi). Haskell lo fa con la notazione x: xs, ma i file batch lo fanno con un ciclo for chiamato con l'opzione / f. Perché? Perché no?

Le chiamate SETLOCAL ed ENDLOCAL ci permettono di fare variabili locali - una specie di. SETLOCAL ci fornisce una copia completa delle variabili originali, ma tutte le modifiche vengono completamente cancellate quando chiamiamo ENDLOCAL, il che significa che non puoi nemmeno comunicare con la funzione chiamante utilizzando i globali. Questo spiega il brutto "ENDLOCAL" imposta return =% ordinato% " sintassi, che in realtà funziona nonostante ciò che la logica indicherebbe. Quando la riga viene eseguita, la variabile ordinata non è stata cancellata perché la riga non è stata ancora eseguita, quindi la variabile return non viene cancellata perché la riga è già stata eseguita. Logico!

Inoltre, in modo divertente, praticamente non puoi usare le variabili all'interno di un ciclo for perché non possono cambiare, il che rimuove la maggior parte del punto di avere un ciclo for. La soluzione alternativa è impostare ENABLEDELAYEDEXPANSION che funzioni, ma rende la sintassi ancora più brutta del normale. Notate che ora abbiamo un mix di variabili a cui fa riferimento solo il loro nome, anteponendole con un singolo%, anteponendole con due%, racchiudendole in% o racchiudendole in!. E questi diversi modi di fare riferimento alle variabili NON sono quasi completamente intercambiabili!

A parte questo, dovrebbe essere relativamente facile da capire!

Answer 2

Ecco una versione più leggibile che ho scritto qualche tempo fa:

@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

Esempio:

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

produce:

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