n this programming exercise you will create an algorithm for solving the following version of the m Smallest Numbers problem and implement it. Instead of just returning the m smallest values as in homework 1, you want to return a list of the positions where the m smallest values are located without changing the original array. Your algorithm should meet the following specifications: mSmallest( L[1..n], m ) Pre: L is a list of distinct integer values. n is the number of elements in the list. 0 < m ≤ n Post: A list [p1, p2, …, pm] has been returned where pj is the position of the jth smallest element of L. The original list L has not been changed. Determine the time complexity of your algorithm.
In this
Your algorithm should meet the following specifications:
mSmallest( L[1..n], m )
Pre: L is a list of distinct integer values. n is the number of elements in the list. 0 < m ≤ n
Post: A list [p1, p2, …, pm] has been returned where pj is the position of the jth smallest element of L. The original list L has not been changed.
Determine the time complexity of your algorithm.
Use Python to implement your algorithm. Your program should:
- prompt the user to enter the list of numbers
- prompt the user to enter the value for m
- print a list of the positions where the m smallest values are located.
You may assume that the elements entered by the user are unique.
In addition, add code to your program to count the number of times the characteristic operation of your algorithm is executed by your program. Compare that number to your determined time complexity.
Code:
n=int(input("Enter number of elements in list: "))
l=[]
index=[]
m=int(input("Enter number of smallest numbers: "))
print("Enter elements: ")
for i in range(n):
# print("enter")
a=int(input())
l=l+[a]
index=index+[i]
zips = zip(l, index)
s = sorted(zips)
sorts = zip(*s)
l, index = [ list(tuple) for tuple in sorts]
print(l[:m])
print("index of smallest numbers are:" ,index[:m])
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
