Click here to Skip to main content
Click here to Skip to main content

Advanced Batch File Techniques Part 1 - Bubble Sort

By , 1 Sep 2007
Rate this:
Please Sign up or sign in to vote.
Batch File 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.

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Miszou
Software Developer (Senior)
United States United States
No Biography provided

Comments and Discussions

 
GeneralExtracting values from the pseudo-array PinmemberBen Burnett4-Dec-07 12:52 
GeneralRe: Extracting values from the pseudo-array PinmemberBen Burnett17-Sep-08 9:54 
GeneralNested expansion Pinmemberyjj10-Sep-07 20:43 
GeneralPhilosophy [modified] Pinmemberemilio_grv4-Sep-07 21:15 
Questionbut...why? PinmemberTomaž Štih4-Sep-07 5:21 
AnswerRe: but...why? PinmemberPaulius Maruška4-Sep-07 12:27 
GeneralCould be shorter PinmemberPaulius Maruška2-Sep-07 19:35 
Hello. First of all - it's a nice article, I really like when people demonstrate that Batch files can be awesome too. However, I would like to point out, that your implementation of the sort isn't really perfect. Storing variables in files is a bad idea - best way to have an array or a list, is to have the string, imho.
 
Anyway, here's an alternative sort algorithm I wrote just a couple of minutes ago - I didn't test very well, so it might not work in some special cases, but all of the tests I've done succeeded:
@echo off
call :sort %*
exit /B 0
 
:sort
	set swaps=0
	set sorted=
	if $%1$ == $$ goto :sort_loop_end
	set var1=%1
	shift
	:sort_loop
		if $%1$ == $$ goto :sort_loop_end
		set var2=%var1%
		set var1=%1
		shift
		set varT=%var1%
		if /I %var1% LSS %var2% (
			set var1=%var2%
			set var2=%varT%
			set /A swaps=swaps+1
		)
		set sorted=%sorted% %var2%
		goto sort_loop
	:sort_loop_end
	set sorted=%sorted% %var1%
	if /I %swaps% GTR 0 (
		rem echo %swaps% : %sorted%
		call :sort %sorted%
	) else (
		echo Done: %sorted%
	)
exit /B 0

 
"C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off." --Bjarne Stroustrup

GeneralRe: Could be shorter PinmemberMiszou4-Sep-07 7:24 
GeneralRe: Could be shorter Pinmemberbbman2255-Apr-14 20:30 
GeneralAwesome PinmvpRama Krishna Vavilala2-Sep-07 13:24 
GeneralRe: Awesome PinmemberMiszou2-Sep-07 15:21 
JokeGreat PinmemberMB_OK2-Sep-07 3:55 
GeneralRe: Great Pinmemberwtwhite3-Sep-07 20:27 
JokeRe: Great PinmemberAlex Weatherall10-Sep-07 15:16 
GeneralRe: Great Pinmemberwtwhite10-Sep-07 15:52 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140415.2 | Last Updated 2 Sep 2007
Article Copyright 2007 by Miszou
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid