- Details
- Parent Category: Programming Assignments' Solutions

# We Helped With This Python Programming Homework: Have A Similar One?

Category | Programming |
---|---|

Subject | Python |

Difficulty | Undergraduate |

Status | Solved |

More Info | Python Coding Help |

## Short Assignment Requirements

## Assignment Description

** **

**Counting sort [20 points] **

In this exercise you will implement and experiment with another sorting algorithm, Counting Sort.

**The Counting Sort Algorithm [15
points] **

Counting sort is an algorithm to be used for sorting positive integers. The algorithm is linear, but requires the range of values of the integers to be known, ahead of time. Because the complexity of the algorithm depends not only on the number of integers to be sorted, but also on their range, it should only be used if the range of the integers is no more than their number. In this assignment, you will implement counting sort for a list of positive integers and verify by experiment that it is a linear-time algorithm.

The basic idea of counting sort is to determine, for each integer x in the unsorted list, the number of integers that are less than x. This information is then used to place x in the sorted list. For example, if there are 17 integers in the unsorted list that are less than x, then x will be placed in the 18th position of the sorted list. This basic schema assumes that there are no multiple occurrences of the same integer in the unsorted list. It can be easily modified to account for multiple occurrences, as demonstrated by the below defined algorithm.

The algorithm uses the list unsorted for the integers to be sorted, the list result for the sorted integers, and the list counts as a work list to determine, for each integer in the unsorted list, the number of integers that are smaller or equal to the integer. Furthermore, the algorithm uses the integer highest that denotes the highest integer in the unsorted list. Both the lists unsorted and result are of length length, where length denotes the number of integers to be sorted. The work list is of length highest+1, and denotes for each integer occurring in the unsorted list how many integers occurring in the unsorted list are smaller or equal to the integer. For example, for the unsorted list 2, 4, 0, 2, highest is 4 and count will be1, 1, 3, 3, 4,and result will be 0, 2, 2, 4. The list count 1, 1, 3, 3, 4 indicates that there is 1 integer that is less than or equal to 0 (because count[0] is 1), that there is 1 integer that is less than or equal to 1 (because count[1] is 1), that there are 3 integers that are less than or equal to 2 (because count[2] is 3), that there are 3 integers that are less than or equal to 3 (because count[3] is 3), and that there are 4 integers that are less than or equal to 4 (because count[4] is 4).

The algorithm is defined as follows:

(i) For i in [0, highest+1), set counts[i] to 0.

(ii) For each integer in unsorted, increment counts[integer] by 1.

(iii) For i in [1, highest+1), set counts[i] to (counts[i-1] + counts[i]).

(iv) For each integer in unsorted,

a. set result[counts[integer]-1] to integer and 1

b. set counts[integer] to (counts[integer] - 1).

The above algorithm computes the list counts gradually. After step (i), counts is initialized with all zeroes. After step (ii), counts contains for each integer in unsorted the number of times it occurs in unsorted. And finally after step (iii), counts denotes for each integer in unsorted how many integers occurring in unsorted are smaller or equal to the integer. In the final step, the algorithm inserts the integers from unsorted into the appropriate place in result, using the information provided by counts. Note that after each insert of an integer, its corresponding count is decreased by one in counts.

** Task:** Define a Python function
countingSort(unsorted, highest) that implements the above algorithm, i.e., that
takes the unsorted list unsorted and its highest integer value highest as
arguments and returns the sorted list result. You may assume that unsorted is
non-empty and contains positive integers, possibly including 0.

Example Usage:

countingSort([2, 4, 0, 2], 4) should return [0, 2, 2, 4]

countingSort([10,
0, 2, 10, 6, 1], 10) should return [0, 1, 2, 6, 10, 10]

countingSort([5], 5) should return [5]

countingSort(list(range(10)), 9) should return [0, 1, 2, 3, 4,
5, 6, 7, 8, 9]

**Time measuring [5 points] **

Next, we ask you to implement a function to measure the execution time of your function countingSort(), which you implemented in the previous step. In the same fil, define the function time sort(n) that returns the time taken by counting sort. The input n indicates the size of the list to be sorted. Your function should create a list of the integers from 0 to n-1 (list(range(10)) creates this list [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) and call the function countingSort() to sort the list. For the experiment, you do not have to worry that the list is already sorted; the function will work the same way anyway.

How do we measure the time taken? First, before the defintion of function time_sort(), include the following line:

from time import time

Inside the definition of function time_sort(), after creating the list to be sorted, but before calling the function countingSort(), incude the following:

start = time ()

This sets the variable start to the current time. Then, after calling the function countingSort(), return the value time()-start, which amounts to the execution time of countingSort() in seconds.

Test this function by choosing a large enough n so that sorting takes several seconds.

__I found this website on the
internet that visualizes how the process of Counting Sort works. Feel free to
take a look, slow it down where necessary and try to understand how the sorting
works.__

__ __

https://www.cs.usfca.edu/~galles/visualization/CountingSort.html