Sorting Algorithms

Solution Preview

Sorting Algorithms
Introduction
Sorting is central to many tasks carried out on a computer. Sorting efficiency will often impact the overall efficiency of a program significantly. I will attempt to present several algorithms and explain the benefits and pitfalls of each.
It is not always possible to say that one algorithm is better than another, as relative performance can vary depending on the type of data being sorted. In some situations, most of the data are in the correct order, with only a few items needing to be sorted. In other situations the data are completely mixed up in a random order and in others the data will tend to be in reverse order. Different algorithms will perform differently according to the data being sorted. Four common algorithms are the exchange or bubble sort, the selection sort, the insertion sort and the quick sort.
 
Exchange (Bubble) Sort
Element 1 2 3 4 5 6 7 8
Data 27 63 1 72 64 58 14 9
1st pass 27 1 63 64 58 14 9 72
2nd pass 1 27 63 58 14 9 64 72
3rd pass 1 27 58 14 9 63 64 72...
The first two data items (27 and 63) are compared and the smaller one placed on the left hand side. The second and third items (63 and 1) are then compared and the smaller one placed on the left and so on. After all the data has been passed through once, the largest data item (72) will have "bubbled" through to the end of the list. At the end of the second pass, the second largest data item (64) will be in the second last position. For n data items, the process continues for n-1 passes, or until no exchanges are made in a single pass.
Bubble Sort Pseudocode
function bubblesort (A : list[1..n]) {
var int i, j;
for i from n downto 1 {
for j from 1 to i-1 {
if (A[j] > A[j+1])
swap(A[j], A[j+1])
}
}
}

 
Selection Sort
Element 1 2 3 4 5 6 7 8
Data 27 63 1 72 64 58 14 9
1st pass 1 63 27 72 64 58 14 9
2nd pass 1 9 27 72 64 58 14 63
3rd pass 1 9 14 72 64 58 27 63...
The selection sort marks the first element (27). It then goes through the remaining data to find the smallest number (1). It swaps this with the first element and the smallest element is now in its correct position. It then marks the second element (63) and looks through the ...