Consider the following array
34 56 14 20 77 51 93 30 15 52
Insertion sort looks at the first two elements of the array, 34
and 56
14
56
, so the program stores 14
in a temporary variable and moves 56
one element to the right14
is less than 34
, so it moves 34
one element to the right14
in element 0
14 34 56 20 77 51 93 30 15 52
20
in a temporary variable20
to 56
and moves 56
one element to the right because it’s larger than 20
20
to 34
, moving 34
right one element20
to 14
, it observes that 20
is larger than 14
and places 20
in element 1
14 20 34 56 77 51 93 30 15 52
Note: The last two lines of source code in this example have been modified from the print book so you can execute the example inside the notebook.
insertion_sort
¶insert
holds the value of the element that will be inserted into the sorted portion of the arraywhile
loop locates the position where insert
's value should be inserted# insertionsort.py
"""Sorting an array with insertion sort."""
import numpy as np
from ch11utilities import print_pass
def insertion_sort(data):
"""Sort an array using insertion sort."""
# loop over len(data) - 1 elements
for next in range(1, len(data)):
insert = data[next] # value to insert
move_item = next # location to place element
# search for place to put current element
while move_item > 0 and data[move_item - 1] > insert:
# shift element right one slot
data[move_item] = data[move_item - 1]
move_item -= 1
data[move_item] = insert # place inserted element
print_pass(data, next, move_item) # output pass of algorithm
def main():
data = np.array([34, 56, 14, 20, 77, 51, 93, 30, 15, 52])
print(f'Unsorted array: {data}\n')
insertion_sort(data)
print(f'\nSorted array: {data}\n')
# call mainto execute the sort
main()
for
loop iterates len(data) - 1
times, inserting an element into the appropriate position among the elements sorted so farlen(data) - 1
is equivalent to n – 1 (as len(data)
is the size of the array)while
loop iterates over the preceding elements in the array©1992–2020 by Pearson Education, Inc. All Rights Reserved. This content is based on Chapter 5 of the book Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and the Cloud.
DISCLAIMER: The authors and publisher of this book have used their best efforts in preparing the book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The authors and publisher make no warranty of any kind, expressed or implied, with regard to these programs or to the documentation contained in these books. The authors and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.