Вступ до сортування об'єднань у JavaScript
Алгоритми сортування дуже важливі в інформатиці. Вихід сортування полягає в упорядкуванні елементів списку в певному порядку (або за зростанням, або за спаданням). Об'єднання Сортування в JavaScript - це один із найефективніших алгоритмів сортування, який базується на концепції ділення та перемог. Як випливає з назви, спочатку розділіть більшу проблему на невеликі проблеми, ніж вирішіть менші проблеми, щоб вирішити більшу проблему. Концептуально сортування об'єднань - це поєднання двох основних алгоритмів, які називаються MERGE та MERGE_SORT.
яка працює наступним чином:
- Розподіліть несортований список на n кількість однопозиційних підсписів (n - загальна кількість елементів у несортованому списку).
- Неодноразово об’єднуючи підлистики в упорядковані списки, поки не буде лише одного відсортованого списку.
Реалізація сортування об'єднань у JavaScript
Алгоритм MERGE дотримується процедури поєднання двох відсортованих списків до одного відсортованого списку.
Приклад: Припустимо, є два списки, тобто список 1 (1, 5, 3) та список 2 (7, 2, 9).
1. Спочатку сортуйте обидва списки.
Тепер ми побачимо і застосуємо на ньому техніку Е.
2. Тоді ми створимо новий список розміром x + y, де x - кількість елементів у Переліку 1, а y - кількість елементів у Списку 2.
У нашому випадку x = 3 і y = 3, тому x + y = 6.
3. Тепер у нас є два покажчики.
Перший вказівник, що вказує на першу позицію Списку 1, і Другий вказівник, що вказує на першу позицію Списку 2.
4. Тоді ми порівняємо значення обох покажчиків. Вказівник із меншим значенням скопіюйте цей елемент у Список 3 та перемістіть вказівник праворуч від списку із меншим значенням та списком, що виходить із ним (тобто Список 1 та Список 3)
5. Аналогічно виконуйте крок 4 знову і знову.
Подальше подорож… ..
Примітка . Якщо один із списків (тобто список 1 або список 2) повністю пройде, як у випадку, скопіюйте весь вміст іншого списку з вказівника на список результатів (тобто список 3) наступним чином.
Псевдокод
Function merge (sublist1, sublist2) (
Create var for result list
While sublist1 length > 0 and sublist2 length > 0
If sublist1(0) < sublist2(0) Copy the sublist1 pointer value to result list and Shift pointer of sublist1 to right
else
Copy the sublist2 pointer value to result list and Shift pointer of sublist2 to right
Return concat sublist1 or sublist2 (depending if node1 is empty or not)
Алгоритм MERGE_SORT ділить заданий несортований список на мінімальний розмір, а потім викликає алгоритм MERGE для об'єднання списку в новий відсортований список.
Псевдокод
function mergeSort(list) (
If list length < 2
Return list
Create var for middle index of list
Create var for left index of list
Create var for right index of list
Recursively call mergeSort function
)
Приклад
Тут ми слідкуємо за реалізацією Сортування вгорі-вниз. Він починається вгорі і продовжується вниз, з кожним рекурсивним поворотом задаючи одне і те ж питання "Що потрібно зробити для сортування списку?", І відповідь: "Розбийте список на два, зробіть рекурсивний дзвінок і об'єднайте результати ».
Код у Javascript
// Split the list into halves and merge them recursively
function mergeSort (list) (
if (list.length < 2) (
return list;// return once we hit a list with a single element
)
var mid = Math.floor(list.length / 2);
var left = mergeSort(list.slice(0, mid));
var right = mergeSort(list.slice(mid));
return merge(left, right);
)
// compare the lists element by element and return the concatenated resultList
function merge (sublist1, sublist2) (
var resultList = ();
while (sublist1.length > 0 && sublist2.length > 0)
resultList.push(sublist1(0) < sublist2(0)? sublist1.shift() : sublist2.shift());
return resultList.concat(sublist1.length? sublist1 : sublist2);
)
const list = (6, 5, 3, 1, 8, 7, 2, 4, 2, 5, 1, 2, 3) console.log(mergeSort(list)) //( 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8 )
Основна функція сортування злиття розділить даний список на менші списки в кожній ітерації рекурсивного виклику. Не забувайте, що для рекурсії необхідна базова умова, щоб уникнути нескінченної рекурсії. У нашому випадку ми маємо:
if (list.length < 2) (
return list;// return once we hit a list with a single element
)
Після того, як ми встановимо базову умову для рекурсії, тоді ми визначимо середній індекс, щоб розділити даний список на лівий і правий підсписи, як ви бачите вище на прикладі діаграми. Тоді нам потрібно об'єднати лівий підсклад і правий підсклад, який ми розглянемо зараз. У функції злиття, наведеної вище, нам потрібно переконатися, що ми сортуємо всі елементи з лівого підсписку та правого підзапису- список. Як ми це зробимо, використовуючи цикл while. Протягом циклу while ми порівнюємо один з одним елемент у лівому підсписі та елемент у правому підсписі. Ми можемо натиснути менший з двох у список результатів і відповідно перемістити курсор лівого підпростору та правого підсписку. Нарешті, нам потрібно об'єднати список результатів. Це дуже важливо! Якщо ми не зробимо цього останнього кроку тут, у нас буде неповний список елементів у кінці, оскільки умова циклу while вийде з ладу, коли будь-який із двох покажчиків досягне кінця.
Вихід:
Властивості сортування об'єднань
- Сортування сортування є стабільним, оскільки один і той же елемент у масиві зберігає свої вихідні положення відносно один одного.
- Сортування сортування не стоїть на місці, оскільки під час об’єднання створюється копія всього списку. Завдяки цьому складність простору (O (n)) цього алгоритму насправді більша, ніж інші, і не повинна використовуватися в складних задачах, де простір є преміальним.
- Загальна часова складність сортування злиття становить O (nLogn). Це більш ефективно, як і в гіршому випадку, також час виконання - O (nlogn).
Висновок
Найкращі сортування злиття, найгірші та середні показники часу складності однакові, що робить його більш ефективним алгоритмом. Це працює швидше, ніж інші методи сортування. Сортування сортування може бути застосоване до файлів будь-якого розміру. Це дуже паралельно завдяки використанню методу ділення та перемоги. Для того, щоб виробити міцні основи інформатики, вам рекомендується ретельно розібратися в різних алгоритмах сортування.
Рекомендована стаття
Це керівництво по об'єднанню сортування в JavaScript. Тут ми обговорюємо Вступ до сортування об'єднань у JavaScript та реалізацію разом із властивостями. Ви також можете ознайомитися з іншими запропонованими нами статтями, щоб дізнатися більше -
- Функції JavaScript математики
- Вступ до JavaScript
- Найкращі рамки Javascript
- Інструменти JavaScript
- Топ-6 алгоритмів сортування в JavaScript