Algorithms: how to sort in linear time: counting sort, bucket sort, radix sort

Опубликовано: 28 Декабрь 2020
на канале: Frank Stajano Explains

1,015

I have been teaching the Algorithms course at the University of Cambridge since 2005 and through these videos you may attend my lectures from anywhere in the world.

We previously established that the optimal cost of sorting is O(n lg n). In this video we show how to go faster than that. Of course we can only do that under special circumstances that invalidate the general assumption under which the above optimal bound was derived, namely that all the sorting algorithm knew about its input was that the elements to be sorted could be compared pairwise to find out if the first was less than, equal to or greater than the second.

I explain three linear-time sorting algorithms: counting sort, bucket
sort, radix sort.

If you find this video useful, support the channel by clicking the thumbs up button and by subscribing. Click the notification bell to be told when I publish new videos.

Course web page:
https://www.cl.cam.ac.uk/teaching/cur...

Course handout:
https://www.cl.cam.ac.uk/teaching/202...

My home page:
https://www.cl.cam.ac.uk/~fms27/