Алгоритм поиска и сортировки JavaScript: сортировка по блину

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

script1adsense2code

script1adsense3code

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

Напишите программу на JavaScript для сортировки списка элементов, используя сортировку по маслу.

Сортировка блинов - разговорный термин для математической задачи сортировки неупорядоченной стопки блинов в порядке их размера, когда шпатель может быть вставлен в любую точку стопки и использован для переворачивания всех блинов над ней. Число блинов - это минимальное количество бросков, необходимое для данного количества блинов. Впервые эту проблему обсудил американский геометр Джейкоб Э. Гудман. Это разновидность проблемы сортировки, в которой единственной допустимой операцией является обращение элементов некоторого префикса последовательности в обратном порядке.

Демонстрация основной операции :

«JavaScript

Шпатель переворачивает три верхних блина, и результат виден ниже. В проблеме сгоревшего блина их верхние стороны теперь сгорали, а не нижние.

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

HTML-код:

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

Код JavaScript:

function pancake_sort(arr) {
    for (var i = arr.length - 1; i >= 1; i--) {
        // find the index of the largest element not yet sorted
        var max_idx = 0;
        var max = arr[0];
        for (var j = 1; j <= i; j++) {
            if (arr[j] > max) {
                max = arr[j];
                max_idx = j;
            }
        }
 
        if (max_idx == i) 
            continue; // element already in place
 
        var new_slice;
 
        // flip arr max element to index 0
        if (max_idx > 0) {
            new_slice = arr.slice(0, max_idx+1).reverse();
            for ( j = 0; j <= max_idx; j++) 
                arr[j] = new_slice[j];
        }
 
        // then flip the max element to its place
        new_slice = arr.slice(0, i+1).reverse();
        for ( j = 0; j <= i; j++) 
            arr[j] = new_slice[j];
    }
    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(pancake_sort(arra, 0, 5));

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

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

Блок-схема:

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

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

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

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