Sort a list of integers.... Counting?

Quicksort usually has a running time of n x log(n), but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat n x log(n) (worst-case) running time, since n x log(n) represents the minimum number of comparisons needed to know where to place each element.

Another sorting method, the counting sort, does not require comparison. Instead, you create an integer array whose index range covers the entire range of values in your array to sort. Each time a value occurs in the original array, you increment the counter at that index. At the end, run through your counting array, printing the value of each non-zero valued index that number of times.

Example

arr=[1,1,3,2,1]

i   arr[i]  result

0   1   [0, 1, 0, 0]

1   1   [0, 2, 0, 0]

2   3   [0, 2, 0, 1]

3   2   [0, 2, 1, 1]

4   1   [0, 3, 1, 1]

Note

For this exercise, always return a frequency array with 100 elements. The example above shows only the first 4 elements, the remainder being zeros.

Given a list of integers, count and return the number of times each value appears as an array of integers.

Function Description

Complete the counting_sort function in the editor below.

counting_sort has the following parameter(s):

arr[n]: an array of integers

Returns

int[100]: a frequency array

Constrains

20 <= n < 10>

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'counting_sort' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#


def counting_sort(list_int:list)->list:
    '''
    Sort a list of integers counting the frecuence but not comparating values.

    This function creates a list whose size is used for representing each possible
    value as an index, and each value in the list represents the frequency each value appears.

    Parameters
    ----------
    list_int : list of int
        List of integers values to sort.

    Return
    ------
    frecuency_array: list of int
        List whose each index represents a value in list int and the values
        in frecuency_array represents the frequency of those list_int's values.

    Examples
    --------
    arr=[1,1,3,2,1]
    frecuency_array=[0,3,1,1]

    arr=[0,3,3,2,0]
    frecuency_array=[2,0,1,2]
    '''
    if 20 <= N <= 10**6:  # First constrain
        frecuency_array = []
        for i in range(max(list_int)+1):
            frecuency_array.append(list_int.count(i))
            if len(list_int) > i:
                if list_int[i] < 0>= 100:  # Second constrain
                    raise ValueError('Second constrain violated')
    else:
        raise ValueError('First constrain violated')
    return frecuency_array


if __name__ == '__main__':

    N = 20
    VALUES = '3 19 15 1 2 2 5 25 3 1 1 0 8 19 12 0 1 3 14 19'
    arr = list(map(int, VALUES.rstrip().split()))

    result = counting_sort(arr)
    print(result)

Explanation

1) Taking in account the constraints

I don't know why, but it is pretty common to read solutions where the constraints were ignored, in my case I preferred to use to "if" that check if the constraints are satisfied, otherwise an error message will raise.

First constraint:

if 20 <= N <= 10**6:  # First constrain
    # code
else:
    raise ValueError('First constrain violated')

Second constraint:

if list_int[i] < 0>= 100:  # Second constrain
    raise ValueError('Second constrain violated')

Count method

I create the list "frecuency_array" and add an item for each value between 0 to the max value found in the original list (list_int), each position in the list "frecuency_array" represents the values in "list_int", but the values in "frecuency_array" represents the frecuency of each value in "list_int".

for i in range(max(list_int)+1):
    frecuency_array.append(list_int.count(i))

A step more

Right now we have accomplished the resolution planted in the exercise's statement, but what if we don't need the list with the frequencies instead we need the sorted list? Then, having "result" which is the same "frecuency_array", we can process it like following:

for x in range(len(result))[::-1]:  # Loop inverse on result
    if result[x]:                   # If the value appeard at least once
        for y in range(result[x]):  # Insert the value into the array as
                                    # many times as it has appeared in the original array
            matrix.append(x)
print(matrix)

Being "matrix" the sorted list. Putting the whole code together:

def counting_sort(list_int:list)->list:
    '''
    Sort a list of integers counting the frecuence but not comparating values.

    This function creates a list whose size is used for representing each possible
    value as an index, and each value in the list represents the frequency each value appears.

    Parameters
    ----------
    list_int : list of int
        List of integers values to sort.

    Return
    ------
    frecuency_array: list of int
        List whose each index represents a value in list int and the values
        in frecuency_array represents the frequency of those list_int's values.

    Examples
    --------
    arr=[1,1,3,2,1]
    frecuency_array=[0,3,1,1]

    arr=[0,3,3,2,0]
    frecuency_array=[2,0,1,2]
    '''
    if 20 <= N <= 10**6:  # First constrain
        frecuency_array = []
        for i in range(max(list_int)+1):
            frecuency_array.append(list_int.count(i))
            if len(list_int) > i:
                if list_int[i] < 0>= 100:  # Second constrain
                    raise ValueError('Second constrain violated')
    else:
        raise ValueError('First constrain violated')
    return frecuency_array


if __name__ == '__main__':

    N = 20
    VALUES = '3 19 15 1 2 2 5 25 3 1 1 0 8 19 12 0 1 3 14 19'
    arr = list(map(int, VALUES.rstrip().split()))

    result = counting_sort(arr)
    print('Array of frequencies:')
    print(result)

    matrix=[]
    for x in range(len(result))[::-1]:  # Loop inverse on result
        if result[x]:                   # If the value appeard at least once
            for y in range(result[x]):  # Insert the value into the array as
                                        # many times as it has appeared in the original array
                matrix.append(x)
    print('Sorted List:')
    print(matrix)

Thanks for reading :)
I invite you to continue reading other entries and visiting us again soon.