How do I implement quicksort using a batch file?

Question

While normally it's good to always choose the right language for the job, it can sometimes be instructive to try and do something in a language which is wildly inappropriate.

1. It can help you understand the problem better. Maybe you don't have to solve it the way you thought you did.
2. It can help you understand the language better. Maybe it supports more features than you realized.

And pushing this idea to it's illogical conclusion...how would you implement quicksort in a batch file? Is it even possible?

Answer 1

Turns out, it's not as hard as you might think. The syntax is ugly as hell, but the batch syntax is actually capable of some surprising things, including recursion, local variables, and some surprisingly sophisticated parsing of strings. Don't get me wrong, it's a terrible language, but to my surprise, it isn't completely crippled. I don't think I learnt anything about quicksort, but I learned a lot about batch files!

In any case, here's quicksort in a batch file - and I hope you have as much fun trying to understand the bizarre syntax while reading it as I did while writing it. :-)

@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

Call it by giving it a set of numbers to sort on the command line, seperated by spaces. Example:

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

The code is a bit of a pain to understand. It's basically standard quicksort. Key bits are that we're storing numbers in a string - poor man's array. The second for loop is pretty obscure, it's basically splitting the array into a head (the first element) and a tail (all other elements). Haskell does it with the notation x:xs, but batch files do it with a for loop called with the /f switch. Why? Why not?

The SETLOCAL and ENDLOCAL calls let us do local variables - sort of. SETLOCAL gives us a complete copy of the original variables, but all changes are completely wiped when we call ENDLOCAL, which means you can't even communicate with the calling function using globals. This explains the ugly "ENDLOCAL & set return=%sorted%" syntax, which actually works despite what logic would indicate. When the line is executed the sorted variable hasn't been wiped because the line hasn't been executed yet - then afterwards the return variable isn't wiped because the line has already been executed. Logical!

Also, amusingly, you basically can't use variables inside a for loop because they can't change - which removes most of the point of having a for loop. The workaround is to set ENABLEDELAYEDEXPANSION which works, but makes the syntax even uglier than normal. Notice we now have a mix of variables referenced just by their name, by prefixing them with a single %, by prefixing them with two %, by wrapping them in %, or by wrapping them in !. And these different ways of referencing variables are almost completely NOT interchangeable!

Other than that, it should be relatively easy to understand!

Answer 2

Here's a more legible version that I wrote awhile ago:

@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

Example:

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

produces:

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