Comment implémenter quicksort en utilisant un fichier batch?

Question

Normalement, il est bon de toujours choisir la bonne langue pour le travail, mais il peut parfois être instructif d'essayer de faire quelque chose dans un langage qui est vraiment inapproprié.

1. Il peut vous aider à mieux comprendre le problème. Peut-être que vous n'avez pas ont pour le résoudre comme vous le pensiez.
2. Il peut vous aider à mieux comprendre la langue. Peut-être qu'il prend en charge plus de fonctionnalités que vous avez réalisé.

Et en poussant cette idée à sa conclusion illogique ... comment mettriez-vous en œuvre quicksort dans un fichier batch? Est-ce même possible?

Answer 1

Il s'avère que ce n'est pas aussi dur que vous pourriez le penser. La syntaxe est laide, mais la syntaxe par lots est en fait capable de certaines choses surprenantes, y compris la récursivité, les variables locales, et une analyse étonnamment sophistiquée des chaînes. Ne vous méprenez pas, c'est une langue terrible, mais à ma grande surprise, elle n'est pas complètement paralysée. Je ne pense pas avoir appris quoi que ce soit à propos du quicksort, mais j'ai beaucoup appris sur les fichiers batch!

Dans tous les cas, voici le quicksort dans un fichier batch - et j'espère que vous aurez autant de plaisir à essayer de comprendre la syntaxe bizarre tout en la lisant comme je l'ai fait en l'écrivant. :-)

@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 

Appelez-le en lui donnant un ensemble de nombres à trier sur la ligne de commande, séparés par des espaces. Exemple:

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

Le code est un peu difficile à comprendre. C'est en fait un quicksort standard. Les bits clés sont que nous stockons des nombres dans une chaîne - le tableau de l'homme pauvre. La seconde boucle est assez obscure, elle divise le tableau en une tête (le premier élément) et une queue (tous les autres éléments). Haskell le fait avec la notation x: xs, mais les fichiers batch le font avec une boucle for appelée avec le commutateur/f. Pourquoi? Pourquoi pas?

Les appels SETLOCAL et ENDLOCAL permettent de faire des variables locales - en quelque sorte. SETLOCAL nous donne une copie complète des variables d'origine, mais toutes les modifications sont complètement effacées lorsque nous appelons ENDLOCAL, ce qui signifie que vous ne pouvez même pas communiquer avec la fonction appel en utilisant des globales. Ceci explique l'horrible syntaxe "ENDLOCAL & set return =% trié%", qui fonctionne réellement malgré ce que la logique indiquerait. Lorsque la ligne est exécutée, la variable triée n'a pas été effacée car la ligne n'a pas encore été exécutée - ensuite, la variable de retour n'est pas effacée car la ligne a déjà été exécutée. Logique! De plus, vous ne pouvez pas utiliser des variables à l'intérieur d'une boucle for parce qu'elles ne peuvent pas changer, ce qui supprime la plupart du temps d'avoir une boucle for. La solution consiste à définir ENABLEDELAYEDEXPANSION qui fonctionne, mais rend la syntaxe encore plus laide que la normale. Notez que nous avons maintenant un mélange de variables référencées simplement par leur nom, en les préfixant avec un seul%, en les préfixant avec deux%, en les enveloppant dans%, ou en les enveloppant! Et ces différentes façons de référencer les variables ne sont presque PAS interchangeables!

À part cela, il devrait être relativement facile à comprendre!

Answer 2

est ici une version plus lisible que j'ai écrit il y a quelque temps:

@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 

Exemple:

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

produit:

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