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

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

script1adsense2code

script1adsense3code

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

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

Расческа - это разновидность пузырчатой сортировки. Подобно сортировке «Шелл», сортировка «Гребень» увеличивает разрыв, используемый в сравнениях и обменах. Некоторые реализации используют сортировку вставкой, когда зазор меньше определенной величины. Основная идея состоит в том, чтобы исключить черепах или небольшие значения в конце списка, поскольку в пузырьковой сортировке они значительно замедляют сортировку. Кролики, большие значения в начале списка, не представляют проблемы в пузырьковой сортировке.
В пузырьковой сортировке, когда сравниваются любые два элемента, они всегда имеют разрыв 1. Основная идея гребенчатой сортировки состоит в том, что разрыв может быть намного больше 1.

Визуализация гребенчатой сортировки:

Анимационные кредиты: Jerejesse

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

HTML-код:

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

Код JavaScript:

function combsort(arr)
{
 function is_array_sorted(arr) {
      var sorted = true;
      for (var i = 0; i < arr.length - 1; i++) {
          if (arr[i] > arr[i + 1]) {
              sorted = false;
              break;
          }
      }
      return sorted;
  }
 
  var iteration_count = 0;
  var gap = arr.length - 2;
  var decrease_factor = 1.25;
 
  // Repeat iterations Until array is not sorted
  
  while (!is_array_sorted(arr)) 
  {
      // If not first gap  Calculate gap
      if (iteration_count > 0)
         gap = (gap == 1) ? gap : Math.floor(gap / decrease_factor);
 
  // Set front and back elements and increment to a gap
      var front = 0;
      var back = gap;
      while (back <= arr.length - 1) 
      {
          // Swap the elements if they are not ordered
        
          if (arr[front] > arr[back])
          {
              var temp = arr[front];
              arr[front] = arr[back];
              arr[back] = temp;
          }
 
          // Increment and re-run swapping
        
          front += 1;
          back += 1;
      }
      iteration_count += 1;
  }
  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(combsort(arra));

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

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

Блок - схема:

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

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

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

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