Algorithm Speed (2.00) :

Array Size (100) :

Flash Sort :

Author(s) : Karl-Dietrich Neubert Date : 1998

Flash sort is a distribution sorting algorithm that operates in linear time O(n) for uniformly distributed data sets. It works by classifying elements into classes (or buckets) based on their values, counting the number of elements in each class to determine their positions, and then permuting the elements into their correct classes. Finally, it uses insertion sort to sort within the classes.

Time Complexity	O(n + k)
Best Case	O(n)
Worst Case	O(n²)
Space Complexity	O(n)
Stable	No

def flashsort(arr):
	n = len(arr)
	if n <= 1:
		return arr
	max_val, min_val = max(arr), min(arr)
	range_val = max_val - min_val
	if range_val == 0:
		return arr
	m = int(0.45 * n)
	dist = [0] * m
	for i in range(n):
		bucket = int((m - 1) * (arr[i] - min_val) / range_val)
		dist[bucket] += 1
	for i in range(1, m):
		dist[i] += dist[i - 1]
	count = 0
	j = 0
	k = m - 1
	while count < n:
		while j > dist[k] - 1:
			j += 1
			k = int((m - 1) * (arr[j] - min_val) / range_val)
		flash = arr[j]
		while j != dist[k]:
			k = int((m - 1) * (flash - min_val) / range_val)
			dist[k] -= 1
			arr[dist[k]], flash = flash, arr[dist[k]]
			count += 1
	for i in range(1, n):
		key = arr[i]
		j = i - 1
		while j >= 0 and arr[j] > key:
			arr[j + 1] = arr[j]
			j -= 1
		arr[j + 1] = key
	return arr

function flashsort(arr) {
	let n = arr.length;
	if (n <= 1) return arr;
	let max = Math.max(...arr);
	let min = Math.min(...arr);
	let range = max - min;
	if (range === 0) return arr;
	let m = Math.floor(0.45 * n);
	let dist = new Array(m).fill(0);
	for (let i = 0; i < n; i++) {
		let bucket = Math.floor((m - 1) * (arr[i] - min) / range);
		dist[bucket]++;
	}
	for (let i = 1; i < m; i++) {
		dist[i] += dist[i - 1];
	}
	let count = 0;
	let j = 0;
	let k = m - 1;
	while (count < n) {
		while (j > dist[k] - 1) {
			j++;
			k = Math.floor((m - 1) * (arr[j] - min) / range);
		}
		let flash = arr[j];
		while (j !== dist[k]) {
			k = Math.floor((m - 1) * (flash - min) / range);
			dist[k]--;
			let temp = arr[dist[k]];
			arr[dist[k]] = flash;
			flash = temp;
			count++;
		}
	}
	for (let i = 1; i < n; i++) {
		let key = arr[i];
		let j = i - 1;
		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = key;
	}
	return arr;
}

public static void flashsort(int[] arr) {
	int n = arr.length;
	if (n <= 1) return;
	int max = arr[0];
	int min = arr[0];
	for (int i = 1; i < n; i++) {
		if (arr[i] > max) max = arr[i];
		if (arr[i] < min) min = arr[i];
	}
	int range = max - min;
	if (range == 0) return;
	int m = (int) (0.45 * n);
	int[] dist = new int[m];
	for (int i = 0; i < n; i++) {
		int bucket = (int) ((m - 1) * (double) (arr[i] - min) / range);
		dist[bucket]++;
	}
	for (int i = 1; i < m; i++) {
		dist[i] += dist[i - 1];
	}
	int count = 0;
	int j = 0;
	int k = m - 1;
	while (count < n) {
		while (j > dist[k] - 1) {
			j++;
			k = (int) ((m - 1) * (double) (arr[j] - min) / range);
		}
		int flash = arr[j];
		while (j != dist[k]) {
			k = (int) ((m - 1) * (double) (flash - min) / range);
			dist[k]--;
			int temp = arr[dist[k]];
			arr[dist[k]] = flash;
			flash = temp;
			count++;
		}
	}
	for (int i = 1; i < n; i++) {
		int key = arr[i];
		int l = i - 1;
		while (l >= 0 && arr[l] > key) {
			arr[l + 1] = arr[l];
			l--;
		}
		arr[l + 1] = key;
	}
}

func flashsort(arr []int) {
	n := len(arr)
	if n <= 1 {
		return
	}
	max := arr[0]
	min := arr[0]
	for i := 1; i < n; i++ {
		if arr[i] > max {
			max = arr[i]
		}
		if arr[i] < min {
			min = arr[i]
		}
	}
	rangeVal := max - min
	if rangeVal == 0 {
		return
	}
	m := int(0.45 * float64(n))
	dist := make([]int, m)
	for i := 0; i < n; i++ {
		bucket := int(float64(m-1) * float64(arr[i]-min) / float64(rangeVal))
		dist[bucket]++
	}
	for i := 1; i < m; i++ {
		dist[i] += dist[i-1]
	}
	count := 0
	j := 0
	k := m - 1
	for count < n {
		for j > dist[k]-1 {
			j++
			k = int(float64(m-1) * float64(arr[j]-min) / float64(rangeVal))
		}
		flash := arr[j]
		for j != dist[k] {
			k = int(float64(m-1) * float64(flash-min) / float64(rangeVal))
			dist[k]--
			arr[dist[k]], flash = flash, arr[dist[k]]
			count++
		}
	}
	for i := 1; i < n; i++ {
		key := arr[i]
		l := i - 1
		for l >= 0 && arr[l] > key {
			arr[l+1] = arr[l]
			l--
		}
		arr[l+1] = key
	}
}

void flashsort(int arr[], int n) {
	if (n <= 1) return;
	int max = arr[0];
	int min = arr[0];
	for (int i = 1; i < n; i++) {
		if (arr[i] > max) max = arr[i];
		if (arr[i] < min) min = arr[i];
	}
	int range = max - min;
	if (range == 0) return;
	int m = (int)(0.45 * n);
	int *dist = (int *)calloc(m, sizeof(int));
	for (int i = 0; i < n; i++) {
		int bucket = (int)((m - 1) * (double)(arr[i] - min) / range);
		dist[bucket]++;
	}
	for (int i = 1; i < m; i++) {
		dist[i] += dist[i - 1];
	}
	int count = 0;
	int j = 0;
	int k = m - 1;
	while (count < n) {
		while (j > dist[k] - 1) {
			j++;
			k = (int)((m - 1) * (double)(arr[j] - min) / range);
		}
		int flash = arr[j];
		while (j != dist[k]) {
			k = (int)((m - 1) * (double)(flash - min) / range);
			dist[k]--;
			int temp = arr[dist[k]];
			arr[dist[k]] = flash;
			flash = temp;
			count++;
		}
	}
	for (int i = 1; i < n; i++) {
		int key = arr[i];
		int l = i - 1;
		while (l >= 0 && arr[l] > key) {
			arr[l + 1] = arr[l];
			l--;
		}
		arr[l + 1] = key;
	}
	free(dist);
}