Алгоритм поиска и сортировки JavaScript: Flash-сортировка

Последнее обновление 9 февраля 2019 08:36:46 (UTC / GMT +8 часов)

script1adsense2code

script1adsense3code

Алгоритм поиска и сортировки JavaScript: упражнение-12 с решением

Напишите программу на JavaScript для сортировки списка элементов с помощью Flash-сортировки.

Flashsort - это алгоритм сортировки распределения, показывающий линейную вычислительную сложность O (n) для равномерно распределенных наборов данных и относительно небольшую потребность в дополнительной памяти. Оригинальная работа была опубликована в 1998 году Карлом-Дитрихом Нойбертом.
Основная идея флэш-сортировки заключается в том, что в наборе данных с известным распределением легко сразу оценить, где должен быть размещен элемент после сортировки, когда известен диапазон набора.

Пример решения: -

HTML-код:

<!DOCTYPE html>
  <html>
  <head>
  <meta charset="utf-8">
  <title>JavaScript program of Flash sort</title>
  </head>
  <body></body>
</html>

Код JavaScript:

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));

Пример вывода:

 Оригинальные элементы массива
[3,0,2,5, -1,4,1]
Сортированные элементы массива
[-1,0,1,2,3,4,5]

Блок - схема:

Демонстрация в реальном времени:

См. Поиск и сортировка-алгоритм-упражнение-12 ручки от w3resource ( @ w3resource ) на CodePen .

Улучшите этот пример решения и опубликуйте свой код через Disqus

Предыдущий: Напишите программу на JavaScript для сортировки списка элементов с использованием сортировки Counting.
Далее: Напишите программу на JavaScript для сортировки списка элементов, используя сортировку по маслу.