Python
Implement a class named BubbleStringList. In this class implement a
method called add, that when given a string, it adds it to an
internal list object.
You can use the list object from the standard python library for
the internal list. Next, implement a sort method that uses a
BubbleSort to sort the list when called.
Create another class called MergeStringList, that implements the
same methods but uses a Merge Sort as the sorting algorithm.
Create another class called QuickStringList that implements the
same methods but used a QuickSort algorithm.
Write a test class for each and use timeit to getting the run times
and compare the results.
Hello,
Please find the below code:
class BubbleStringList: def __init__(self): self.list = [] def add(self, input): self.list.append(input) def sort(self, lst): for i in range(len(lst)): for j in range(i + 1, len(lst)): if lst[j] < lst[i]: lst[j], lst[i] = lst[i], lst[j] return lst class MergeStringList: def __init__(self): self.list = [] def add(self, input): self.list.append(input) def merge(self, left, right): result = [] i, j = 0, 0 while i < len(left) and j < len(right): if len(left[i]) <= len(right[j]): result.append(left[i]) i = i + 1 else: result.append(right[j]) j = j + 1 result += left[i:] result += right[j:] return result def sort(self, nlist): if len(nlist) > 1: mid = len(nlist) // 2 lefthalf = nlist[:mid] righthalf = nlist[mid:] self.sort(lefthalf) self.sort(righthalf) i = j = k = 0 while i < len(lefthalf) and j < len(righthalf): if lefthalf[i] < righthalf[j]: nlist[k] = lefthalf[i] i = i + 1 else: nlist[k] = righthalf[j] j = j + 1 k = k + 1 while i < len(lefthalf): nlist[k] = lefthalf[i] i = i + 1 k = k + 1 while j < len(righthalf): nlist[k] = righthalf[j] j = j + 1 k = k + 1 return nlist class QuickStringList: def __init__(self): self.list = [] def add(self, input): self.list.append(input) def sort(self, array): """Sort the array by using quicksort.""" less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) elif x == pivot: equal.append(x) elif x > pivot: greater.append(x) # Don't forget to return something! return self.sort(less) + equal + self.sort(greater) # Just use the + operator to join lists # Note that you want equal ^^^^^ not pivot else: # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array. return array if __name__ == '__main__': b = BubbleStringList() b.add("Sumit") b.add("Amit") b.add("Kumit") b.add("Pul") b.add("Kul") b.sort(b.list) print(b.list) c =MergeStringList() c.add("Sumit") c.add("Amit") c.add("Kumit") c.add("Pul") c.add("Kul") c.sort(c.list) print(c.list) q = QuickStringList() q.add("Sumit") q.add("Amit") q.add("Kumit") q.add("Pul") q.add("Kul") print(q.sort(q.list))
Test_Quick_Sort.py:
import timeit def test1(array=["Kul","Pul","dul"]): less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) elif x == pivot: equal.append(x) elif x > pivot: greater.append(x) return test1(less) + equal + test1(greater) else: return array if __name__ == '__main__': print(timeit.timeit("test1()", setup="from __main__ import test1"))
Test_Merge_Sort.py:
import timeit def merge(left, right): result = [] i, j = 0, 0 while i < len(left) and j < len(right): if len(left[i]) <= len(right[j]): result.append(left[i]) i = i + 1 else: result.append(right[j]) j = j + 1 result += left[i:] result += right[j:] return result def test1(nlist=["Kul","Pul","dul"]): if len(nlist) > 1: mid = len(nlist) // 2 lefthalf = nlist[:mid] righthalf = nlist[mid:] test1(lefthalf) test1(righthalf) i = j = k = 0 while i < len(lefthalf) and j < len(righthalf): if lefthalf[i] < righthalf[j]: nlist[k] = lefthalf[i] i = i + 1 else: nlist[k] = righthalf[j] j = j + 1 k = k + 1 while i < len(lefthalf): nlist[k] = lefthalf[i] i = i + 1 k = k + 1 while j < len(righthalf): nlist[k] = righthalf[j] j = j + 1 k = k + 1 return nlist if __name__ == '__main__': print(timeit.timeit("test1()", setup="from __main__ import test1"))
Test_bubble_sort.py:
import timeit def test1(lst=["Kul","Pul","dul"]): for i in range(len(lst)): for j in range(i + 1, len(lst)): if lst[j] < lst[i]: lst[j], lst[i] = lst[i], lst[j] return lst if __name__ == '__main__': print(timeit.timeit("test1()", setup="from __main__ import test1"))
Test Cases Using timeit:
Test Case Results:
Let me know if you have anything in comments sections.
Thanks
Python Implement a class named BubbleStringList. In this class implement a method called add, that when...
Objective: Implement a sorting algorithm. Description: Implement a radix sort in a Java class named RadixSort.java. Your program should receive its input from a file named "input.txt", which contains one integer per line. It should produce a sorted output file named "output.txt". Include a main method which demonstrates that your algorithm works.
in python Write a class named RetaiI_Item that holds data about an item in a retail store. The class should store the following data in attributes: • Item Number • Item Description • Units in Inventory • Price Create another class named Cash_Register that can be used with the Retail_Item class. The Cash_Register class should be able to internally keep a list of Retail_Item objects. The class should include the following methods: • A method named purchase_item that accepts a...
Create a Python class named Phonebook with a single attribute called entries. Begin by including a constructor that initializes entries to be an empty dictionary. Next add a method called add_entry that takes a string representing a person’s name and an integer representing the person’s phone number and that adds an entry to the Phonebook object’s dictionary in which the key is the name and the value is the number. For example: >>> book = Phonebook() >>> book.add_entry('Turing', 6173538919) Add...
Write a java class, MaxHeap, to implement a max-heap of values of type double. Use an array and be prepared to grow the array. The array implementation will probably be more efficient. Next, write three java sorting methods: a) One should be the heapsort algorithm. b) the second should sort the array by inserting all the elements from the array into a heap defined by the MaxHeap class, and then removing all the items from the heap and putting them...
WRITING METHODS 1. Implement a method named surface that accepts 3 integer parameters named width, length, and depth. It will return the total surface area (6 sides) of the rectangular box it represents. 2. Implement a method named rightTriangle that accepts 2 double arameters named sideA and hypotenuseB. The method will return the length of the third side. NOTE To test, you should put all of these methods into a ‘MyMethods’ class and then write an application that will instantiate...
Sorting Threads Assignment Overview Write a multithreaded sorting program in Java which uses the merge sort algorithm. The basic steps of merge sort are: 1) divide a collection of items into two lists of equal size, 2) use merge sort to separately sort each of the two lists, and 3) combine the two sorted lists into one sorted list. Of course, if the collection of items is just asingle item then merge sort doesn’t need to perform the three steps,...
Here is the code given for this problem: **And please do this in Python** def mergesort(mlist): if len(mlist)<2: return mlist else: mid=len(mlist)//2 return merge(mergesort(mlist[:mid]),mergesort(mlist[mid:])) Problem 1 (30 points) stable merge sort Consider the following unsorted list of integers containing duplicates where the relative position of each duplicated integer in the unsorted list is noted as a subscript. For example, 1, is at a smaller index than 12. The subscript is ignored when comparing two values since it would not actually...
Instructions C++ programming Your task is to write a class called Data, stored in a file named Data.h. Your class should be able to store a collection (vector) of integers. In addition to the appropriate constructors, your class should also have the following methods. void add (int number); Adds a number to the data set. void print (); Prints out the entire data set on a single line, separated by space. void sort (); Sorts the data set in ascending...
SOLVE IN PYTHON: Exercise #1: Design and implement class Circle to represent a circle object. The class defines the following attributes (variables) and methods: A private variable of type double named radius to represent the radius. Set to 1. Constructor Methods: Python : An overloaded constructor method to create a default circle. C# & Java: Default Constructor with no arguments. C# & Java: Constructor method that creates a circle with user-specified radius. Method getRadius() that returns the radius. Method setRadius()...