Radix Sort Algorithm - Theory + Code

Рет қаралды 23,892

Kunal Kushwaha

Күн бұрын

Пікірлер

@KunalKushwaha 5 ай бұрын

DSA + interview preparation playlist: kzbin.info/aero/PL9gnSGHSqcnr_DxHsP7AW9ftq0AtAyYqJ

@yahyamohamoud7290 Жыл бұрын

so much amazing content all at once, the least everybody could do is like and share for more

@chrisumeran Жыл бұрын

Wow, five new videos all at once. See, just trust Kunal. It doesn't matter how long it will take because when he does, it always delivers. Thanks for all of these brother. Much love from Philippines.

@DivyanshuSharma-vp4pw Жыл бұрын

@KunalKushwaha Bhaiya there is question 2343 (Leetcode) which is based on Radix Sort it will be a great question to clear the concept of Radix Sort more clearly

@iswitchcomputerscience7071 7 ай бұрын

I tried the same approach as explained in the video for 2343, and it was accepted : class Solution { public int[] smallestTrimmedNumbers(String[] nums, int[][] queries) { int maxLength = nums[0].length(); int[] result = new int[queries.length]; for(int i=0;i

@faizaankhan8090 Жыл бұрын

Kunal you are rocking right now with all the new content. Highly appreciate it!

@sufiserious798 7 ай бұрын

What I did before seeing the method of iterating over original array itself and using the count array which now has cumulative sums for adjusting indices: I made the count array a List of Linked Lists. While counting elements with respective base, I used the obtained digit as index for the list, and then inserted the current element into the linked list at that index. After that I iterated over the count list from 0 to 9th index and for every linked list which wasn't empty, I removed its first element (head) and added it into the sorted array, this was repeated till linked list became empty. (Single Removal happens in constant time as a linked list is used) After iterating over the count list the array was sorted according to the selected base digits in each element. Repeating this iteration for 'digit' times, I finally obtained the final sorted array.

@MahmoodAlSaghiri 6 ай бұрын

I did the same exact thing, I am struggling to understand this method though (the one Kunal demonstrates). if you understand it can you help explain what is happening?

@sufiserious798 6 ай бұрын

@@MahmoodAlSaghiri He is taking a cumulative sum inside the frequency/count array. By doing this, at every index in the count array we know how many other elements appear before the current index. Eg: Array: [24, 11, 91, 44, 31, 58, 48, 27] our frequency array for base 1: [0, 3, 0, 0, 2, 0, 0, 1, 2, 0] By looking at it we know that for our selected digit place for all elements: 1 appears 3 times 4 appears 2 times 7 appears 1 time 8 appears 2 times Now if we take cumulative sum: (adding value of previous element to value of current element, starting from index 1 and repeating till 9) [0, 0+3, 3, 3, 3 + 2, 5, 5, 5 + 1, 6 + 2, 8] That is: [0, 3, 3, 3, 5, 5, 5, 6, 8, 8] Now we also know that how many elements will appear before the current element in the sorted array and using that we can get correct index for current element in O(1) constant time. Remember that, Radix Sort is a 'stable sort' algorithm which means that when elements are equal, then they are placed in the order in which they appeared in the original array. Due to this we need to start traversing the original array again but now in REVERSE order So let us again note what we have currently: Cum. Sum Frequency Array: X = [0, 3, 3, 3, 5, 5, 5, 6, 8, 8] Original Array: [24, 11, 91, 44, 31, 58, 48, 27] New Sorted Array: sorted = [0, 0, 0, 0, 0, 0, 0, 0] Traversing Org. Array in reverse: 27 -> index is 7 -> X[7] is 6 (we know that 5 numbers will appear before '27' and it is the 6th element) -> However, array will be zero-indexed therefore we take: 6 - 1 = 5 -> sorted[5] = 27 -> (Important step) X[7] = X[7] - 1 = 6 - 1 = 5 We reduce the count for current index in frequency array. If we come across another element that also provides index '7' we now know that there will be only (5 - 1 = 4) elements before it as '27' is already placed. Now: X = [0, 3, 3, 3, 5, 5, 5, 5, 8, 8] sorted = [0, 0, 0, 0, 0, 27, 0, 0] Similarly for, 48 -> sorted[X[8] - 1] = sorted[8 - 1] = sorted[7] = 48 -> X[8] -= 1 X = [0, 3, 3, 3, 5, 5, 5, 5, 7, 8] Sorted = [0, 0, 0, 0, 0, 27, 0, 48] 58: X = [0, 3, 3, 3, 5, 5, 5, 5, 6, 8] Sorted = [0, 0, 0, 0, 0, 27, 58, 48] 31: X = [0, 2, 3, 3, 5, 5, 5, 5, 6, 8] Sorted = [0, 0, 31, 0, 0, 27, 58, 48] 44: X = [0, 2, 3, 3, 4, 5, 5, 5, 5, 6, 8] Sorted = [0, 0, 31, 0, 44, 27, 58, 48] 91: X = [0, 1, 3, 3, 4, 5, 5, 5, 5, 6, 8] Sorted = [0, 91, 31, 0, 44, 27, 58, 48] 11: X = [0, 0, 3, 3, 4, 5, 5, 5, 5, 6, 8] Sorted = [11, 91, 31, 0, 44, 27, 58, 48] 24: X = [0, 0, 3, 3, 3, 5, 5, 5, 5, 6, 8] Sorted = [11, 91, 31, 24, 44, 27, 58, 48] We get an array sorted at units place. This gets copied into original array and process is repeated for different bases to obtain the final sorted array.

@MahmoodAlSaghiri 6 ай бұрын

@@sufiserious798"By doing this, at every index in the count array we know how many other elements appear before the current index." This is the sentence that I couldn't find anywhere. Thanks for the explanation it all makes sense now. I appreciate you

@KunalKushwaha Жыл бұрын

👉 Resources - Join Replit: join.replit.com/kunal-kushwaha - Lecture code: replit.com/@KunalsReplit/RadixSort

@mittalkabir277 Жыл бұрын

Kunal When you complete this course? I watch your all videos of java dsa and practicing as much question as i can but problem is placement session is going on and you don't complete all topics till now ☹️

@the_sage_007 Жыл бұрын

@kunal I have a interview lined up next week with one of MAANG, and it would help a lot to revise and prepare if you can upload DP videos :) [ Only theory will also work ] The videos until now are the only thing needed for solving any problem - Rightly said. Thanks

@idfortablenovo5012 Жыл бұрын

Are all the lectures enough or have to go for paid version

@gojosatoru988 Жыл бұрын

4 videos in just 1 day!!!!!!! I'm dreaming or what!!! ❤❤❤❤

@abhayrana5965 Жыл бұрын

your teaching style, just aww , kunal 🔥🔥

@manishbera2902 Жыл бұрын

Hey kunal how much time will it this course take to complete?? I mean can you do it by the end of this year?? Just asking as i caught upto your videos and is practicing the previously taught concepts by you .....

@KunalKushwaha Жыл бұрын

Yes, by December

@abhijitmanna4524 Жыл бұрын

It will be good if you complete it by Dec mid , my semester is getting over by that time, so I want to complete the playlist and crack for companies, this time companies are not coming like last year, I can wind up in 2 or 3 months, I am in my final year

@mahirr8090 Жыл бұрын

Thanks a lot Kunal for such amazing explanation... Keep it going❤️

@sanjanachauhan217 Жыл бұрын

Keep up the good work!!🎉

@TanishRealm 3 ай бұрын

Great video bro keep it up

@its_shivam_jha Жыл бұрын

4th video of the day... 😱

@siddimahendra2049 9 ай бұрын

kunal I request please give animation of algorithm also,makes esier to undersgtand

@iel958 Жыл бұрын

Love you bhaiya .. Thank you so much🙇🏻‍♀️😃

@Balaram12-hj2ot Жыл бұрын

Kunal bro, plz try to upload all the dsa videos completely to the current trend

@santoshis2568 Жыл бұрын

Hi Kunal can you do a video on sliding window problems?

@Karthi_Max Жыл бұрын

It would be grateful if u cover the same in c++. Try to demonstrate in both c++ & java. Coolest explanation. Thanks

@hardeepdhull3793 Жыл бұрын

Bro bombarded content.

@AnonymousCoder7 Жыл бұрын

Woahhh... Hold on Kunal 👾👾... Way too much of a surprise from you !! 😅😅

@kishore8940 Жыл бұрын

Kunal I'm waiting more than a year, when you going to finish DSA bootcamp

@VivekYadav-iv3pb Жыл бұрын

Bhai heap ka next video bacha hai . Please complete kar do

@abhisheksah99 5 ай бұрын

kunal bhaiya 8 mahina hogaya ,ak bad phir akar course complete kardo yaar,mujha pata ha aap busy ho lakin aap kiya apko roj dekhna ki aur apsa padhna ki aadat hogayi ha to aakar complete kardo playlist

@dshorts9604 Жыл бұрын

Bhailog kunal bhaiaya full mood me hai abhi . Mein abhi dsa start nahi kya hu fir bhi dekhne aya hu kitna video upload hua kyoki baad me inhi ka video dekhna hai 😂😂😂😂😂

@SB20002 Жыл бұрын

Please make a video on multithreading

@Nutrino259 Ай бұрын

what if array contains -ve numbers??????

@pankajsingh-wr6yl Жыл бұрын

Thanks kunal

@rahulnishad24 Жыл бұрын

Hey Kunal Pls pls pls complete greedy and trie also

@sparkspark-tn6sc Жыл бұрын

Thank you very much

@sarfrasahamed3322 Жыл бұрын

hello bro your teaching is good and your content is good but we need the contents very immidiately....because we are preparing for our interview this year and we are jobless now

@madhugandamala8995 3 ай бұрын

to see my comment please run this code 😀 class main { public static void main(String args[]) { System.out.println("this DSA palylist is best playlist ever i seen") } }

@jk-sm6qr 9 ай бұрын

thanks

@chikuu6770 10 ай бұрын

so based on kunal explanation I think they don't ask radix sort in interview😆

@mrmadhan8557 Жыл бұрын

🔥🔥🔥🔥

@karthikeyareddy9794 Жыл бұрын

It's amazing ❤...

@pikajil1663 8 ай бұрын

hi bro I want to ask about the taking digits count using log. For all digits it works great but for the 1000 and other 10's power it given 1 lesser digit like 1000 the answer is 4 it giving 3.

@dharminnagar6226 8 ай бұрын

Hi, just take the ceiling of the output given by log

@mohmmedjilanibabu1296 8 ай бұрын

Bro If I ceil it then the other numbers are getting one digit extra. Why don't you try and tell me

@sufiserious798 7 ай бұрын

@@mohmmedjilanibabu1296 We just convert the result of Math.pow() to an integer, which gives us floored integer value. After that we add 1 to it and that will always be the number of digits. This is not special for 10, 100, 1000... But it is the same for all other numbers. Eg: 1) 432 Log10(432) = 2 This means that, 432 contains 2 powers of 10. Note that, 2 is not the exact answer but it will be a double value like 2.635, but when we type cast it to (int) we get 2. Now we add 1 to it to get: 2 + 1 = 3 that is the number of digits in 432 2) 100 Log10(100) = 2 Here, though the value I still double like 2.0, we get an exact 2 as 100 is an exact 10 to power 2. Again, we add 1 to the answer: 2 + 1 = 3 that is the number of digits in 100. Make sure that you are using '10' as the base for log and you are typecasting the log result to 'integer' Suppose our integer variable is 'x' and we want to find the number of digits in that integer. In Java this can be done by: int digits = (int)(Math.log(x) / Math.log(10)) + 1; Here we are making use of the log formula: Log(a) / Log(b) = Logb(a) where 'b' becomes the base of the log.