Counting Sort

Counting Sort algorithm based on using keys of a specific range. It works by counting the number of values in given array with a key value and storing it in an array or map by this key.

Lets understand it with example:

arr = [4, 3, 1, 6, 9, 0, 1, 0, 2, 2]

indexes = [0 1 2 3 4 5 6 7 8 9] – key values, indexes of array

counts => [2 2 2 1 1 0 1 0 0 1] – number of elements with index value in array arr.

So you create additional array [2, 2, 2, 1, 1, 0, 1, 0, 0, 1].

Then, you can traverse it and get all elements in sorted order, since array indexes are sorted already.

Counting sort works only for arrays with non-negative integer values. For other cases, you can use dict() or any other ordered data structure.

Time complexity: O(max(N, max(arr)) - to traverse two arrays: first one of size N and second array of size max(arr).

Space complexity: O(max(arr)) - to create additional array.

Uppgift

Swipe to start coding

Implement the countingSort() function. Then call it for the given arrays arr1 and arr2 and output the sorted arrays separately. Do not change the arr1 and arr2.

Lösning

def countingSort(arr):

# Create additional array of size max(arr)+1

counts = [0 for _ in range(max(arr)+1)]

for val in arr: # Forming counts array

counts[val]+=1

ans = [] # Empty array

for key, count in enumerate(counts):

while count>0:

ans.append(key)

count -= 1

return ans

arr1 = [19, 34, 61, 36, 17, 76, 64, 16, 48, 45, 62, 50, 5, 30, 13, 42, 71, 55, 10, 42]

arr2 = [23, 40, 73, 15, 42, 54, 76, 98, 94, 32]

arr1_sorted = countingSort(arr1)

arr2_sorted = countingSort(arr2)

print(arr1_sorted)

print(arr2_sorted)

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 5

def countingSort(arr):

# Create additional array of zeroes of size max(arr)+1

counts = _ _ _

for val in arr: # Forming counts array

counts[val] _ _ _

ans = [] # Empty array

for key, count in enumerate(counts):

# Append value until count>0

_ _ _

return _ _ _

arr1 = [19, 34, 61, 36, 17, 76, 64, 16, 48, 45, 62, 50, 5, 30, 13, 42, 71, 55, 10, 42]

arr2 = [23, 40, 73, 15, 42, 54, 76, 98, 94, 32]

# Call the function for arr1 and arr2

Fråga AI

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal