QuestionQuestion

Introduction Sorting algorithms rearrange elements in a list in order, so it is much easier to search for something in a sorted list than an unsorted one. In this assignment, we will perform an empirical analysis of sorting algorithms based on Doubling Hypothesis: “What is the effect on the running time of doubling the size of the input?” 1.

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 PreviewSolution 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.

$55.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Python Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats