Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Counting Sort | Simple Algorithms
Sorting Algorithms
course content

Conteúdo do Curso

Sorting Algorithms

Sorting Algorithms

1. Simple Algorithms
2. Divide and Conquer Algorithms
3. Problems

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

Tarefa

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.

Switch to desktopMude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixo
Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 1. Capítulo 5
toggle bottom row

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

Tarefa

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.

Switch to desktopMude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixo
Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

Seção 1. Capítulo 5
toggle bottom row

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

Tarefa

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.

Switch to desktopMude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixo
Tudo estava claro?

Como podemos melhorá-lo?

Obrigado pelo seu feedback!

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.

Tarefa

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.

Switch to desktopMude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixo
Seção 1. Capítulo 5
Switch to desktopMude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixo
some-alt