Counting Sort | GeeksforGeeks

Counting Sort, well known for its linear time complexity, takes a unique approach to sorting integers by counting the occurrences of each element and then reconstructing the sorted sequence. Join us as we unravel the simplicity and power of Counting Sort.

-------------------------------------------------------------------------

-------------------------------------------------------------------------

📖 Want to Learn more about Data Structures and Algorithms?

-------------------------------------------------------------------------

Follow us for more fun, knowledge, and resources:

Related Queries:
DSA course
Data Structures and Algorithms
DSA Counting Sort
Counting Sort algorithm
Sorting Algorithms
DSA sorting algorithms
working of counting sort algorithm
time complexity of counting sort algorithm
important algorithms for interview

#countingsort #countingsortalgorithm #sortingalgorithm #sorting #algorithms #dsa #datastructuresandalgorithms #gfg #geeksforgeeks

[lfcuhk]

Whoever invented this is an evil genius

[arascan]

the last step is wrong. the algorithm starts to place the numbers in reverse order.(starts with last element 2, not 1) if you start from first index when placing the numbers as you did, you lose stable sort property of counting sort. more precisely, you lose the order of the same numbers.

[tezza]

Imma need to see a proof because that is magic.

[spirridd]

It is unstable version =(
To make it better we have to go from right to left when we fill in the output array.
No need to modify the count array when we don't use this feature properly.
Awesome video by the way!

[FunnyBuns]

You taught me in 5 minutes what my teacher couldnt teach me in 80. superb!

[ashstunes]

Great visualization, just note that this is the unstable version of the algorithm. To make it stable, in the last step, begin placing items in the output array starting from the end of the input array.

[roopkishore]

just cleared it's concept only in 2:18 minutes, really thankful to you

[malharjajoo]

Its imp to note that we need to index into count array using item from original array (this is exactly whats shown in the video) ! Because when countsort becomes part of radixsort, then things change ... Also, if you want stabke sort, then start traversing the original array backwards

[heanz]

Very helpful. I love videos where in 2 minutes everything is said. There are 20min videos out there that have the same information. keep it up

[MCLushy]

Pay attention that on the last step, if you're implementing this with a result array(starts in 0):
you first need to decrement the index-array value and then use it.

[edoardodepiccoli]

for anybody wondering if this keeps the original relative order: it does not. only inserting the elements starting from the last one to the first one the algorithm keeps the relative order and it is considered stable

[joonyou]

The question is, since we're going through the counting array anyways, why not output into an array straightaway?

Here for example
int idx = 0;
for(int i = 0; i < LIMIT; i++) {
‎ while(count[i]--) {
‎ sortedarr[idx] = i;
‎ idx++;
‎ }
}
Can someone explain the point of having to turn it into a sum array to get the indices?

[gpatil]

Easy Explanation : Understanding the algorithm is more important than just following slides and remembering them. Putting here in simple words if someone wants to understand, . I guess its pretty easy to understand that we built the frequency/occurrence array. After that lets understand why need to add the previous count to next one. Lets say in your line for some appointment, you want to know when ( what position ) is your turn, there is 2 ways to know that. If you know your index in line then, all good, there you go. But if someone tells you that dude, there are 3 people before you then you would be like, aaha, since there are 3 before me, I'm fourth. My index will be 4th. Make sure here don't start from 0, but just think like normal life experience.
So in this case here, we keep adding the frequency or count of the other elements, so that how many there are before you and where number stands like their index.
Boom !! There you go, there you built the index for the elements. Happy learning !!

[yunusemrepala]

amazing video to understand it's logic, short and clear...

[MrSilentknight]

You already have all the data you need at 0:42. Why are there more steps?

From this screen you know that the sort is 1122457

[himalay]

The way you implement the last step makes it unstable, you are reversing the order of inserting elements from original array to Places array. The right approach is to shift the index array towards right by one and then put it places array.

[ColdplayIsMyLover]

I was looking for something like that. This is great. Thank you so much. <3

[TheLumbersnack]

Wow this is neat. I saw it in all the sorting algorithms visualized videos and aside the LSD Radix sort, this was one I was most curious about.

[thenewmidiera]

No comparison! Interesting, the subroutine of the fantastic radix sort!

[idogilboa]

amazing!! simple and targeted! nice music to!