Need help writing a bubble sort with no loops

[Paul McKenzie]

As to the psuedo-code -- a bubble sort can be checked for termination by simply setting a boolean and checking if any swaps occurred. If that boolean suggests that no swaps occurred, then you know the list is sorted and its time to quit. If you've reached the end of the list, and the boolean suggests that you made a swap somewhere, then you know you have to go back to the start of the list and go through the list again.

You know that you can't use loops, so the first thing is to write a function that will call itself up until it reaches the end of the list. So to this function, you must pass a variable that denotes the number of items in the list, the current item you're looking at now, and of course, the array itself, and the boolean that tests if you need to keep sorting. You set this boolean to "I am sorted", and then call the swapper recursive function from the first item (item 0).

Then you do some checks in this "swapper" function:

1) If you are at the last item, determine whether you need to start the swapper from item 0 again (check the boolean for "I am not sorted"), or quit swapper because you know that nothing was swapped and you've sorted the list successfully (check the boolean to see if "I am sorted"). If you need to go back to the beginning, then you also need to set the boolean to "I am sorted".

2) If you are not at the last item , determine if you need to swap the item and the one next to it. If so, set the boolean to "I am not sorted", swap the items, and then call the "swapper" recursion with the next item number.

See, no loops -- all I do is call this "swapper" and I return from everything when that boolean determines nothing was swapped, and I went through the entire list.

Now is this right? I don't know for sure -- maybe I missed something. The point is I can go through it by hand, draw it up on paper, and see if it does what I expect it to do by trying a small number of items. Once I make the corrections to the above, then and only then do I consider how to write this using C++.

At least I have some sort of blueprint in front of me that seems to do the job in terms of psuedo-code. Again, the trick is to draw this up on paper without loops.

Regards,

Paul McKenzie