Linear-time sorting, part 2: Counting Sort, Radix Sort and Bucket Sort

Three linear-time sorting algorithms: counting sort works well if the numbers to be sorted are not too big (O(n)). With Radix Sort we can push things a bit further. Finally, Bucket Sort is not for sorting integers, but numbers nicely spread out between 0 and 1.

Timeline:
0:00 Counting Sort: position(i)
5:06 Counting Sort: algorithm
11:27 Counting Sort: correctness + running time
18:14 Radix Sort
27:42 Bucket Sort
33:58 Bucket Sort: running time
38:22 E[n_i^2]
43:28 Wrap-Up

[salmaabousaid]

The bucket sort time complexity analysis was very good. Thank you so much!

[sufiyanadam]

It is fascinating to me that the syllabus for Design Analysis and Algorithms for Bachelor of Science (CS Hons) of the University of Delhi corresponds so well to your playlist, almost every single topic is part of the current 2022 LOCF syllabus or was a part at an earlier time in the past; for instance, Red Black trees, they have recently been removed from the syllabus but they were surely an important part of the question paper in previous years. Even the Cormen's Algorithms book is prescribed in the syllabus, but that is a standard book across most of the universities.

[amisha]

sir everywhere its given "Radix Sort/ Bucket sort" so i am confused if its same or different method. According to my research Is it that Radix places elements in bucket from msd to lsd one by one and Radix has decimal numbers and puts them in bucket from first element after 0.? please help me clear this confusion.