## Question

Rationale In the lecture, we walked through Binary search, Insertion sort, and Merge sort. You will have a closer look at the algorithms by implementing it by yourselves, and discover what difference they yield by measuring the time of execution.

Prerequisites Understanding of classic sorting algorithms and the template files. You will work on the provided files:

• sorter.py contains Sorter class with 4 incomplete instance methods. You will complete those methods to perform the analysis on different sorting algorithms.

• doubling_test.py is a script to perform a doubling test with the Sorter class. You don’t need to make any change to this file.

NOTE All the sorting methods of Sorter take an optional argument reverse – when True is passed, the method sorts a list in descending order, otherwise in ascending order by default. Also the returned sorted list from the sorting methods MUST be List 2 data type. For this assignment, you MUST NOT use any third-party library, package, or module like numpy. (The Python Standard Library 3 is OK.)

Generate A Tuple of Random Integers

(a) Read the docstring of the instance method Sorter.generate_new_tuple(n) in sorter.py

and implement the method.

(b) Run the script doubling_test.py without an argument to self-test if the method is im- plemented properly. The script should then perform a doubling test with “default” sorting method called _default_sort()4 and you should see an output as shown below. You will figure out the meaning of the output by doing Task 2 – nothing to submit for this sub task.

The Sorter Class and Doubling Test

Study the sorter.py and doubling_test.py. In your README.txt, answer the following ques- tions.

(a) Some instance methods of Sorter have the leading ”_” (e.g., _default_sort()) and others don’t (e.g., set_algorithm()). What do you think this convention mean? Explain it by examining doubling_test.py and looking up the PEP 8 Style Guide for Python Code 5.

(b) Sorter._default_sort() has “lst = list(self.unsorted_tuple)” at the beginning of its definition. Why do you think unsorted_tuple is defined as a tuple instead of a list?

(c) Sorter.time_trials() uses “time()”.

(d) In Sorter.time_trials(), explain the following part of the code mentioning n, algorithm, and is_reverse.

Insertion Sort

Implement the instance method Sorter._insertion_sort() with Insertion Sort algorithm.

Bubble Sort

Implement the instance method Sorter._bubble_sort() with Bubble Sort algorithm.

Merge Sort

Implement the method Sorter._merge_sort() with Merge Sort algorithm. As Merge Sort is a recursive algorithm, so you may need to add another helper method/function 6.

6You may write some piece of code outside the indicated block in the template.

Test Doubling Hypothesis

Run the script doubling_test.py with an argument: bubble, insertion, and merge. Observe the results and compare. In your README.txt, put the results up to n: 4096, state the Doubling Hypothesis, and approximate the time increasing factor for each sorting algorithm.

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

class Sorter():"""Sorter implements several algorithms to sort a list.

`unsorted_tuple`: A tuple of random integers to be sorted.

`algorithm`: A string contains name of the algorithm to be used for sorting.

Valid valus are 'bubble', 'default', 'insert', and 'merge'.

Each sorting method make a list copy of `unsorted_tuple` and maintains the original order.

"""

def __init__(self):

"""Sorter constructor.

By default, the `algorithm` is set as 'default' to use the built-in sort()

"""

self.unsorted_tuple = tuple([])

self.algorithm = 'default'

def generate_new_tuple(self, n):

"""Generate a n-length tuple of random integers for `unsorted_tuple`

`n` is an integer indicates the length of the list.

Random integers are in a range from 0 to 9223372036854775807 (sys.maxsize)

The method generate_new_tuple() first generates a new list of `n` length

containing random integers, converts the newly generated list to a tuple,

assigns the tuple to `self.unsorted_tuple`, and returns None.

"""

### Task 1(a) ###

lst = []

for i in range(n):

lst.append(random.randint(0, maxsize))

### Task 1(a) END ###

self.unsorted_tuple = tuple(lst)...

By purchasing this solution you'll be able to access the following files:

Solution.py.