Introduction
This is an implementation of a bubble-sort, using only Windows batch files. It can be used to sort a list of items specified on the command line.
Abstract
The problem of sorting a list of command-line items was originally specified by Rama, in a lounge thread entitled Friday Programming Quiz. He was actually looking for a solution using LINQ, but I decided to try doing it using nothing but Windows batch programming.
In this article, I will present a technique for writing a batch file to perform a bubble sort on an arbitrary number of parameters. For example, given the following input:
67 89 12 1 8 1 3 5 7
the program should produce the output shown below:
1
1
3
5
7
8
12
67
89
Using the code
Batch files can be rather difficult to read and understand, especially if you are unfamiliar with some of the more esoteric Windows commands and flags required to get the job done. I will explain each section in detail and then provide the complete listing at the end of the article.
Also note that I have used the C++ style double-slash comments for the code fragments. This is because batch file comments consist of either the REM
statement or a double colon at the start of a line. Batch files do not support lines with comments after them, but I wanted to annotate each line. I have used this syntax simply to illustrate the important points. Please do not try to run any code with a //
comment in it!
Initialization
The first thing to do is to initialize a counter and turn off the echoing of commands. Leaving echo on
is a useful debugging tool, but it also produces screens full of output, which we don't want. The counter will be used to uniquely name the items as they are loaded.
@echo off
set count=1
Loading the Variables
Now we need to load the arguments into variables so we can sort them. Unfortunately, we do not have the luxury of data structures such as arrays or lists. Furthermore, while we can create variables as needed, we cannot read the value back, due to the way the variable expansion is performed. In other words, the following code will NOT work, because the variable var
will not be expanded correctly. This makes it possible to "create" environment variables, but we are unable to read the value back, since we do not truly know it's name.
set count=1
set var%count%=%1 // create a variable called 'var1'
set var // We can see the variable...
echo %var%count%% // ...but we can't access the value!
What we're really trying to create here is a pseudo-array, where the variables themselves contain the index. i.e.: var1=67, var2=89
etc. This would mean that we can create the variable names on-the-fly, by virtue of concatenation and expansion: var%count%=%1
. However, in order for this to work, we need to surround the "entire" variable in %
symbols to indicate that the variable should be expanded,(%var%count%%
) and this is where it falls apart, because we cannot expand the inner variable.
Instead, we use the file system to store our variables for us. It's a little more convoluted and a lot slower, but it works just fine. The code fragment below shows how each command-line argument is stored in a small, sequentially numbered text file.
:loadLoop // Start of our loop
echo %1 > _%count%.var // Copy the arguments into a file
// called _1.var, _2.var etc.
set /a count=count+1 // Increase the counter
shift // shift the arguments
if "%1" == "" goto :startSort // If we are out of arguments,
// continue to the next phase
goto loadLoop // Back to the top, and process
// the next argument
The /a
flag specified in the set
command indicates that the string to the right of the equals sign is a numerical expression and should be evaluated. This allows us to perform arithmetic operations - in this case incrementing the value of a variable. The shift
command will rotate all the command line arguments one place to the left, so that %2
becomes %1
and %1
slides off the end and disappears forever. By using shift
in this manner, we can process any number of arguments in a loop by always referring to %1
.
Finally, the if
statement simply checks to see if there are any more arguments to process. If the value of %1
is an empty string, we have loaded all the arguments into known "variables", and we can then goto
the start of the sort routine.
Sorting the input
Now that we've loaded the arguments, and they are in known variable names that we can readily access, it is time to sort them. In this version of the bubble sort algorithm, the sort is restarted whenever a swap is detected, rather than scanning and swapping multiple items in a single pass. This will hamper performance, but is easier to implement than a full scanning bubble sort. Besides, since we are using batch files to accomplish this, performance is not really at the top of our list of desired features...
The following code simply loops through our "array" of known elements, starting at 0
, up to %total%
. Each item is compared with the following array element by calling the subroutine :swap
, which will be explained in the next section. The %next%
variable is calculated from the current item index, stored in %count%
, by simply adding one to it, again using the /a
flag of the set
command.
If the variable %swapped%
is true
, then we know that the elements were exchanged, and we jump to :RestartSort
to rescan the array from the beginning. If the index of the current item (%count%
) is equal to the total number of elements, and we haven't swapped anything in this pass, we know that all the elements are sorted, so we can goto :output
to display them.
:startSort // Set our upper "array bound"
set /a total=count-1
:RestartSort // Restart the sort from the beginning
set /a count=1
:sortLoop
set /a next=%count%+1 // Swap n and n+1
call :swap %count% %next%
set /a count=count+1
if "%swapped%" == "true" goto :RestartSort // If the variables were swapped,
// start again
if "%count%" == "%total%" goto :output // If we're done,
// output the results
goto :sortLoop // Back to the start to
// swap the next two
Swapping the Elements
Bubble sort works by swapping elements that are out of order. In our implementation we can trivially swap the order of two elements by simply renaming the files that the elements are stored in! The code below shows the :swap
subroutine that tests for less-than-or-equal and swaps the elements accordingly.
The first problem though, is how to read our element values out of the files they are stored in, and into an environment variable that we can use to make the comparison. The trick is to use the set
command with the /P
flag and some basic file redirection. set /P
will set the variable to a line of input entered by the user. We can utilize this feature by redirecting the file containing the element into the set
command, thereby setting the variable to the contents of the file.
:swap
set /P var1="" < _%1.var // Get the first element
set /P var2="" < _%2.var // Get the second element
if /I %var1% LEQ %var2% goto noSwap // Compare and swap if necessary
ren _%1.var _temp.var // Simply rename the files to swap
// the positions
ren _%2.var _%1.var
ren _temp.var _%2.var
set swapped=true // Let the caller know that
// we swapped the elements
goto :eof // return
:noSwap
set swapped= // No swap occurred, so clear the
// "swapped" flag
goto :eof // and return
Once we have loaded two elements into some variables, we can employ an extension to the if
command, the /I
flag, which causes a case insensitive string comparison between the two values. Interestingly, if the values are numeric, then a numeric comparison is performed instead of a string compare, which means that this batch script can sort lists of numbers just as easily as strings, with no modification whatsoever.
The available comparison operators for the string compare are shown below, but for our sort we only need LEQ
, less-than-or-equal. We could also have used GEQ
, greater-than-or-equal, and our sort would sort in the opposite direction. Implementing a batch sort that can accept a flag indicating whether an ascending or descending sort should be performed is left as an exercise for the reader.
EQU | equal |
NEQ | not equal |
LSS | less than |
LEQ | less than or equal |
GTR | greater than |
GEQ | greater than or equal |
Displaying the Sorted Items
Once our list is sorted, we need to be able to output the results. For this task, we use a for
loop with the /L
flag, which causes the command to generate a set of numbers with a specific start, increment and end point. These numbers are actually indices into our now sorted array. For each element in the set, we call the :showval
routine to display the contents of the file with the given index number.
Once the loop is complete, we clean up any leftover files and free up the environment variables by setting them to nothing.
:output
for /L %%i in (0,1,%total%) do call :showval %%i
:cleanup
erase *.var
set next=
set offset=
set total=
set count=
set var=
set var1=
set var2=
goto :eof
:showval // %1 is the first parameter in the subroutine, NOT the batch file
type _%1.var // type the file to the screen
goto :eof
The Completed Program - BatchSort.bat
The completed program is shown below. To use it, simply copy and paste the code into a new text file, with a .bat extension, such as BatchSort.bat and run it. Windows Notepad is an excellent editor for creating batch files.
@echo off
set /a count=0
:loop
echo %1 > _%count%.var
set /a count=count+1
shift
if "%1" == "" goto :startSort
goto loop
:startSort
set /a total=%count%-1
:RestartSort
set /a count=0
:sortLoop
set /a next=%count%+1
call :swap %count% %next%
set /a count=count+1
if "%swapped%" == "true" goto :RestartSort
if "%count%" == "%total%" goto :output
goto :sortLoop
:swap
set /P var1="" < _%1.var
set /P var2="" < _%2.var
if /I %var1% LEQ %var2% goto noSwap
ren _%1.var _temp.var
ren _%2.var _%1.var
ren _temp.var _%2.var
set swapped=true
goto :eof
:noSwap
set swapped=
goto :eof
:output
for /L %%i in (0,1,%total%) do call :showval %%i
:cleanup
erase *.var
set next=
set offset=
set total=
set count=
set var=
set var1=
set var2=
goto :eof
:showval
type _%1.var
goto :eof
Summary
Hopefully, this article has provided some insight into the power of batch file programming. It is not always necessary to fire up a complex IDE to create software. Sometimes the tools we need are right at our fingertips.
For more information on Windows batch commands, see the documentation on Microsoft's web site. There are also plenty of resources that can be found using Google.