An insertion sort traverses a list, from the second item to the end of the list.<\/p>\n
On each iteration, the item list[n] is placed into it’s correct position by compared it with each of the earlier items in the list, with values larger than the current\u00a0 being moved up the list, until the correct location is found.\u00a0<\/span><\/p>\n An insertion sort traverses a list, from the second item to the end of the list. On each iteration, the item list[n] is placed into it’s correct position by compared it with each of the earlier items in the list, with values larger than the current\u00a0 being moved up the list, until the correct location is found.\u00a0 General Algorithm FOR i = 1 to length(list)-1 DO SET valueToInsert TO array[i]<\/p>\nGeneral Algorithm<\/h2>\n
FOR i = 1 to length(list)-1 DO\n SET valueToInsert TO array[i]\n SET currentIndex TO i\n \n WHILE (currentIndex> 0) AND (valueToInsert < list[currentIndex-1]) DO\n SET list[currentIndex] TO list[currentIndex-1]\n SET currentIndex TO index - 1\n END WHILE\n \n SET list[currentIndex] TO valueToInsert \nEND FOR<\/pre>\n
\r\n#work through the list from the second item to the last item\r\nfor index in range(1, len(array)):\r\n # get next value to be put into correct place\r\n currentValue = array[index]\r\n currentPosition = index\r\n \r\n #check if not at beginning of list, and previous item is less than value to be placed\r\n while currentPosition > 0 and array[currentPosition - 1] > currentValue:\r\n #move the lower value up a slot\r\n array[currentPosition] = array[currentPosition -1]\r\n #now for the next previous item in the list\r\n currentPosition = currentPosition - 1\r\n \r\n # can put value into correct slot\r\n array[currentPosition] = currentValue\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"