sorts.flash_sort

Flash Sort Algorithm Implementation

Flash sort is a distribution sorting algorithm showing linear computational complexity O(n) for uniformly distributed datasets and relatively little additional memory requirement. The basic idea is to use the distribution of the values to be sorted to determine their approximate final positions directly, without comparing and moving each element through many intermediate positions as done by other algorithms.

The algorithm was developed by Karl-Dietrich Neubert in 1998 and builds upon the idea of bucket sort. It works by classifying elements into classes and then sorting each class.

Time Complexity: - Best Case: O(n) when data is uniformly distributed - Average Case: O(n + k) where k is the number of classes - Worst Case: O(n²) when data is not uniformly distributed

Space Complexity: O(k) where k is the number of classes

Source: https://en.wikipedia.org/wiki/Flashsort

Attributes

test_cases

Functions

flash_sort(→ list[int | float])

Sorts a list using the Flash Sort algorithm.

Module Contents

sorts.flash_sort.flash_sort(arr: list[int | float]) → list[int | float]

Sorts a list using the Flash Sort algorithm.

Flash sort is particularly efficient for uniformly distributed data. It uses the distribution of values to determine approximate positions.

Args:

arr: List of integers or floats to be sorted

Returns:

Sorted list in ascending order

Examples: >>> flash_sort([4, 2, 7, 1, 9, 3]) [1, 2, 3, 4, 7, 9] >>> flash_sort([]) [] >>> flash_sort([5]) [5] >>> flash_sort([3, 3, 3, 3]) [3, 3, 3, 3] >>> flash_sort([-1, -5, 0, 3, 2]) [-5, -1, 0, 2, 3] >>> flash_sort([1.5, 2.3, 0.1, 3.7, 1.2]) [0.1, 1.2, 1.5, 2.3, 3.7] >>> flash_sort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] >>> import random >>> data = random.sample(range(100), 20) >>> flash_sort(data) == sorted(data) True >>> flash_sort([42]) [42] >>> flash_sort([2.5, 1.1, 3.3, 2.5, 1.1]) [1.1, 1.1, 2.5, 2.5, 3.3]

sorts.flash_sort.test_cases: list[list[int | float]]