¿Cómo implemento quicksort usando un archivo por lotes?

Question

Si bien normalmente es bueno elegir siempre el idioma adecuado para el trabajo, a veces puede ser instructivo intentar hacer algo en un idioma que es muy inapropiado.

1. Puede ayudarlo a comprender mejor el problema. Tal vez no tenga para resolverlo de la manera que pensó que lo hizo.
2. Puede ayudarlo a comprender mejor el idioma. Tal vez admite más funciones de las que creías.

Y llevando esta idea a su conclusión ilógica ... ¿cómo implementaría la clasificación rápida en un archivo por lotes? ¿Es incluso posible?

Answer 1

Resulta que no es tan difícil como podría pensar. La sintaxis es fea como el infierno, pero la sintaxis por lotes es realmente capaz de algunas cosas sorprendentes, incluidas la recursividad, las variables locales y algunos análisis de cadenas sorprendentemente sofisticados. No me malinterpretes, es un lenguaje terrible, pero para mi sorpresa, no está completamente tullido. No creo que haya aprendido nada sobre Quicksort, ¡pero aprendí mucho sobre archivos por lotes!

En cualquier caso, aquí hay una selección rápida en un archivo por lotes, y espero que se divierta tanto tratando de comprender la extraña sintaxis mientras la leía como lo hice mientras la escribía. :-)

@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

Llámelo dándole un conjunto de números para ordenar en la línea de comando, separados por espacios. Ejemplo:

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

El código es un poco difícil de entender. Básicamente es una clasificación rápida estándar. Los bits clave son que estamos almacenando números en una cadena: la matriz del hombre pobre. El segundo bucle for es bastante oscuro, básicamente divide la matriz en una cabeza (el primer elemento) y una cola (todos los demás elementos). Haskell lo hace con la notación x: xs, pero los archivos por lotes lo hacen con un bucle for llamado con el modificador / f. ¿Por qué? ¿Por qué no?

Las llamadas SETLOCAL y ENDLOCAL nos permiten hacer variables locales, más o menos. SETLOCAL nos da una copia completa de las variables originales, pero todos los cambios se borran por completo cuando llamamos a ENDLOCAL, lo que significa que ni siquiera se puede comunicar con la función de llamada utilizando globales. Esto explica la fea " ENDLOCAL & amp; establecer retorno =% ordenado% " sintaxis, que realmente funciona a pesar de lo que la lógica indicaría. Cuando se ejecuta la línea, la variable ordenada no se ha borrado porque la línea aún no se ha ejecutado; luego, la variable de retorno no se borra porque la línea ya se ha ejecutado. ¡Lógico!

Además, de manera divertida, básicamente no puedes usar variables dentro de un ciclo for porque no pueden cambiar, lo que elimina la mayor parte del punto de tener un ciclo for. La solución es establecer ENABLEDELAYEDEXPANSION que funciona, pero hace que la sintaxis sea aún más fea de lo normal. Tenga en cuenta que ahora tenemos una mezcla de variables a las que se hace referencia solo por su nombre, prefijándolas con un solo%, prefijándolas con dos%, envolviéndolas en% o envolviéndolas en! ¡Y estas diferentes formas de hacer referencia a variables son casi NO intercambiables!

¡Aparte de eso, debería ser relativamente fácil de entender!

Answer 2

Aquí hay una versión más legible que escribí hace un tiempo:

@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

Ejemplo:

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