Thomas W. Christopher

Consulting in High Performance Computing. Training in Concurrency, Networking, and Parallelism, especially in Python and Java.

Sorting Algorithms

Abstract

The beginning of a tutorial on sorting algorithms, this page animates bubble sort and insertion sort. The others are Shell sort, quick sort, heap sort, and bitonic sort.

Author
Thomas W. Christopher

In these sorting algorithms, each element in the array is represented by a dot. The value of the element is represented by its height. It's position is the array is represented by its distance from the left.

In the code fragments:

1. The actual array is hidden. It is examined and manipulated by method calls.
2. Method call get(i) returns the value of the ith element in the array.
3. Method call exchgange(i,j) exchanges the values of the ith and jth elements.
4. The hidden array uses zero-origin addressing.

Bubble and Insertion sorts

Bubble Sort Bubble Sort Bubble Sort works by repeatedly scanning through the array exchanging elements that are out of order. Watching this work, you will see that the sorted array grows right to left. Each sweep picks up the largest remaining element and moves to the right as far as it can go. It is therefore not necessary to scan through the entire array each sweep, but only to the beginning of the sorted portion.

We define the number of inversions as the number of elements that are out of order. They needn't be adjacent. If element 7 is greater than element 16, that's an inversion.

There can be at most N*(N-1)/2 inversions in the array. The maximum number of inversions occurs when the array is sorted in reverse order and has no equal elements.

Each exchange in Bubble Sort removes precisely one inversion; therefore, Bubble Sort   requires O(N²) exchanges.

Here's the code:

    int i,j;
    for (j=N-1;j>0;j--) {
        for (i=0;i<j;i++) {
            if(get(i)>get(i+1))exchange(i,i+1);
        }
    }

Insertion Sort Insertion Sort In insertion sort, we build a sorted list from the bottom of the array. We repeatedly insert the next element into the sorted part of the array by sliding it down (via exchanges) to its proper position.

In the worst case, this will require as many exchanges as Bubble Sort, since only one inversion is removed per exchange. So Insertion Sort  also requires O(N²) exchanges. However, the average distance an element must move for random input is one-half the length of the sorted portion, so Insertion Sort should, in practice, be twice as fast as Bubble Sort. (For those pedants who think terms like "twice as fast" are meaningless, here is how the expression is being used: "x-times as fast" means it runs in 1/x the time.)

Here's the code. We use method setColor to temporarily color the element we are inserting.

    int i,j;
    for (j=1;j<N;j++) {
        setColor(j,Color.red);
        for (i=j;i>0 && get(i)<get(i-1);i--) {
            exchange(i,i-1);
        }
        setColor(i,Color.blue);
    }

On to Shell Sorts

These AdSense ads may be a little inappropriate for an academic page, but they may help pay the costs of maintaining the website.