Sorting Notes

Topics

 Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort

Bubble Sort

 On each pass, the largest item 'bubbles' up to the begining (or end) of the list. On each pass, each pair is compared, and swapped if they're out of order. Algorithm terminates after n passes of the list (or early if no swaps are made on a certain pass). 
for( i=0; i<n-1; i++) 
   for( j=i+1; j<n; j++) 
      if( A[i] > A[j] ) swap( i, j );

0  7  4  3  8  9  1  2  6  5
0  1  7  4  8  9  3  2  6  5
0  1  2  7  8  9  4  3  6  5
0  1  2  3  8  9  7  4  6  5
0  1  2  3  4  9  8  7  6  5
0  1  2  3  4  5  9  8  7  6
0  1  2  3  4  5  6  9  8  7
0  1  2  3  4  5  6  7  9  8
0  1  2  3  4  5  6  7  8  9

Selection Sort

 On each pass, the smallest item is 'selected', and moved to the ith position in the list. ie. on the first pass, the smallest item is located and moved to the first position. Next pass, the second-smallest is located, and moved into the second position. 
for( i=0; i<n; i++) {
  smallest = i+1;
  for( j=i+1; j<n; j++) {
    if( A[j] < A[smallest] ) smallest = j;
  }
  swap( i, smallest );
}

7 4 3 1 8 9 0 2 6 5
0 4 3 1 8 9 7 2 6 5
0 1 3 4 8 9 7 2 6 5
0 1 2 4 8 9 7 3 6 5
0 1 2 3 8 9 7 4 6 5
0 1 2 3 4 9 7 8 6 5
0 1 2 3 4 5 7 8 6 9
0 1 2 3 4 5 6 8 7 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

Insertion Sort

 Conceptually, the list is divided in half. The first half is considered sorted. Items are pulled from the first list, and 'insert'ed into the sorted list. The insertion algorithm can affect the complexity of this sort. 
for( i=1; i<n; i++) {
   index = find( A[i], i );
   // shift all elements from index over one
   // move A[i] into A[index];
}

7 4 3 1 8 9 0 2 6 5 (index = 0 )
4 7 3 1 8 9 0 2 6 5 (index = 0 )
3 4 7 1 8 9 0 2 6 5 (index = 0 )
1 3 4 7 8 9 0 2 6 5 (idnex = 4)
1 3 4 7 8 9 0 2 6 5 *1
1 3 4 7 8 9 0 2 6 5 *2
0 1 3 4 7 8 9 2 6 5 (index = 2 )
0 1 2 3 4 7 8 9 6 5
0 1 2 3 4 6 7 8 9 5
0 1 2 3 4 5 6 7 8 9
A few notes on implementations. There a few a few different searching methods to find where to insert the new item. Since the first half of the list is known to be sorted, we can use a binary search. Unfortunately, this requires the elements to be in an array, and shifting items over can more than make up for the effecient search. Another implementation is using a linked list. Insertions in a linked list are really easy to do (at most 2 or 3 'next' pointers to change).
A few other notes. Look at lines *1 and *2. Line 1 is done for 'free'. The list doesn't need to be updated. Line 2, all the items need to be shifted over by 1 position. This is where linked list implementation pays off.

Merge Sort

 A divide-and-conquer algorithm. Initially, the list is divided into n/2 lists of size 2. They are sorted. Next The n/2 lists are merged into n/4 lists of size 4. This process continues until one list of size n is obtained. The merge works by taking the smaller of the two lists until one is exhausted. 
7 4 3 1 8 9 0 2 6 5
4 7 1 3 8 9 0 2 5 6
1 3 4 7 0 2 8 9 5 6
0 1 2 3 4 7 8 9 5 6
0 1 2 3 4 5 6 7 8 9

Quick Sort

 Another divide-and-conquer algorithm. The first element is picked as a 'pivot'. A search begins from the left, looking for an item larger than the pivot. Another search from the right looks for an item smaller than the pivot. These two items are swapped. If the searches cross over, the pivot is moved into the cross-over location, and the list is divided in two (not necessarily equal) parts, and the algorithm processes them in turn. 
example to come

Graphical race

See a comparison of some of the sorting algorithms run at the same time: Comparison of Bubblesort, Bi-directional Bubblesort, and QuickSort
This page and contents maintained by Erik Huizing