Analyzing Algorithms
We start our journey into the world of complexity by analyzing the insertion sort algorithm.
We'll cover the following...
Insertion Sort Analysis
Let's start with the example of an array that contains 5 elements sorted in the worst possible order, i.e. descending when we want to sort the array in an ascending order. We'll use the insertion sort algorithm as the guinea pig for our analysis.
We'll not delve into explaining the algorithm itself as our focus is on analyzing algorithm performance. The coursework assumes that readers have an understanding of the fundamental algorithms used in everyday computing tasks, or they can do a quick web-search to get up to speed on the algorithm under discussion. Let's proceed with the implementation of the algorithm first:
class Demonstration {static void insertionSort(int[] input) {for (int i = 0; i < input.length; i++) {int key = input[i];int j = i - 1;while (j >= 0 && input[j] > key) {if(input[j] > key){int tmp = input[j];input[j] = key;input[j + 1] = tmp;j--;}}}}static void printArray(int[] input) {System.out.println();for (int i = 0; i < input.length; i++)System.out.print(" " + input[i] + " ");System.out.println();}public static void main( String args[] ) {int[] input = new int[] {7, 6, 5, 4, 3, 2, 1};insertionSort(input);printArray(input);}}
Below, we extract out the meat of the algorithm.
1. for (int i = 0; i < input.length; i++) {
2. int key = input[i];
3. j = i -