0.6 Sorting  (Page 8/20)

In pseudocode , this will cause the following change:

procedure bubbleSort( A : list of sortable items ) defined as:

n := length( A )

do

swapped := false

n := n - 1

for each i in 0 to n do:

if A[ i ]>A[ i + 1 ] then

swap( A[ i ], A[ i + 1 ])

swapped := true

end if

end for

while swapped

end procedure

We can then do bubbling passes over increasingly smaller parts of the list. More precisely, instead of doing n2 comparisons (and swaps), we can use only n + (n-1) + (n-2) + ... + 1 comparisons. This sums up to n(n + 1) / 2, which is still O(n2), but which can be considerably faster in practice.

In practice

Although bubble sort is one of the simplest sorting algorithms to understand and implement, its O(n2) complexity means it is far too inefficient for use on lists having more than a few elements. Even among simple O(n2) sorting algorithms, algorithms like insertion sort are usually considerably more efficient.

Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.

The Jargon file , which famously calls bogosort "the archetypical perversely awful algorithm", also calls bubble sort "the generic bad algorithm". Donald Knuth , in his famous The Art of Computer Programming , concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he discusses therein.

Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary. Experimental results such as those of Astrachan have also shown that insertion sort performs considerably better even on random lists. For these reasons many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort.

Bubble sort also interacts poorly with modern CPU hardware. It requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions . Experiments by Astrachan sorting strings in Java show bubble sort to be roughly 5 times slower than insertion sort and 40% slower than selection sort .

6.2. effectively sorting algorithms

6.2.1. shell sort

(From Wikipedia, the free encyclopedia)

Shell sort is a sorting algorithm that is a generalization of insertion sort , with two observations:

• insertion sort is efficient if the input is "almost sorted", and
• insertion sort is typically inefficient because it moves values just one position at a time.

Implementation

The original implementation performs Θ (n2) comparisons and exchanges in the worst case. A minor change given in V. Pratt's book improved the bound to O(n log2 n). This is worse than the optimal comparison sorts , which are O(n log n).