Bubble sort & Shaker sort

grasping the bytes > Information Visualization > Sort Algorithms Visualizer > Bubble sort - (fr)

menu

Sort Algorithms Visualizer

About sorting

> Sort algorithms

Instructions

Exercises

About the applet (source code).

Usually considered the most inefficient sort algorithm, it happens to be quite suited to some frequently found data distributions, and thus it still used sometimes in professional products, even though this is quite an unsafe practice.

Complexity is O(n*n) both in number of comparisons and number of exchanges. Works well only when the distribution is almost sorted, with no small items at the end of the array.

 class BubbleSort extends AlgoTri {
    BubbleSort (int t, VueTris v) { super("Bubble Sort", t, v); }
 public void sort () {
    boolean moved;
    int curndx=size;
    do {
        moved=false;
        for (int i=1; i < curndx; i++) {
            if (compare(i, i-1)<0) {
                 exchange(i, i-1);
                 moved=true;
            }
        }
        curndx--;
    } while (moved);
 }
};

Shaker sort is a simple optimization that does passes in both directions, allowing out of place items to move fast across the whole array. Same complexity as Bubble sort, only works much better when some smal items are at the end of the array.

class ShakerSort extends AlgoTri {
    ShakerSort (int t, VueTris v) { super("Shaker Sort", t, v); }
 
    public void sort () {
        boolean moved=false;
        int curmax=size, curmin=1;
        do {
           moved=false;
           for (int i=curmin; i < curmax; i++)
                if (compare(i, i-1)<0) {
                    exchange(i, i-1);
                    moved=true;
                }
           curmax--;
           if (!moved) break;
           for (int i=curmax-1; i >= curmin; i--)
                if (compare(i, i-1)<0) {
                     exchange(i, i-1);
                     moved=true;
                }
           curmin++;
         } while (moved);
   }
};