7 7 - 6.2 Insertion Sort

Sorts an array by sorting each element compared to the elements already sorted to their left.

Psuedocode:

traverse each element starting from index 1 
	traverse sorted elements to find current element position
		shift sorted elements to place current element

Implementation:

for( int i = 1 ; index < array.length; index++)

were starting at 1 because index 0 is considered sorted, as there are no other things to compare it to. this list: sortedlist = [55] is sorted. This list: unsortedlist = [55,1] isnt.

for ( int index = 1 ; index < array.length ; index++ ) {
	int currentIndexValue = array[index];
	int sortedIndex = index - 1;
	while(sortedIndex > -1 
				&& array[sortedIndex] > currentIndexValue) { 
		array[sortedIndex + 1] = array[sortedIndex];
		sortedIndex--;
	}
	array[sortedIndex + 1] = currentIndexValue;
}

grows from the left - left section is growing as it increases in value insertion - > left to right selection - > scattered.

which one should we use and why do we have more than one way to sort? the efficiency of each method depends on how sorted the list is at the start of the sort. The approach impacts which types of list are best for each sort. array1 = {0,1,2,4,3} array2 = {4,3,2,1,0}

array1 insertion sort would have a lower execution count because the while loop wouldnt execute. if it is almost sorted perfectly it wont execute for most of the traversal

alternatively when the array is completely reversed selection sort is more efficient. insertion sort has to shift every single value for every single change, while selection sort only switches two values each change.

statement execution counts can be used to determine efficiency of sorting algorithms.