Question

Based on the source code below, add codes to count how many times array has been access by this program in sorting the array using the insertion sort. Explain how did you count the number of array access on this code. Note that this program tests on 100 until 5000 integers, with increment of 100.

import random

#create randomized array of length 'length' from range 0 up to max
def create_array(length=100, max=5000):
    return [random.randint(0,max) for _ in range(length)]

#executes insertion sort on the input array 'a'
def insertion_sort(a):
   for sort_len in range(1,len(a)):
      cur_item=a[sort_len] #next unsorted item to insert
      insert_idx=sort_len #current index of item

      #iterate down until reach the correct insert spot
      while insert_idx>0 and cur_item<a[insert_idx-1]:
         a[insert_idx]=a[insert_idx-1] #shift elements to make room
         insert_idx+=-1 #decrement the insert spot

        #insert item at correct spot
      a[insert_idx]=cur_item
   return a

#benchmarks the insertion sorting method
from time import time
b0=[] #insertion sort times
n=range(100,5100,100)

for length in n:
    a=create_array(length, length)

    t0 = time()
    s=insertion_sort(a) #sort with insertion sort
    t1=time()
    b0.append(t1-t0) #record insertion time

print("\n|INSERTION SORT|\n")
print("_________________________________________________")
print("n\t\trunning time (s)\t\tNo. of array access") #display number of array access on each n integers in the next column
print("_________________________________________________")
for i,cur_n in enumerate(n):
    print("%d\t\t%f"%(cur_n, b0[i]))

Answer 1

Thanks for A2A.

Below is the changes python code:

import random

#create randomized array of length 'length' from range 0 up to max
def create_array(length=100, max=5000):
    return [random.randint(0,max) for _ in range(length)]

#executes insertion sort on the input array 'a'
def insertion_sort(a):
   count = 0; #to count how many times array is accessed
   for sort_len in range(1,len(a)):
      cur_item=a[sort_len] #next unsorted item to insert
      count += 1 #since above line access the array element
      
      insert_idx=sort_len #current index of item

      #iterate down until reach the correct insert spot

      count += 1 #in while condition cur_item is checked with array element
      #here this count is special one among all other counting in this function
      #as it for while condition false
      while insert_idx>0 and cur_item<a[insert_idx-1]:
         #below count is for while condition true
         count += 1 # since in while cur_item< a[insert_idx-] is true .here alsi accessing a[insert_idx-1]
         
         a[insert_idx]=a[insert_idx-1] #shift elements to make room

         count += 2 # array accessed two times in above line ie, a[insert_idx] ,a[insert_idx-1]
         insert_idx+=-1 #decrement the insert spot

        #insert item at correct spot
      a[insert_idx]=cur_item
      count += 1 # again accessed the array for insert_idx th element in a
   return a,count

#benchmarks the insertion sorting method
from time import time
b0=[] #insertion sort times
arr_access_count = [] #insertion sort array access count
n=range(100,5100,100)

for length in n:
    a=create_array(length, length)

    t0 = time()
    s,count=insertion_sort(a) #sort with insertion sort
    t1=time()
    arr_access_count.append(count)
    b0.append(t1-t0) #record insertion time

print("\n|INSERTION SORT|\n")
print("_________________________________________________")
print("n\t\trunning time (s)\t\tNo. of array access") #display number of array access on each n integers in the next column
print("_________________________________________________")
for i,cur_n in enumerate(n):
    print("%d\t\t%f\t\t\t%d"%(cur_n, b0[i],arr_access_count[i]))

Screenshot of python code:

For better understandablity of special case of couting

consider the a = [1,2,1] and trace the program from sort_len =2.

If you stil have any queries please comment.

Thank you.