Bubble Sort Challenge

The last time I wrote a BubbleSort was 1993 for my then-husband. He had written an index of all the dead people in Pembina County, North Dakota, (he's into genealogy) and he needed to sort the pile in alphabetical order. So I sat down in front of my Amstrad PCW and wrote a bubble sort in BasicLanguage. Before that, I'm sure I must have written a bubble sort in FortranLanguage in 1978. I posted my PythonLanguage code on the BubbleSort page. It felt so strange to write it in Python, I think because in Python I'm accustomed to iterating without being aware of the index of the current list element, or even the length of the list. Writing the bubble sort, I had to force myself to think about counters and indices. And then it took me a day to notice I had a couple FencePostErrors. That's what I get for forgetting to CodeUnitTestFirst! -- ElizabethWiethoff

You realize, of course, that "this means war", as Daffy Duck was fond of saying: you have implicitly created a new programming challenge! I.e. writing BubbleSort in a natural way in a language more powerful than BasicLanguage/FortranLanguage, where focus on indices and lengths is somewhat unnatural. I hadn't thought about it before, but offhand I would think that MergeSort would be the most natural sort for such languages, given DivideAndConquer over chunks (and not needing to worry about extra allocation -- MergeSort requiring O(n) space), but the challenge would be to take the natural MergeSort and distort it into a natural BubbleSort. Extra credit for distorting QuickSort into Bubblesort. :-)

Sounds like an AbstractionInversion (after all Perl already has array sorting capability).
There are any number of criticisms you could make about it, but that's missing the point that we're just talking about a toy exercise, like EightQueensInManyProgrammingLanguages. Surely you don't think we're talking about using BubbleSort for a serious application?

I'm the kind of algorithm geek such that I implemented the new (a few years old, but not all that well known) RobertSedgewick?/JonBentley improvements to QuickSort as soon as I heard about it. Not because I'm a sorting expert, but because I was so impressed. I'm also the kind of geek that is highly impressed with things like the very impressive MultiplyAndSurrender. :-) It's lovely, in an utterly warped, twisted, deviant way. I admire the creativity involved.

BTW I remember at least 3 times that I tried but couldn't remember how to do BubbleSort; I think this must mean that there's something about BubbleSort that is unnatural, even though (like most things) it's obvious in retrospect once one refreshes one's memory. That's not the same as natural. -- DougMerritt

FYI: Amazon says MasteringAlgorithmsWithPerl presents a "dozen or so sorting algorithms." Thanks to you, Earle, I'm rereading MasteringAlgorithmsWithCee... Now, later, I'm reading MasteringAlgorithmsWithPerl. BubbleSort is covered in the Perl book, but not the C book. -- ElizabethWiethoff

BubbleSort lines of text using PerlLanguage RegularExpression operations, not an array:

 $_ = <<EOF;
 Perl
 Python
 Ruby
 JavaScript
 Java
 Fortran
 C
 C++
 Basic
 Pascal
 Lisp
 EOF

 my ($count, $swaps, $done) = (0, 0, 0);
 until ($done) {
     m|^(.+\n){$count}|g;   # match first '$count' lines in $_
     if (m|\G(.+)\n(.+)|) { # try matching the next pair
         if ($2 lt $1) {             # if they're in the wrong order
             s|\G(.+)\n(.+)|$2\n$1|; # swap 'em round
             $swaps++;
         } else {       # otherwise,
             pos() = 0; # reset the \G boundary for $_
         }
         $count++;
     } else {
         $done = 1 if ($swaps == 0); # done if there were no swaps
         ($count, $swaps) = (0, 0);  # reset for next time around
     }
 }

 print;

The above code (except the here document) is from BeginningPerl, 1st ed. This is the first elementary sort I've seen which does not use an array (or Python "list" or whatever array-like structure the language supports). It doesn't even use indices. Not really. The closest it gets to using indices is pattern matching on a number of lines counted as it goes and fiddling with the \G global match boundary. Curious, indeed! And very Perl-ish. -- ElizabethWiethoff

In a way, this RubyLanguage solution is overkill because it requires a lot of support code to enable the actual sort routine, but the support code is general-purpose and helps with any code that needs to abstract away array element read/write access.

 # Iterates over an array, and provides
 # read/write access to the current and next
 # elements at each step.
 class ArrayStepper
   include Enumerable

   def initialize(array)
     @index = -1
     @array = array
   end

   # Get or set the value at the current position.
   def cur ; @array[@index] ; end
   def cur=(value) ; @array[@index] = value ; end

   # Get or set the value at the next position.
   def prev ; @array[@index-1] ; end
   def prev=(value) ; @array[@index-1] = value ; end

   # Check if the array has items after/before current.
   def has_next? ; @index + 1 < @array.length ; end
   def has_prev? ; @index > 0 ; end

   def swap_with_prev
     self.prev, self.cur = self.cur, self.prev
   end

   def swap(other_step)
     self.cur, other_step.cur = other_step.cur, self.cur
   end

   # Moves to the next position in the array.
   def to_next
     @index += 1
     return self
   end

   # Any methods not responded to by the stepper
   # are passed through to the current element
   # object.
   def method_missing(sym, *args)
     cur.send(sym, *args)
   end
   def respond_to?(sym)
     super || cur.respond_to?(sym)
   end

   # Starts before the first element, and
   # repeatedly moves to the next, passing the
   # stepper to the supplied block.
   # The "each" iterator of a clone of the stepper
   # proceeds from the subsequent item to the end.
   def each
     yield(to_next) while has_next?
   end

 end

 module ArrayStepping

   # Any method call names beginning with
   # stepper_... generate a new stepper, then
   # use the remainder of the method name as a
   # call to the stepper with yield.
   def method_missing(sym, *args)
     ( match = /^stepper_/.match(sym.to_s) ) || 
       ( return super )
     stepper = ArrayStepper.new(self)
     stepper.send(match.post_match.to_sym, *args) {|*a| yield *a }
   end

 end

 class Array
   include ArrayStepping
 end

 def bubble_sort!(array)
   loop do
     ( array.stepper_inject(false) do |again, st|
         next ( st.has_prev? and st.prev > st ?
                     (st.swap_with_prev ; true) :
                     again
              )
       end
     ) || break
   end
   return array
 end

 def selection_sort!(array)
   array.stepper_each do |i|
     i.clone.each do |j|
       i.swap(j) if i > j
     end
   end
   return array
 end

- SteveJorgensen

Obligatory ForthLanguage version:

: Perl s" Perl" ; : Python s" Python" ; : Ruby s" Ruby" ; : JavaScript s" JavaScript" ; : Java s" Java" ; : Fortran s" Fortran" ; : C s" C" ; : C++ s" C++" ; : Basic s" Basic" ; : Pascal s" Pascal" ; : Lisp s" Lisp" ;

create pointers ' Perl , ' Python , ' Ruby , ' JavaScript , ' Java , ' Fortran , ' C , ' C++ , ' Basic , here ' Pascal , ' Lisp ,

constant penultimate

: name @ execute ; resolve a table entry to a name string : swp >r r@ @ r@ cell+ @ swap r@ cell+ ! r> ! ; swap adjacent table entries : pair dup name rot cell+ name ; two adjacent names : arrange dup pair compare 0> if swp exit then drop ; : bubble penultimate begin 2dup u> if 2drop exit then bubbles from end of list towards the beginning. dup arrange [ 1 cells ] literal - again ; : sort pointers begin dup penultimate u> if drop exit then dup bubble cell+ again ;

: e dup name type space cell+ ; : show pointers e e e e e e e e e e e drop cr ; display current table state : demo show sort show ; demo

--SamuelFalvo?

java-like version at ProofAnnotationsForBubbleSort.

CategoryAlgorithm SortingAlgorithms