Comment implémenter quicksort à l'aide d'un fichier de commandes?

Question

Bien qu'il soit bon de toujours choisir la bonne langue pour le poste, il peut parfois être instructif d'essayer de faire quelque chose dans une langue extrêmement inappropriée.

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

Et en poussant cette idée à sa conclusion illogique ... comment implémenteriez-vous le tri rapide dans un fichier batch? Est-ce même possible?

Answer 1

Il s’avère que ce n’est pas aussi difficile que vous ne le pensez. La syntaxe est laide, mais la syntaxe batch est capable de choses surprenantes, notamment la récursion, les variables locales et certaines analyses sophistiquées de chaînes. Ne vous méprenez pas, c'est un langage terrible, mais à ma grande surprise, il n'est pas complètement infirme. Je ne pense pas avoir rien appris sur quicksort, mais j'ai beaucoup appris sur les fichiers de traitement par lots!

Dans tous les cas, voici un tri rapide dans un fichier batch - et j'espère que vous aurez autant de plaisir à comprendre la syntaxe bizarre en la lisant qu'à moi-même 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. Il s'agit essentiellement d'un tri rapide standard. Les bits clés sont que nous stockons des nombres dans une chaîne - le tableau du pauvre homme. La seconde boucle for est assez obscure, elle consiste essentiellement à diviser 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 de commandes le font avec une boucle for appelée avec le commutateur / f. Pourquoi? Pourquoi pas?

Les appels SETLOCAL et ENDLOCAL nous permettent de créer 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 appelante à l'aide de globales. C’est la raison pour laquelle le fichier "ENDLOCAL & amp; set return =% trié% " syntaxe, qui fonctionne en dépit de 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 manière amusante, vous ne pouvez pas utiliser de variables dans une boucle for, car elles ne peuvent pas changer - ce qui élimine la plupart du temps d'avoir une boucle for. La solution de contournement consiste à définir ENABLEDELAYEDEXPANSION qui fonctionne, mais rend la syntaxe encore plus laide que la normale. Remarquez 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 2%, 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

Voici une version plus lisible que j'ai écrite 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