Последние новости:

Поиск по сайту:

Вслед за автором мудрого речения идет тот, кто впервые его процитировал (Р. Эмерсон).

Как работает алгоритм сортировки слияния

09.11.2018
Как работает алгоритм сортировки слияния

Алгоритм сортировки слиянием был изобретен Джоном фон Нейманом в 1945 году. Это эффективный алгоритм, используется подход разделяй и властвуй.

  1. Сортировка слиянием несколько раз делит массив на более мелкие куски, до тех пор, пока мы больше не сможем разделить массив на куски.
  2. Он повторно объединяет фрагменты массива для получения отсортированного массива.

Пример: [3,4,2,1]

1. Во-первых, мы должны разделить массив на более мелкие куски.

left  [ 3 , 4 ]     right [ 2, 1 ]
[ 3 ] [ 4 ]      [ 2 ] [ 1]

 

2. Мы должны объединить меньшие куски, чтобы получить сортированный массив. Сравниваем 3 и 4 они уже отсортированы, в следующем 2 и 1 поставить 1первый на место второго.

left   [ 3 , 4 ]     right [ 2, 1 ]
[ 3 ]  [ 4 ]      [ 2 ] [ 1]
[3, 4 ]          [1 ,2 ]

Теперь сравните индекс левой части 0 и индекс правой части 0, которые являются 3 и 1.

где 1 меньше 3, поэтому мы удаляем 1 из правой части и помещаем в сортированный список.

left  [ 3 , 4 ]     right [ 1, 2 ]
[ 3]  [ 4 ]      [ 2 ] [ 1]
[3, 4 ]          [ 2 ]
sorted array  [ 1 ]

 

Снова проверяем 3 и 2 и удаляем 2 из правой части и добавляем в сортированный список

left  [ 3 , 4 ]     right [ 1, 2 ]
[ 3]  [ 4 ]      [ 2 ] [ 1]
[3, 4 ]           [  ]
sorted array  [ 1 ,2 ]

 

Теперь добавьте левую и правую части с отсортированным списком.

left  [ 3 , 4 ]     right [ 1, 2 ]
[ 3]  [ 4 ]      [ 2 ] [ 1]
[3, 4 ]           [  ]
sorted array  [ 1 ,2 ,3, 4]

 

Давайте реализуем алгоритм сортировки слиянием

function mergeSort(array,half = array.length/2){
if(array.length < 2){
    return array  // это значит, что мы больше не делим массив
                  // на более мелкие куски
  }
const left = array.splice( 0,half ); //левая часть массива
return merger( mergeSort( left ),mergeSort( array ) )
}

 

В приведенном выше коде мы используем метод splice, который удаляет левую часть массива, так что оставшаяся часть массива является правой.

Далее нам нужно написать функцию слияния, которая поможет нам объединить левую и правую часть массива и вернет отсортированный список.

function merger(left, right) {
    const arr = [  ];
    while (left.length && right.length) {
        if (left[ 0 ] < right[ 0 ]) { 
            arr.push( left.shift( ) ) 
        } else {
            arr.push( right.shift(  ) ) 
        }
    }
    return [ ...arr, ...left, ...right ]; 
}

 

Итого

conlole.log(mergeSort([10, 5, 3, 8, 2, 6, 4, 1, 7, 9]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...
Поделиться в соц. сетях:
0 0 голоса
Рейтинг статьи
Подписаться
Уведомить о
guest

**ссылки nofollow

0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии

Читайте также

Статьи партнеров:

0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам:

Заполните форму и наш менеджер перезвонит Вам в самое ближайшее время!

badge
Обратный звонок 1
Отправить

Спасибо! Ваша заявка принята

close

Спасибо! Ваша заявка принята

close