JavaScript Searching and Sorting Algorithm: Flash sort
JavaScript Searching and Sorting Algorithm: Exercise-12 with Solution
Write a JavaScript program to sort a list of elements using Flash sort.
Flashsort is a distribution sorting algorithm showing linear computational complexity O(n) for uniformly distributed data sets and relatively little additional memory requirement. The original work was published in 1998 by Karl-Dietrich Neubert.
The basic idea behind flashsort is that in a data set with a known distribution, it is easy to immediately estimate where an element should be placed after sorting when the range of the set is known.
Sample Solution: -
HTML Code:
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript program of Flash sort</title>
</head>
<body></body>
</html>
JavaScript Code:
function flash_sort(arr)
{
var max = 0, min = arr[0];
var n = arr.length;
var m = ~~(0.45 * n);
var l = new Array(m);
for (var i = 1; i < n; ++i) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > arr[max]) {
max = i;
}
}
if (min === arr[max]) {
return arr;
}
var c1 = (m - 1) / (arr[max] - min);
for (var k = 0; k < m; k++) {
l[k] = 0;
}
for (var j = 0; j < n; ++j) {
k = ~~(c1 * (arr[j] - min));
++l[k];
}
for (var p = 1; p < m; ++p) {
l[p] = l[p] + l[p - 1];
}
var hold = arr[max];
arr[max] = arr[0];
arr[0] = hold;
//permutation
var move = 0, t, flash;
j = 0;
k = m - 1;
while (move < (n - 1)) {
while (j > (l[k] - 1)) {
++j;
k = ~~(c1 * (arr[j] - min));
}
if (k < 0) break;
flash = arr[j];
while (j !== l[k]) {
k = ~~(c1 * (flash - min));
hold = arr[t = --l[k]];
arr[t] = flash;
flash = hold;
++move;
}
}
//insertion
for (j = 1; j < n; j++) {
hold = arr[j];
i = j - 1;
while (i >= 0 && arr[i] > hold) {
arr[i + 1] = arr[i--];
}
arr[i + 1] = hold;
}
return arr;
}
var arra = [3, 0, 2, 5, -1, 4, 1];
console.log("Original Array Elements");
console.log(arra);
console.log("Sorted Array Elements");
console.log(flash_sort(arra, 0, 5));
Sample Output:
Original Array Elements [3,0,2,5,-1,4,1] Sorted Array Elements [-1,0,1,2,3,4,5]
Flowchart:
Live Demo:
See the Pen searching-and-sorting-algorithm-exercise-12 by w3resource (@w3resource) on CodePen.
Improve this sample solution and post your code through Disqus
Previous: Write a JavaScript program to sort a list of elements using Counting sort.
Next: Write a JavaScript program to sort a list of elements using Pancake sort.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
JavaScript: Tips of the Day
How to insert an item into an array at a specific index (JavaScript)?
What you want is the splice function on the native array object.
arr.splice(index, 0, item); will insert item into arr at the specified index (deleting 0 items first, that is, it's just an insert). In this example we will create an array and add an element to it into index 2:
var arr = []; arr[0] = "Jani"; arr[1] = "Hege"; arr[2] = "Stale"; arr[3] = "Kai Jim"; arr[4] = "Borge"; console.log(arr.join()); arr.splice(2, 0, "Lene"); console.log(arr.join());
Ref: https://bit.ly/2BXbp04
- New Content published on w3resource:
- HTML-CSS Practical: Exercises, Practice, Solution
- Java Regular Expression: Exercises, Practice, Solution
- Scala Programming Exercises, Practice, Solution
- Python Itertools exercises
- Python Numpy exercises
- Python GeoPy Package exercises
- Python Pandas exercises
- Python nltk exercises
- Python BeautifulSoup exercises
- Form Template
- Composer - PHP Package Manager
- PHPUnit - PHP Testing
- Laravel - PHP Framework
- Angular - JavaScript Framework
- Vue - JavaScript Framework
- Jest - JavaScript Testing Framework