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

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.

Task

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.

Solution

Everything was clear?

How can we improve it?

Thanks for your feedback!

SectionΒ 1. ChapterΒ 5
single

single

Ask AI

expand

Ask AI

ChatGPT

Ask anything or try one of the suggested questions to begin our chat

Suggested prompts:

Summarize this chapter

Explain the code in file

Explain why file doesn't solve the task

close

Awesome!

Completion rate improved to 7.69

bookCounting Sort

Swipe to show menu

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.

Task

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.

Solution

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

close

Awesome!

Completion rate improved to 7.69
SectionΒ 1. ChapterΒ 5
single

single

some-alt