Advanced Batch File Techniques Part 1 - Bubble Sort

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.

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.