Sort

Question 1

Counting Sort Algorithm

Answer 1

Counting sort is an integer-based sorting algorithm for sorting an array whose keys lie between a specific range. It counts the total number of elements with each distinct key value and then uses those counts to determine the positions of each key value in the output.

We can use counting sort to find the most frequent letter in a file or sort a limited range array efficiently. It is often used as a subroutine in the radix sorting algorithm, and because of this, counting sort needs to be a stable sort.

Unlike other sorting algorithms like Insertion sort, Selection sort, Merge sort, Quicksort, etc., Counting sort is not a comparison sort. It uses key values as indices into an array.

Question 2

Implementing Counting Sort Algorithm

Given a collection of n items, each of which has a non-negative integer key whose maximum value is at most k, effectively sort it using the counting sort algorithm.

Answer 2

The algorithm loops over the items, computing a histogram of each key’s number of times within the input collection. It then performs a prefix sum computation to determine, for each key, the starting position in the output array of the items having that key. Finally, it loops over the items again, moving each item into its sorted position in the output array.

After the first for-loop, freq[i] stores the total number of items with a key equal to i.
After the second for-loop, it instead stores the total number of items with a key less than i, which is the same as the first index at which an item with key i should be stored in the output array.
Throughout the third loop, freq[i] always stores the next position in the output array into which an item with key i should be stored, so each item is moved to its correct position in the output array.

’’
A ——> the input list of integers to be sorted
k ——> a number such that all integers are in range 0…k-1
‘’’
def countsort(A, k):

    # create an integer list of size `k + 1` to store each integer's count
    # in the input list
    freq = [0] * (k + 1)

# using the value of each item in the input list as an index,
# store each integer's count in `freq[]`
for i in A:
    freq[i] += 1

    # overwrite the input list with sorted order
    index = 0
    for i in range(k + 1):
        while freq[i] > 0:
            A[index] = i
            index += 1
            freq[i] -= 1

if __name__ == ‘__main__’:

A = [4, 2, 10, 10, 1, 4, 2, 1, 10]

    # range of list elements
    k = 10

countsort(A, k)
print(A)