Algorithms: sorting algorithms compared

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

667

This video is part of Professor Frank Stajano's lecture course on Algorithms at the University of Cambridge.

As we conclude our overview of sorting algorithms, this video provides a brief recap.

We saw four quadratic sorting algorithms: insertsort, selectsort, binary insertsort and bubblesort. We proved that the optimal asymptotic cost of a comparison sort is O(n lg n), therefore quadratic algorithms are sub-optimal.

We investigated three plausible algorithms: mergesort, heapsort and quicksort. The first two are asymptotically optimal. The third isn't (it's actually quadratic) but, paradoxically, is usually faster than them if it doesn't hit its worst case. You should be aware of the trade-offs between them.

In special circumstances you might be able to sort in linear time. We explained counting sort, bucket sort and radix sort.

The animation of sorting algorithms visible in the background is due to Timo Bingmann: • 15 Sorting Algorithms in 6 Minutes

If you like this video, give it a thumbs up. Subscribe and hit the notification bell for more of the same and to encourage me to publish more videos for budding computer scientists. If you have any questions or comments (or, why not, answers to other people's questions), leave them below.

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

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

My home page:
http://frank.stajano.com