EECS1015-Lab 9 Min Max List (Importing classes and improving efficiency) Solved

Task 1 – MinMaxList: simple modifications 

(1) Write the code the MinMaxList class in a separate file named "MinMaxList.py."   In PyCharm, this should be in the same project and folder as your main.py code. Note that the code above imports the MinMaxList class. 

(2) Modify the MinMaxList class (--- see Lecture 9--- https://trinket.io/python/19a5baaa92 ) as follows: 

Remove the getMinMax() and replace it with two methods as follows (see code above too that calls these methods): 

getMin() – returns the minimum item from the list, deletes the item from the list. getMax()  - returns the maximum item from the list, deletes the item from the list.  

(3) Add a new method called printList printList() – prints the instance variable storing the list 

 

See next page for Task 2 – Making insert more efficient 

 

 

 

 

 

 

Task 2: Making MinMaxList more efficient by modifying the insertItem() method 

The current implementation of the MinMaxList is to perform a sort() in the constructor and when an item is inserted.   For the constructor, apply sort() reasonable.   

The current implementation of insertItem() is as follows:   def insertItem(self, item):     self.listData.append(item)     self.listData.sort() 

 

For inserting an item into an already sorted list, the current approach is highly inefficient.  The time complexity of a sort() algorithm is O(nlogn) (this means, n * log(n)), which is slower than O(n).   We can modify insertItem() to have a time-complexity of O(n) by searching the list for the correct location to insert the item.  Recall that a list object has a method called "insert(index, item)" to insert an item at a particular index.   

 

You need to make two modification to insertItem().  The first is to remove the sort, the second is to allow the method to printout information regarding how your insertion worked. 

Modification #1 – do not use sort, instead, find the correct location to insert the item 

Pseudo-code for performing the insertion: if the List is empty 

    Append item to end of the List (same as adding item to the list) else if item = last element in the List:     Append item to end of the List 

otherwise 

    Find the appropriate index in the list to    

   insert the new item.  

(a)  Start by setting the index to 0.  

(b)  Add one to the index if the item is larger                  than the current position.    

(c)  Stop when you find an item is smaller than              the element at the current position.    (d) Insert the item at this index to the List. 

                  See diagram on the right à 

 

 

Modification #2 – have insertItem() printout information on your insertion 

insertItem(self, item, printResult=False/True) 

Add an additional parameter to allow a print out of where you inserted the item. Your print out should be as follows: 

Item (86) inserted at location 5                     # print out the item and location you inserted it [1, 2, 10, 11, 34, 86, 88, 99, 99]               # print out the the list after insertion  

Note that the provided code above uses this option. 

        

Sample Output  

If your MinMaxList is implemented correctly, your main.py (provided to you – see above) should work. 

An example output is shown below.  Note that the inserted numbers are randomly generated, so your output will look different. 

--- Insert Item --- 

Item (99) inserted at location 5 

[1, 10, 11, 34, 88, 99, 99] 

Item (2) inserted at location 1 

[1, 2, 10, 11, 34, 88, 99, 99] 

Item (86) inserted at location 5 

[1, 2, 10, 11, 34, 86, 88, 99, 99] 

Item (83) inserted at location 5 

[1, 2, 10, 11, 34, 83, 86, 88, 99, 99] 

Item (39) inserted at location 5 

[1, 2, 10, 11, 34, 39, 83, 86, 88, 99, 99] 

Item (16) inserted at location 4 

[1, 2, 10, 11, 16, 34, 39, 83, 86, 88, 99, 99] 

Item (81) inserted at location 7 

[1, 2, 10, 11, 16, 34, 39, 81, 83, 86, 88, 99, 99] 

Item (98) inserted at location 11 

[1, 2, 10, 11, 16, 34, 39, 81, 83, 86, 88, 98, 99, 99] 

Item (17) inserted at location 5 

[1, 2, 10, 11, 16, 17, 34, 39, 81, 83, 86, 88, 98, 99, 99] 

Item (78) inserted at location 8 

[1, 2, 10, 11, 16, 17, 34, 39, 78, 81, 83, 86, 88, 98, 99, 99] 

Item (97) inserted at location 13 

[1, 2, 10, 11, 16, 17, 34, 39, 78, 81, 83, 86, 88, 97, 98, 99, 99] --- I SKIPPED A FEW INSERTS ---- 

[1, 2, 10, 11, 16, 17, 33, 34, 39, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Item (41) inserted at location 9 

[1, 2, 10, 11, 16, 17, 33, 34, 39, 41, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Item (50) inserted at location 10 

[1, 2, 10, 11, 16, 17, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Item (24) inserted at location 6 

[1, 2, 10, 11, 16, 17, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Item (24) inserted at location 6 

[1, 2, 10, 11, 16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] 

--- Get Min --- 

Min item 1  

[2, 10, 11, 16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 2  

[10, 11, 16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 10  

[11, 16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 11  

[16, 17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 16  

[17, 24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 17  

[24, 24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 24  

[24, 33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 24  

[33, 34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 33  

[34, 39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] Min item 34  

[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99, 99] --- Get Max --- 

Max item 99  

[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98, 99] Max item 99  

[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97, 98] 

Max item 98  

[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95, 97] 

Max item 97  

[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93, 95] 

Max item 95  

[39, 41, 50, 78, 81, 81, 83, 85, 86, 88, 93] 

Max item 93  

[39, 41, 50, 78, 81, 81, 83, 85, 86, 88] 

Max item 88  

[39, 41, 50, 78, 81, 81, 83, 85, 86] 

Max item 86  

[39, 41, 50, 78, 81, 81, 83, 85] 

Max item 85  

[39, 41, 50, 78, 81, 81, 83] 

Max item 83  

[39, 41, 50, 78, 81, 81]