7.10 Radix Sort/Bucket Sort in Data Structure | Sorting Algorithm

here the numbers are not compared like the C we have done in other another sorting algorithm suppose I'm taking 15 and 10 then I'm going to compare this 15 with me with this 10 his 15 greater than 10 yes then do swapping something like this see we are not going to do any comparison here between the numbers given right so now if no comparison is there then how the data is to be sorted see data is to be sorted here desert by desert we are going to solve the data according to the place value of the desert but you can say the position of the desert in that number see suppose we are taking a number 4 to 1 right so this is what C place value is what here we have this place value of this one is once place value of 2 is tens place value of this 4 is hundreds fine and face value of this one is 1 face value of this is to face value of this is for eye I hope you know what is face value and place value right so we are going to start from the least significant digit least significant visitors this side and this is the most significant desert so I am going to start the sorting from this least significant desert and we're going to move towards most significant digit right desert by desert the data is to be sorted so see how that it has to be sorted digit by digit let us take this example you are going to solve this one we are going to we are going to solve this data using radix sort fine see the sorting algorithm we have discussed bubble quick merge selection insertion those are comparison based sorting and the best best time complexity for those comparison based algorithm is order of n log N or you can say Omega n log n they cannot do better than this so after sorting we we are also going to see what is the time complexity for this radix sort fine see here the first step in this sorting algorithm is out of these given numbers find out the maximum number fine now see by looking at these number we can see the maximum number is what 8 0 2 second step is calculate how many visits are there in this maximum number how many deserts are there one two and three now third step is you are going to make all these numbers or three-digit number right now how we are going to make you are going to put zeros now where where you are going to put a zero suppose this has the number this is two digit number one and two now where you are going to put a zero to make it a three-digit number you cannot put a zero here because if you put a zero here then it will become 150 and the number is 15 fine so you cannot change the number the value of this number that is why we are going to put a zero to the hell this side now all the numbers are three-digit number fine here and X means basically the base so here I am dealing with decimal numbers so base for decimal number is 10 right so that is why I am going to take 10 buckets this is also known as bucket sorting so here we are going to take 10 but 10 buckets from 0 to 9 fine see this sorting algorithm is also used to sort strings so you can say alphabets in that case the base is 26 for alphabets so we are going to take buckets from 0 to 25 right in that case how we are going to sort suppose I am going to take two names one is Jenny and one is Jia so in that case we are going to start from here but you can say from MSB you can say from the most significant bit right so we are compared with this with this both are J then fine again we are going to compare second here we have a here we have I so he comes first then I so this is this Jenny comes first today Jia right in case of numbers we are going to we are going to check from this side from the least significant digit right now see so now we are going to take 10 buckets ranging from 0 to 9 right and now we are going to put these numbers into these buckets now the next step is how we are to fill these buckets see this is pass one so in past one we are going to salt we are going to sort these numbers according to which visit the least significant digit and the least significant digit is this one so we are going to check this desert of every number right and see so first of all take this number the least significant desert is five so now we are going to put this number in which bucket in fifth bucket the number the bucket having number five so here I am going to put this one zero one five next number is zero zero one now we are sorting the data according to this this visit so I am just going to check this desert here we have one so I am going to put this in bucket 1 here we have one so I'm going to put again this in one here we have zero so we are going to put this in zero here we have two in bucket two here we have two in bucket two here we have three so we are going to put this in bucket three here we have zero again we are going to put this in bucket zero the nine we are going to put this in ninth bucket and then one we are going to put this in zero one one one bucket right now next step is we are going to remove the data from this these buckets and how starting from zero the bucket now say this bucket is having two numbers now which number you are going to remove first this number the first number right not this number you remember you are going to move this number first so in one bucket also from first this then this then this now remove one by one from data from all buckets and after pass one after pass one the data is something like this first of all remove this one so the data is 0 1 0 then 90 then 0 0 1 then you remove 321 then 0 1 1 now after first pass the data is this one so here one more thing you have to here the passes would be same as number of visits in the maximum number so maximum number is a 2-0 - number of visits are three so here we have three passes so after pass one the data is something like this now pass two in past two we are going to sort the data according to which does it distill it the second one right the desert of it which is at tenth place we have already sorted the data coding to this visit the desert a bit which is at one place right now this does it now again we are going to take 10 buckets now repeat the same step check first number this 1 0 1 0 now we are going to take which it is it this one the desert which is at 10th place now here we have 1 so we are going to put this in this bucket bucket number 1 we have 9 so we are going to put this in this bucket here we have 0 0 1 in 0th bucket 3 2 1 2 second bucket 0 1 1 in one bucket 8 0 2 0 is there so here 2 0 2 here also we have 0 here we have 2 1 2 3 here we have 1 0 1 5 and here we have 0 1 0 9 these buckets are in pretty fine so that's fine now next step is what you are going to remove the data from these buckets and how from the starting bucket and from starting book at all so if many numbers are then then we are going to remove the first number first right so after pass - this is passed - so after pass - the data is something like this remove this 1 0 0 1 8 0 2 0 0 2 1 0 9 here we have 0 1 0 so after pass to the data is this one now the last pass that is the third pass in that pass we're going to sort the data according to which visit the third one this one the desert which is at hundredth place right so now repeat the same step we are going to take again 10 buckets this is past 3:00 again we are going to take 10 buckets ranging from zero to nine again we are going to fill these buckets half so these are the number after past two so now we are going to see which digit to that third one third one so now here we have zero where we are going to put this in 0th bucket here we have eight eight zero two zero zero zero two one zero nine zero one zero here we have again zero one one zero one five three two one three two one one two three so does it is one here we have zero zero nine zero right so these are the buckets now now next step is what you are going to remove data from these buckets right and remove means we are going to store the data in an output array so here is zero zero one sugar you can write one here we have two here we have ten eleven fifteen ninety one zero nine one two three three two one and finally a 2-0 - so this is the data after pass three so as you can see this is the sorted data now so here we have removed the extra zeros we have put to make the numbers three-digit number right so this is now the sorted data as you can see how many passes are required three means the number of deserts in the maximum number those number of passes would be required here we have three deserts so three passes would be required so this is how radix sort will sort the data see this reddick sort use what count sold as a subroutine so you know what is a count sort right and if you say the running time complexity for this sort is what you can write order of B into n plus B now here see these what number of digits in maximum number number of digits are three so here for each digit we are going to repeat the steps right first of all for this it is it understand this how many times three times you have repeated so here we are taking B into n is the number of how many numbers are there plus B is what base what is base here because we are going to take buckets equal to the base here base is 10 so we are going to take 10 buckets in alphabets basis to intersect so in that case we will take 26 buckets from 0 to 25 that is why I am going to take here BN plus B and D is number of deserts so we are going to repeat the steps here for 3 times the number of digits times right so this is the time complexity so this is all about bucket salt or you can say this radix sort in next video we are going to discuss shell sorting so till then bye bye I take

Channel: Jenny's Lectures CS IT

Views: 297,594

Keywords: radix sort, sorting algorithm, all sorting algorithms, cs it youtube channel, computer science, information technology, computer science engineering, jenny lamba, jayanti khatri lamba, jayanti khatri, NET coaching, GATE COaching, NET computer science, GATE Computer science, NET JRF CS IT, NET JRF CSE IT, data structure, abdul bari, data structure algorithm, NTA NET, jennys lectures, jenny's lectures, bucket sort, bin sort

Id: JMlYkE8hGJM

Length: 11min 51sec (711 seconds)

Published: Sat Jun 22 2019