7.12 Counting Sort (Analysis and Code) | Easiest Explanation | Data Structure Tutorials

this sorting algorithm fine see first of all we have discussed many sorting algorithms all those sorting algorithms are comparison sort buying bubble selection MERS quick heap all all are comparison source we are going to compare the when u is given and after comparing the values either we are going to swap the values or we are not going to swap the values fine but this sorting algorithm is not a comparison sort we are not going to compare the values then how we are going to sort C we are going to sort the values according to the according to the keys the key value given fine or you can say the main fun time this sorting algorithm is you are going to count see as the names are just counting so you are going to count the number of elements having having distinct key values find out you can say different key values now what is this key value how we are going to count the number of elements how we are going to sort we are going to see this with the help of an example so say let us suppose you are given this a fine and you are going to sort this any C although you can you can apply that any comparisons over so quick sort and the time complexity for that the best fam complexity would be n log n you cannot get better than n log n but how we can sort in linear time you can say order of n time is it possible sometimes it is possible say sometimes we are going to see the time complexity of this counting sort and how we are going to sort this so see here in this array 0 is 1 2 3 4 4 times 1 is also repeated 2 is also repeated I guess 5 is also repeated something like this so here total number of elements are 17 fine and all the elements are in the range of C from 0 to 0-2 C minimum element is 0 maximum element find out the maximum element in Cerie maximum element is I guess seven so ranges from zero to seven fine so you can say here K value is seven so here you can say we have an array having K different elements right and maybe in this array values can be duplicate values can be there so how to solve this array so here the situation is first cases first cases suppose the array name is a all the elements in the array would be in the range of 0 to K fine our second case may be this elements belongs to any integer may be 0 negative or positive very large integers are very small integer something like this with K different venues fine so we are going to check this case so here for this case we are going to apply another sorting algorithm because here values can be negative so this counting sort we will discuss that will not work on the negative values fine so condition is here the array should contain no negative values and the values should be in the range of 0 to K somewhere in in sum and numericals you are given the scale value in the question only but somewhere it is not given so you can find out K value just you just you check out the maximum element in this maximum element is 7 fine so K value would be 7 right and the range would be from 0 to K so first of all we'll discuss this case the range would be from 0 to K with the help of an example then we are also going to see some another variants of this counting sort ok so let us take this example this is the array the name of there is a total number of elements in this array is 17 indexes from 0 to 16 fine and K value is what the range you can you can check out the minimum is a 0 the maximum element is 9 fine so ranges from 0 to 9 or you can say the K value is 9 fine now the first step is what we are going to count CI I have told you accounting the elements having the string key values key is key value means this this to this is the key value 1 this is the key value find how many times this 2 is there in this area you are going to count that thing one two three four fine how many times one is there in this area one two and three three times like this we are going to count the elements fine and after counting obviously you are going to store those elements in somewhere so for storing that count we are going to take another array and I'm going to take the name of the area's count right now the size of this count array would be this K plus 1 so 9 is there C ranges from 0 to 9 so 10 elements would be there ranger this the size would be K plus 1 or you can say range plus 1 so let us suppose this head is there another array so index would be from 0 to 9 same as the range of this array given any now we are going to count the frequency or counting the elements having distinct key values C so C what should be there in this count array the key values to this 2 is how many times 1 2 3 4 so here we should have 4 C 1 the key value is 1 1 is how many times 1 2 & 3 so here 1 is there and this is how many times three times and next 0 0 is how many times 1 2 3 3 like this you you you are going to fill this array but now we will see how we are going to fill this array actually how you are going to write down 4 here how we are going to count the number of elements fine how you are going to write down the code see first of all we are going to take one variable I find here the value is 2 right so the value is 2 in this in this count array go to the index 2 this is the index 2 and at starting the value in this count array would be 0 you are going to initialize this count array would be 0 all the values right fine now see this to go to the index 2 and increment this value now it becomes 1 we are going to add 1 now I would be at this place you are going to increment this I now here value is 1 now go to this index 1 and increment this value this is now one now again increment I value is 1 again go to the index 1 and increment this value we have 1 so after incrementing the value becomes 2 now next is 0 go to the 0th index increment this value 1 now next is to go to the index to increment this value that is 2 next is 5 go to the index 5 increment this value next is 4 go to the fourth and X increment this value next is 0 between 0 and X and increment this value 2 next is to fine go to index 2 and increment this value that is 3 next is 8 values eight right so go to the index 8 increment this value next is 7 index 7 increment this value next is also 7 go to index 7 increment this value again next is 9 go to index 9 increment this value next is to go to index to increment this value that is 4 next is 0 go to this 0th index increment this value 1 go to index 1 increment this value then last is 9 go to the index 9 increment this well fine this is how we are going to fill this counter you can check out this 9 is how many times 1 & 2 this 8 is how many times only fine how we are going to write down the code for this see we are going to take one for loop we are going to take one variable I I would be started from zero and I would move till here less than an or you can say less than equal to n minus 1 n is 17 and I plus plus now have to fill this count array you are going to write down code for that you are going to increment this value count array value fine see first of all what you have done you have just check this value that is 2 and you have gone to the index 2 and then increment this way fine so how we are going to access this value array name is a and I this is how we are going to access the value of an array I hope you know fine now you find two now you go to this index index 2 and name is count fine index is same not two and two so here you will write count because this the value of this AO Phi is just an index of this a so count brackets a and and now we will do plus plus so here you can write plus plus or head you can write plus plus post increment or pre increment in this case both will be C this is what you have done it starting only when you are going to take this array you are going to initialize this array with zeros for I is equal to 0 I less than equal to K K and count of I is equal to 0 so now next step is now you have you have counted the elements the frequency of the elements fine but now you are supposed to find out the actual position of these elements in the sorted array see after sorting the array would be something like this see after sorting after sorting area would be something like this fine this is unsorted array this is sorted array right so this is 0 would be from 0 to 2 the index would be from 0 to 2 fine first 3 position 4 0 then position 4 1 is 3 4 5 these position 3 to 5 position for this 2 is 6 7 8 9 from index 6 to 9 this is 10 11 12 13 14 15 and 16 for ninth the position would be 15 and 16 now how you will come to know that the position of one is from 3 to 4 from index 3 to 4 how will you have you will come to know that the position for this 7 is because here from here you can say that 7 are 2 times in this area but what is the position in this sorted array at index 2 ln 13 so now we are going to update this count array fine such that this this count array contains the actual position of the elements fine see how we are going to do that we are going to update this array I am going to update this count array this is same count array we are going to update in the same L fine see first first value would be as it is the value at index 0 that would be as a piece we are going to start a loop from here only from the first index fine after these three zeros after three zeros nay for next 3 for next 3 positions one would be there fine so the position of one would be see after these 3 zeros so 3 plus 3 that is 6 up to 6 see index is 5 but position is 6 1 2 3 4 5 6 right so here we are going to we are going to take the count now that is why we are going to take the 6 how we are going to find out this position five I'm going to tell you later fine now after after one after one next for would be 2 so position of this tomb would be 6 plus 4 that is 10 till 10 here see Nexus 9 but position is 10 this is how we are going to update this area so now next is this for this 3 10 plus 0 that is n only 10 Plus this one this next element and that does 11 10 plus 1 is 2 L position 4 6 is 12 plus 0 that is 2 L four seven four seven that would be 12 plus 2 that is 14 4 8 14 plus 1 15 15 plus 2 17 4 9 it is 17 so this is how now the updated company so now this head is going to reflect the actual position of this element in the sorted array now I am going to write down the code fine see how to update this count array see when for loop would be there we are going to start the for loop from 1 so I is equal to 1 I less than equal to K value K is 9 so I less than equal to 9 and I plus plus now how have you are going to update this see we have done what we have just taken us three value as a T's then 3 plus next fine 6 then 6 plus next n like this we have done so how we are going to do this see this count of I would be count of I plus count of I minus 1 see I have started from one that is why count 1 here count to 1 this count 1 would be 3 plus 3 that is 6 means count to 5 plus previous value I minus 1 sorry I minus 1 fine so this is how we are going to update this area now we are going to build the output area how we are going to build this Harry this output I see I see we have taken 1 another array the name is supposed be the size is same as the original area having element 17 total element 17 how we are going to fill this area this array would be sorted a say this is our original area we are going to scan this area from right to left from here we are going to take one variable Y I am going to start from here I am going to tell you that thing also see first of all suppose I am going to start from here the value is 9 right key value is 9 so what you have to do in count in count array you just you just go say this is our updated count array we are going to see this now we are not going to see this one so see just go to the index 9 this is the next 9 right value is 9 go to index 9 in countering right but we cannot store 9 at 17 because we don't have 17 this is the count but we are actually working on the index now so first of all we are going to decrement this by 170 minus 1 that is 6 stream and in the output array go to the index 16 and store this knife this is the actual place for this 9 fine now decrement I now eyes at this place find out the value at this that is 1 now go to the index 1 in this counter index 1 value is 6 but we are not going to store one here why so because this is count value but we are we are going to store at index 5 fine so first of all we are going to decrement this by 1 that is five and now we are going to store at five here we got one fine why we have started from here see you can start from here you will get sorted anything but I am going to start from here just to maintain the stability of this counting sword now what is that stability of sort see let us suppose in this case in this case this is nine and this is nine both are same nine and nine the position of this is twelve indexes to l and indexes 16 so this nine is before this nine right the position is before this line so in sorted array this nine should be before this nine the position of this nine should be before this 9 that is the stability that is the stable sort although we can write in the sorting in the sorting the sorted array you can write this line here and this nine at this place but the value is same obviously there it would be sorted but this will not maintain the stability of the sorting algorithm fine if you start from here only that is why to maintain just the stability I am going to start from here now decrement I now here value is zero go to the index 0 value is 3 first decrement this value that is 2 now in this output array at index 2 store 0 next decrement I value is to go to the index 2 value is 10 but first of all decrement this that is 9 and now at ninth Index store what to now again decrement value is 9 now see again go to the index 9 at index 9 update the value is 16 but first of all we are going to decrement this that is 15 and add 15 index in output array you are going to store this 9 so see as you can see here this this line is at place 15 and this at 16 and 15 is before 16 or you can say less than 16 so this is how we are going to maintain the stability fine now decrement again is 7 now go to the index 7 here is 7 in the updated count sort value is 14 first of all decrement this that is 13 and at the index 13 now store 7 again decrement our value we have again 7 go to the index 7 value is 13 first of all decrement this that is 12 now at index 2 L store 7 decrement this that is it go to the index 8 value is 15 decrement this that is 14 at 14th store a decrement this so the value is 2 now go to the index 2 in this count array at index 2 value is 9 first decrement this value that is 8 and 8 index now we are going to store this value to decrement this I value now 0 go to that and X 0 value is to decrement this one we are going to store 0 here decrement this one value is 4 go to the index 4 here the value is 11 decrement this first of all 10 a tenth index we are going to store for now determine this here the element is 5 key value is 5 go to the index 5 at index 5 in the count array here the value is number is 12 decrement this first of all that is 11 at 11 we are going to store not 5 fine again decrement I value now here the key value is to go to the index to here the value is 8 decrement this first of all 7 now at 7 we are going to store 2 now go to this this place value is 0 go to the index 0 here we have 1 decrement this that is 0 add this at the 0th index we are going to store 0 again decrement I value here the key value is 1 go to the index 1 value is 5 decrement this first of all 4 at 4 via go we are going to store 1 you can't agreement 1 go to this index one values for decrement this that is three at third we are going to store one now decrement this two now at an x2 value is 7c update the value is 7 we are going to decrement the status six at six we are going to place this to now fine and we are going to store because we have reached to 0th index now you can say this is the sorted array fine so we have taken another area that is B now simply what you have you do you simply copy the content of this array the element of this array to this array with a for loop now how to write down this thing into code how to build this array see we have just this is one for loop for this this is for loop for this updated count and now this for loop is for building this output array fine we have started our for loop from here fine so I value would be n minus 1 till I greater than equal to 0 and I - - fine now whether that's for loop what you will write see first of all what we have done we are going to take this value and you are going to place this value in the sorted array after finding proper position using this count fine so take this value this value how to take this value array name is a and a of I see a of I this is how we are going to assess this element now where to put this element to this side what you will write we are going to put this element in array B but first of all you have to find out the proper index in this b4 that index what you will do you will use count array fine and in count array also for finding this index you will use this value right see the value is 9 so same we are going to index nine fine see so this is how we are going to write count a oh I fine see let us say fi is 9 so count 9 count of nine this index now what we have done decrement this index first of all fine so we will decrement this - - see first we will decrement then we are going to store so pre-decrement so after decrementing the value is what we have got 16 fine now this 16 is the index in this array B where we are going to store this value fine so this is the index and name is Harry B so in B array this is the index you are going to calculate where you are going to store the value a Oh fine fine this is how we are going to build this array so now at last one another for loop would be there just to copy the value of this area into the original area so what you can write after this for loop for I is equal to 0 to I is equal to less than n or less than equal to n minus 1 I plus plus just copy the content here any name is a we are going to copy the content of B into hey this is how we are going to code this thing fine this the logic this logic these for for loops you are going to write in a function that is you can take count sort the name would be maybe count so in count sort you can pass array or you can say the number of elements and sometimes key value would also be passed it is given then you can pass the K value fine or if you will not pass the K value here you can calculate within this function you can calculate the K value just find out the maximum element from the given array that could be the K value fine and just take initializer array count I guess you can take this one thus sorry the size would be capable one something like this take another area that is B and this B would be same as the size of original area if an element's then be off in something like this so I guess you can write down this counts or initialize or declare this count array or Bieri something like this this is the main logic these four four loops and just call this count sort function into main function C now what is the time complexity for this count sort I am complexity would be 1 see time complexity is what just find out the calculations for the for loops given in the program how many for loops 1 2 3 4 how many times the statements written within the for loops has been executed how many times C this for loop this statement has been executed for n times find n times plus this for loop K times this for loop also n times and this for loop also from 0 to n means n times so maybe something like this 3n plus e or you can say order of n plus K this would be the time complexity n plus K where K is given the range and is number of elements in the array so if case suppose a constant you can say so you can neglect this K and you can say order of n in linear time you can sort the elements so one drawback of this count sort algorithm can be say this K value should be feasible what does that mean let us suppose you are you are taking an array a and having 100 elements in the array here we have taken 17 only and in that array we have 100 elements and let us suppose K value is 10,000 now what will happen you are going to create a count array and the size of this count array would be how much from 0 to 10,000 in these locations only hundred elements would be there only hundred elements so many many places in this count sword would be zero zero zero zero something like this fine so this should not be a case in this case this applying of this count suit is not feasible fine so the upper bound the upper bound for this case should be this case should be order of n n means number of elements in the area upper limit for this K would be number of elements in the number of elements is hundred then k can be hundred it's not like it can be hundred it can be 2 n it can be 5 in it can be six in something like this but it cannot be approximately n square fine so this is the pound for this K this case should be order of N and second robic is this count sort will not work for negative values and floating point values you can modify this count sword for negative values after modification it can work maybe you can apply some normalization methods like C minus negative values are there so how you can normalize this how you can apply how you can modify this counts or just find out this minus value is 5 so just add this 5 to all the values minus y + 5 0 + 5 6 + 5 5 + 5 11 + 5 14 plus 5 is 6 + 5 is 5 and here we have 0 now this is very the range would be here C from 0 to 14 you can say fine and again after sorting you can again decrement this you can again do - 5 from the result so this is how you can normalize the negative values and and apply this counts or but this logic directly cannot be applied on negative values and floating-point values plus one more drawback of this count sort is what it cannot be applied if the values are different in any range there is no proper or specific range see the values different values are there in any range so we cannot apply count sort on this algorithm it is better to apply now radix sort for this in such kind of example rednecks sort also use comes sort but in that case we we apply that radix sort in visits own digits first in this then this then then this and then on this fine so if we apply on that digits then you can say K value would always be from zero to nine because these values will be from zero to nine now each digit can be either 0 1 2 up to 9 so K values would be 0 to 9 so how we can apply this counts out in the radix sort we will discuss in the next video as well as I'll write down a piece of code for this that radix sort algorithm fine so I'll see in the next video till then bye bye I take it

Channel: Jenny's Lectures CS IT

Views: 241,355

Keywords: selection sort in c, bubble sort in c, sort, heap sort, quick sort, sorting algorithms, merge sort, sorting algorithms complexity, bucket sort, counting sort, radix sort, insertion sort, ugc net computer science, cse, it, computer science youtube channels, jennys lectures, jayanti khatri lamba, data structure, data structure and algorithms, algorithm, engineering, c programming, data structure notes, best youtube channel, gate, GATE computer scence, study material, net and jrf

Id: pEJiGC-ObQE

Length: 31min 40sec (1900 seconds)

Published: Thu Jul 18 2019