Общее количество сравнений для сортировки массива с помощью сортировки вставкой - PullRequest
Новая
       22

Общее количество сравнений для сортировки массива с помощью сортировки вставкой

0 голосов
/ 14 июля 2020

Обратите внимание, что эта программа тестирует от 100 до 5000 целых чисел с приращением 100. Программа работает нормально, но сравнение не дает текущий результат

Я добавил переменную сравнение , но это не дает правильного сравнения. 

import random

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


def insertion_sort(a):
   x = []
   comparisons = 0
   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     
      comparisons = comparisons + 1
      #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
         comparisons = comparisons + 1
         x.append(comparisons)
        #insert item at correct spot
      a[insert_idx]=cur_item
      
   return x, a
from time import time
b0=[] #insertion sort times
n=range(10,51,10)

for length in n:
    a=create_array(length, length)
    t0 = time()
    s,c=insertion_sort(a) #sort with insertion sort  
    print(c)
    t1=time()
    b0.append(t1-t0) #record insertion time

print("\n|INSERTION SORT|\n")

print("_________________________________________________")
print("n\t\trunning time (s)\t\tNo. of comparison") #display number of comparisons on each n intergers in the next column
print("_________________________________________________")
for i,cur_n in enumerate(n):
    print("%d\t\t%f\t\t%d"%(cur_n, b0[i],s[i] ))

Я добавил переменную сравнение , но это дает мне неправильный результат, я думаю.

...