Комментарии 11
Мягко говоря, данное описание сортировки слиянием воспринимается гораздо хуже, чем «академическое».
Я не программист, но разве с самого начала не очевидно, что надо сравнивать первые элементы массивов, брать наименьший, сдвигать индекс на 1 и снова сравнивать? Без всяких буферов. Со стеками проще — там просто верхние элементы сравниваются.
А момент с разбиением массивов пополам напомнил qsort.
А момент с разбиением массивов пополам напомнил qsort.
Типичный для новичка переусложнённый велосипед. Слияние двух отсортированных массивов производится простейшим кодом (вариант далеко не самый эффективный, но даже он будет работать быстрее, чем Ваш):
И кто Вам сказал такую глупость, что делить надо, пока не останется 2 элемента (а тем более, один)? Деление до минимального размера имеет смысл только для сортировки списков с последовательным доступом к элементам. Массивы же надо делить ровно до того момента, когда размер блока станет достаточно маленьким, чтобы применить эффективный алгоритм сортировки с прямым доступом к элементам. Да и само использование сортировки слиянием для массивов, полностью помещающихся а памяти — это демонстрация полного непонимания данного алгоритма в частности и полного же незнания даже минимальных основ теории алгоритмов в целом.
int i=0, j=0, k=0;
while(i < a1.length && j < a2.length) {
a3[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++];
}
if(i< a1.length) {
arraycopy(a1, i, a3, k, a1.length - i);
} else if(j< a2.length) {
arraycopy(a2, j, a3, k, a2.length - j);
}
И кто Вам сказал такую глупость, что делить надо, пока не останется 2 элемента (а тем более, один)? Деление до минимального размера имеет смысл только для сортировки списков с последовательным доступом к элементам. Массивы же надо делить ровно до того момента, когда размер блока станет достаточно маленьким, чтобы применить эффективный алгоритм сортировки с прямым доступом к элементам. Да и само использование сортировки слиянием для массивов, полностью помещающихся а памяти — это демонстрация полного непонимания данного алгоритма в частности и полного же незнания даже минимальных основ теории алгоритмов в целом.
Сортировка слиянием — это не эффективный алгоритм сортировки? Почему его нельзя использовать для массивов?
Сортировка слиянием — очень эффективный алгоритм внешней сортировки. Разумеется, как любой алгоритм сложности O(n*ln(n)), он будет эффективен и для сортировки массивов… Но зачем, когда для массивов есть множество более эффективных алгоритмов внутренней сортировки?
Надо понимать, что для разных данных надо использовать разные алгоритмы.
Для массива из 10 чисел простейший, но имеющий минимальные накладные расходы, алгоритм сложности O(n^2) будет эффективнее, чем быстрый алгоритм сложности O(n*ln(n)): чем меньше объём данных, тем заметнее накладные расходы, требуемые для быстрых алгоритмов.
Для массива из 10 тысяч строк уже понадобится алгоритм сложности O(n*ln(n)). Но опять же, выбор алгоритма зависит от сортируемых данных и наличия ресурсов. Например, пирамидальная сортировка в среднем медленнее, чем быстрая, но если требуется минимизировать затраты памяти (например, в микроконтроллере), то эффективнее будет именно пирамидальная. А уж сортировка слиянием в задачах, требующих минимизации памяти, вообще не рассматривается.
А для линейного однонаправленного списка, или для файла, размер которого превышает объём RAM (вполне себе типичная ситуация для баз данных), будет использован один из алгоритмов внешней сортировки. В том числе и сортировка слиянием.
Надо понимать, что для разных данных надо использовать разные алгоритмы.
Для массива из 10 чисел простейший, но имеющий минимальные накладные расходы, алгоритм сложности O(n^2) будет эффективнее, чем быстрый алгоритм сложности O(n*ln(n)): чем меньше объём данных, тем заметнее накладные расходы, требуемые для быстрых алгоритмов.
Для массива из 10 тысяч строк уже понадобится алгоритм сложности O(n*ln(n)). Но опять же, выбор алгоритма зависит от сортируемых данных и наличия ресурсов. Например, пирамидальная сортировка в среднем медленнее, чем быстрая, но если требуется минимизировать затраты памяти (например, в микроконтроллере), то эффективнее будет именно пирамидальная. А уж сортировка слиянием в задачах, требующих минимизации памяти, вообще не рассматривается.
А для линейного однонаправленного списка, или для файла, размер которого превышает объём RAM (вполне себе типичная ситуация для баз данных), будет использован один из алгоритмов внешней сортировки. В том числе и сортировка слиянием.
на пальцах сортировка слиянием отлично описана в википедии, в виде гифки.
в данной же статье я потерял мысль на фтором параграфе.
в данной же статье я потерял мысль на фтором параграфе.
Ваше «начали за здравие» это вообще не слияние, а простое запихивание элементов по очереди.
Правильное слияние:
Шаг 1.
Взять по элементу из обоих массивов.
Шаг 2.
Поместить больший элемент в результирующий массив
Шаг 3.
Попытаться взять следующий элемент из того массива, из которого мы на Шаге 2 поместили элемент в результирующий массив.
Еще остались элементы? Перейти к Шагу 2
Элементы закончились? Добавить все оставшиеся элементы второго массива(где они еще есть) в конец результирующего.
Шаг 4.
Конец
Правильное слияние:
Шаг 1.
Взять по элементу из обоих массивов.
Шаг 2.
Поместить больший элемент в результирующий массив
Шаг 3.
Попытаться взять следующий элемент из того массива, из которого мы на Шаге 2 поместили элемент в результирующий массив.
Еще остались элементы? Перейти к Шагу 2
Элементы закончились? Добавить все оставшиеся элементы второго массива(где они еще есть) в конец результирующего.
Шаг 4.
Конец
Мне сложно представить более сложный способ объяснить сортировку слиянием, чем тот, что использовался в статье:) Однако, не могу не отметить, что статья из песочницы. Человек пробует публиковать свои мысли и это прекрасно. Редко у кого первая статья бывает шедевром по содержанию. Всё приходит с опытом.
Автор молодец, что всё аккуратно оформил. Успехов в изучении програмирования!
Автор молодец, что всё аккуратно оформил. Успехов в изучении програмирования!
Написал тотже самый код. У меня через по-другому.
1. Нам потребуется процедура copyArray(sourceArray, sourceStartPosition, destinationArray, destinationStartPosition) — замечу что копирование происходит фрагмента [sourceStartPosition; sourceArray.length — 1] в позиции [destinationStart; destinationStart + lengthOfSourceFragment — 1].
2. Код процедуры слияния
narray, murray — входные массейвы
rarray — выходной
narray — 0..n-1, length = n, i — indexer
murray — 0..m-1, length = m, k — indexer
rarray — 0..n+m-1, length = n+m, l — indexer
i, k, l = 0;
while ( i < n or k < m) {
x = narray[i];
y = murray[k];
if (x <= y) {
rarray[l] = x;
i++;
}
else {
rarray[l] = y;
k++;
}
l++;
}
if i = n-1 then copyArray(murray, k, rarray, l+1)
if k = m-1 then copyArray(narray, i, rarray, l+1)
1. Нам потребуется процедура copyArray(sourceArray, sourceStartPosition, destinationArray, destinationStartPosition) — замечу что копирование происходит фрагмента [sourceStartPosition; sourceArray.length — 1] в позиции [destinationStart; destinationStart + lengthOfSourceFragment — 1].
2. Код процедуры слияния
narray, murray — входные массейвы
rarray — выходной
narray — 0..n-1, length = n, i — indexer
murray — 0..m-1, length = m, k — indexer
rarray — 0..n+m-1, length = n+m, l — indexer
i, k, l = 0;
while ( i < n or k < m) {
x = narray[i];
y = murray[k];
if (x <= y) {
rarray[l] = x;
i++;
}
else {
rarray[l] = y;
k++;
}
l++;
}
if i = n-1 then copyArray(murray, k, rarray, l+1)
if k = m-1 then copyArray(narray, i, rarray, l+1)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сортировка слиянием по-простому