Sorting algorithms/Bubble sort: Difference between revisions

The '''bubble sort''' is generally considered to be the simplest sorting algorithm. Because of its simplicity and ease of visualization, it is often taught in introductory computer science courses. Because of its abysmal O(n²) performance, it is never used anywhere else.

The bubble sort works by passing sequentially over a list, comparing each value to the one immediately after it. If the first value is greater than the second, their positions are switched. Over a number of passes, at most equal to the number of elements in the list, all of the values drift into their correct positions. Because each pass finds the maximum item and puts it at the end, the portion of the list to be sorted can be reduced at each pass. (Large values "bubble" rapidly toward the end, pushing others down around them.) A boolean variable is used to track whether any changes have been made in the current pass; when a pass completes without changing anything, the algorithm exits.

Using it to sort an array of a hunderdhundred numbers:

Sorts the 'cnt' cells stored at 'addr' using the test stored in the deferred word 'bubble-test'. Uses forth local variables for clarity.

This version uses the polymorphic <tt>Maybe</tt> type to designate unchanged lists. (The type signature of <tt>_bsort</tt> is now <tt>Ord a => [a] -> Maybe [a]</tt>.) It is slightly faster than the previous one.

Bubble sorting (ascending) an array of any <tt>Comparable</tt> type:

Although the native Ruby sort method for Arrays if much faster (O(n*log(n)) versus O(n**2)), you can find a Ruby version of Bubble sort hereunder. It adds the bubblesort! method to the Array object. Below are two different methods that show four different iterating constructs in ruby.