Samuel's tutorial for the bucket sort algorithm (runtime complexity and Python implementation).

Timestamps:
00:00 - Bucket Sort: Samuel's tutorial
00:24 - Bucket Sort
01:52 - Bucket Sort Python Implementation
03:44 - Bucket Sort Runtime Complexity
05:55 - A Variation of Bucket Sort

Corrections:
04:32 - This should say E[m_i] = 1

Detailed description:
This video covers the properties of bucket sort, a distribution sorting algorithm.

The main idea behind bucket sort was introduced by Earl Isaac and Richard Singleton in their 1955 paper, "sorting by address calculation." We first describe how bucket sort uses scatter, sort and gather operations. Then we describe its runtime complexity (big theta of n in the average case for n keys if we use the same number of buckets as keys).

Next, we step through an animated Python implementation of bucket sort to show how the scatter, sort and gather operators combine to produce a sorted output. We then explain why it is the bucket sort has linear complexity in the average case (provided that the keys follow a known distribution and that buckets are chosen appropriately).

Finally, we describe a variant of bucket sort that can produce a fast implementation.

Topics: #bucket #sorting #algorithms

Python code to implement bucket sort can be found here: https://github.com/albanie/algorithms...

Slides (pdf): https://samuelalbanie.com/files/diges...

References for papers mentioned in the video can be found at
http://samuelalbanie.com/digests/2023...

For related content:
Twitter:   / samuelalbanie  
Research lab: https://caml-lab.com/
web page: https://samuelalbanie.com/
YouTube:    / @samuelalbanie1