Вступ до сортування алгоритмів у JavaScript
Як і в більшості інших мов програмування, ви можете зіткнутися з сценаріями, де вам доведеться сортувати деякі числа в JavaScript за порядком зростання або зменшення. Для цього ми можемо використовувати багато алгоритмів, таких як сортування бульбашок, сортування вибору, сортування об'єднань, Quicksort тощо. Ці алгоритми відрізняються не лише тим, як вони працюють, але й у кожного є різні вимоги щодо пам’яті та часу, який ми потребуємо, давайте глибше заглибтесь у деякі важливі алгоритми сортування та подивіться, як ви можете використовувати їх у коді JavaScript.
Топ 6 алгоритмів сортування в JavaScript
Ось деякі алгоритми сортування в javascript, пояснені нижче з прикладами:
1. Алгоритм сортування бульбашок
Вважаючись одним із найпоширеніших інструментів цієї торгівлі, сортування Bubble працює, створюючи цикл, який порівнює кожен елемент у масиві з іншим елементом. Якщо порівняний предмет менший, ніж той, що знаходиться в руці, ми поміняємо місцями. Це триває, поки у нас не буде пропуску, де жоден елемент масиву не перевищує елемент, який знаходиться поруч.
Сортування бульбашок має O (n 2 ) часову складність та O (n) просторову складність.
Код:
function swap(arr, firstIndex, secondIndex)(
var temp = arr(firstIndex);
arr(firstIndex) = arr(secondIndex);
arr(secondIndex) = temp;
)
function bubbleSortAlgo(arraaytest)(
var len = arraaytest.length,
i, j, stop;
for (i=0; i < len; i++)(
for (j=0, stop=len-i; j < stop; j++)(
if (arraaytest(j) > arraaytest(j+1))(
swap(arraaytest, j, j+1);
)
)
)return arraaytest;
)
console.log(bubbleSortAlgo((3, 6, 2, 5, -75, 4, 1)));
Вихід:
2. Алгоритм вибору сортування
Тепер, коли ми закінчили обговорювати алгоритм сортування бульбашок, давайте розглянемо так само, як популярний алгоритм сортування під назвою Сортування виділення.
На відміну від сортування бульбашок, ми орієнтуємося на пошук найменшого значення в масиві, щоб виконати сортування. Ось покрокове розбиття того, як працює Сортування вибору:
- Ми вважаємо, що перший елемент у масиві є найменшим.
- Ми порівнюємо цей елемент із наступним елементом у масиві.
- Якщо наступний елемент менший, ніж під рукою, наступний елемент ми встановлюємо як нове найменше значення.
- Ми продовжуємо повторювати ці кроки, поки не досягнемо кінця масиву.
- Коли ми знаходимо значення в масиві, меншому, ніж той, з якого ми почали, ми поміняємо місцями свої позиції.
- Ми продовжуємо робити порівняння та переходимо до наступного пункту. Поки не буде відсортовано весь масив.
Так само, як алгоритм сортування міхурів, сортування вибору має O (n 2 ) часову складність та O (n) складність простору.
Код:
function SelectionSortAlgo(array, compare_Function) (
function comp(a, b) (
return a - b;
)
var min = 0;
var index = 0;
var temp = 0;
compare_Function = compare_Function || compare;
for (var i = 0; i < array.length; i += 1) (
index = i;
min = array(i);
for (var j = i + 1; j < array.length; j += 1) (
if (compare_Function(min, array(j)) > 0) (
min = array(j);
index = j;
)
)
temp = array(i);
array(i) = min;
array(index) = temp;
)
return array;
)
console.log(SelectionSortAlgo((9, 15, 2, 44, -1, 36, 1), function(a, b) ( return a - b; )));
Вихід:
3. Злиття алгоритму сортування
Подібно до сортування та вибору сортування бульбашок, сортування об'єднань - це один із популярних алгоритмів сортування в інформатиці, ви можете реалізувати його в більшості мов програмування, і він має хороші показники, не надто потребуючи в ресурсах.
Об'єднання Сортування використовує метод Ділення та підкорити для сортування масиву чи будь-якого списку елементів. Термін розділяє і перемагає означає, що ми розділимо одну велику проблему на кілька менших проблем, а потім вирішимо ці невеликі проблеми. Після вирішення менших проблем ми поєднуємо результати, які призводять до вирішення великої проблеми.
Розуміння алгоритму насправді просте:
- Ми поділимо заданий масив на n масивів, кожен з цих масивів містить всього 1 елемент.
- Об'єднайте масиви, щоб отримати новий масив.
- Повторіть крок 2, поки не залишиться лише 1 масив, який буде відсортованим масивом.
Код:
function merge_sort_algo(left, right)
(
var i = 0;
var j = 0;
var result = ();
while (i < left.length || j < right.length) (
if (i === left.length) (
// j is the only index left_part
result.push(right(j));
j++;
)
else if (j === right.length || left(i) <= right(j)) (
result.push(left(i));
i++;
) else (
result.push(right(j));
j++;
)
)
return result;
)
console.log(merge_sort_algo((1, 44, 6), (84, 7, 5)));
Вихід:
4. Алгоритм швидкого сортування
Quicksort - це один із найефективніших способів сортування елементів у комп'ютерних системах. Similor для злиття сорту, Quicksort працює над алгоритмом ділення та підкорення. У цьому випадку ми знаходимо елемент зведення в масиві для порівняння всіх інших масивів елементів проти, а потім переміщуємо елементи таким чином, що всі елементи перед нашими вибраними елементами зведення є меншими, а всі елементи після пункту зведення мають більші розміри. Після того, як ми зробимо це, головне - продовжувати робити це неодноразово, і ми матимемо відсортований масив.
Нижче наведено кроки, які можна виконати для впровадження алгоритму швидкості:
- Ми вибираємо елемент масиву і називаємо його "Pivot Point"
- Ми починаємо вказівник, званий лівим вказівником, з якого знаходиться на першому елементі масиву.
- Аналогічно ми запускаємо вказівник, який називається правильним вказівником, на останньому елементі масиву.
- Якщо значення елемента в лівому вказівнику менше порівняно з обраною точкою зведення, переміщуємо лівий вказівник вліво (додаємо +1 до нього) і продовжуємо повторювати його, поки значення лівого вказівника не виявиться більшим, ніж значення значення точки повороту або дорівнює їй.
- Якщо значення елемента в правому вказівнику в списку вище, ніж значення елемента зведення, ми направляємо правий вказівник наліво. Повторіть це, поки значення правого бічного вказівника не буде нижчим (або рівним) значенням повороту.
- Коли значення лівого вказівника менше або дорівнює значенню правого вказівника, поміняйте місцями значення.
- Перемістіть правий вказівник наліво на один, лівий вказівник праворуч на один.
- Повторюйте, доки лівий і правий покажчики не зустрінуться.
Код:
function quickSortAlgo(origArray) (
if (origArray.length <= 1) (
return origArray;
) else (
var left = ();
var right = ();
var newArray = ();
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) (
if (origArray(i) <= pivot) (
left.push(origArray(i));
) else (
right.push(origArray(i));
)
)
return newArray.concat(quickSortAlgo(left), pivot, quickSortAlgo(right));
)
)
var myArray = (13, 50, 2, 45, -1, 74, 11 );
var arreySorted = quickSortAlgo(myArray);
console.log(arreySorted);
Вихід:
5. Алгоритм сортування вставки
Що стосується простоти реалізації, сортування вставки широко відоме як один із простих алгоритмів. У сортуванні вставки елементи масиву порівнюються між собою та потім розташовуються в певному порядку. Це дуже схоже на упорядкування карт в колоду. Сортування вставки імен походить від процесу вибору елемента та вставки його в правильному місці, а потім повторення для всіх елементів.
Ось як працює алгоритм:
- Перший елемент масиву вважається вже відсортованим.
- Виберіть наступний елемент масиву.
- Порівняйте вибраний елемент з усіма елементами масиву.
- Зсуньте кожен елемент масиву, який перевищує значення вибраного елемента.
- Вставте елемент
- Повторіть крок 2 - 5, поки масив не буде відсортований.
Код:
function insertion_Sort_algo(arr)
(
for (var i = 1; i < arr.length; i++)
(
if (arr(i) < arr(0))
(
arr.unshift(arr.splice(i, 1)(0));
)
else if (arr(i) > arr(i-1))
(
continue;
)
else (
for (var j = 1; j < i; j++) (
if (arr(i) > arr(j-1) && arr(i) < arr(j))
(
arr.splice(j, 0, arr.splice(i, 1)(0));
)
)
)
)
return arr;
)
console.log(insertion_Sort_algo((44, 20, 26, 54, -9, 41, 16)));
Вихід:
6. Алгоритм сортування купи
Сортування в купі - це спосіб сортування елементів за допомогою структури даних “Heap”. Метод досить схожий на техніку відбору сортування, про яку ми говорили раніше. Тепер ви можете задатися питанням про Heaps та як вони визначаються, перш ніж перейти до алгоритму, давайте розберемося спочатку в купи.
У двох словах, купа - це бінарне дерево з деякими доданими правилами. Одне правило говорить, що в купі дерево повинно бути повним двійковим деревом, що просто означає, що потрібно заповнити всі вузли на поточному рівні, перш ніж додавати ще один. Наступне правило для купи - це те, що повинні бути визначені стосунки дитини та батьків із значеннями елементів кучі.
У мін-купі значення батьків має бути меншим, ніж його діти. Як можна здогадатися, у максимальній купі значення батьків має бути більшим, ніж його дочірня.
Тепер, коли визначення не вдається, давайте подивимось, як працює цілий кусок:
- Спочатку ми будуємо максимальну купу, яка гарантує, що елемент найвищого значення знаходиться вгорі.
- Перемикаємо верхній елемент з останнім елементом купи і виймаємо верхній елемент з купи і зберігаємо його на відсортованому масиві.
- Ми постійно повторюємо крок перший і другий, поки в купі не залишиться лише один елемент.
Одне, що слід пам’ятати, - це те, що Heaps не підтримується в JavaScript, тому ми повинні вдаватися до впровадження Heaps за допомогою масивів. Складність простору сортування купи - це O (1), що є чудовим, і хоча це трохи складніше порівняно зі сортуванням з’єднання або сортуванням вставлення, коли мова йде про розуміння та реалізацію, я думаю, що для переваг продуктивності, це в кінцевому підсумку краще використовувати в великі проекти.
Код:
var arrLength;
function heapRoot(input, i) (
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
if (left input(max)) (
max = left;
)
if (right input(max)) (
max = right;
)
if (max != i) (
swap(input, i, max);
heapRoot(input, max);
)
)
function swap(input, index_A, index_B) (
var temp = input(index_A);
input(index_A) = input(index_B);
input(index_B) = temp;
)
function heapSortAlgo(input) (
arrLength = input.length;
for (var i = Math.floor(arrLength / 2); i >= 0; i -= 1) (
heapRoot(input, i);
)
for (i = input.length - 1; i > 0; i--) (
swap(input, 0, i);
arrLength--;
heapRoot(input, 0);
)
)
var arr = (12, 10, 22, 55, -8, 64, 14);
heapSortAlgo(arr);
console.log(arr);
Вихід:
Висновок
Сортування - важлива частина створення програм та веб-сайтів із JavaScript. Тепер, коли ви знайомі з деякими найважливішими алгоритмами, щоб виконати роботу, ви повинні відчувати себе впевненіше у розробці JS.
Одним важливим фактом, який слід пам’ятати про різні сортування, є те, що вам не потрібно занадто сильно наголошувати на тому, який алгоритм використовувати у більшості випадків. Тепер, коли апаратне забезпечення комп’ютера настільки потужне, сучасні процесори для телефонів і настільних ПК не будуть порушувати потужність у сортуванні навіть сотень елементів за кілька мілісекунд. Це лише ті випадки, коли ви застрягли з повільним обладнанням або ситуаціями, коли ви оптимізуєте кожен окремий розділ коду, де зміна алгоритмів сортування може бути корисною.
Рекомендовані статті
Це посібник зі сортування алгоритмів у JavaScript. Тут ми обговорюємо 6 найкращих алгоритмів сортування в JavaScript разом із прикладами та реалізацією коду. Ви також можете переглянути наступні статті, щоб дізнатися більше -
- Компілятори JavaScript
- Зворотний бік JavaScript
- Вступ до JavaScript
- Квадрати на Яві
- Швидке сортування алгоритмів на Java
- Масиви в структурі даних
- Алгоритм C ++ | Приклади алгоритму С ++