В чем суть данной реализации сортировки слиянием? (Интересует сама функция merging)

181

25 апреля 2018, 06:53

Добрый день всем кто читает! Возник вопрос с пониманием самого слияния в сортировке слиянием, каким образом это происходит в данном примере кода, и за что отвечает каждый цикл while и for.

Непонятен этот кусок:

void merging(int *firstMas, int *secondMas, int low, int mid, int high) {
int l1, l2, i;
for (l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
    if (firstMas[l1] <= firstMas[l2])
        secondMas[i] = firstMas[l1++];
    else
        secondMas[i] = firstMas[l2++];
}
while (l1 <= mid)
    secondMas[i++] = firstMas[l1++];
while (l2 <= high)
    secondMas[i++] = firstMas[l2++];
for (i = low; i <= high; i++)
    firstMas[i] = secondMas[i];
}

Вызов идет отсюда:

void merge_sort(int *firstMas, int *secondMas, int low, int high) {
int mid;
if (low < high) {
    mid = (low + high) / 2;
    merge_sort(firstMas, secondMas, low, mid);
    merge_sort(firstMas, secondMas, mid + 1, high);
    merging(firstMas, secondMas, low, mid, high);
}
else {
    return;
}
}

Еще раз повторюсь, что хотелось бы пояснение по внутреннему устройству merging, а именно за какие случаи отвечают форы и вайлы.

Благодарю заранее за помощь!!

Answer 1

В первом цикле for

for (l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
    if (firstMas[l1] <= firstMas[l2])
        secondMas[i] = firstMas[l1++];
    else
        secondMas[i] = firstMas[l2++];
}

происходит сортировка значений из первого массива с последующей записью их во второй массив. Тобишь, если левое число меньше правого, то переписывается левое, иначе - правое. Следующие за for циклы while необходимы для того, чтобы, если цикл for закончился раньше, чем были переписаны все цифры, все оставшиеся были переписаны во второй массив автоматом, так как в сортировке уже не нуждаются (нет относительно чего сортировать, так как один из отрезков: до середины или после - уже закончился).

Последний же цикл for просто переписывает отсортированные значения из второго в первый массив. Кстати, не совсем понятно зачем изначально передается два массива, т.к. второй массив не несет полезной информации, которая могла бы быть использована за пределами ф-ции сортировки. Это просто буфер. Можно избавится от него в определении ф-ции и просто добавить динамическое выделение необходимой памяти под второй массив прямо в ф-ции.

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Сокеты QT(QTSocket)

Как обращаться на прямую к компьютерю подключенного к серверу по tcpsocket, как реализовать авторизацию пользователя, логины и пароли хранятся...

188

c++

Как добавить окно(QWidget) в модуль?

При разборе очередного модуля нужно добавить UI-интерфейс для добавления нужных элементовМожете что посоветовать? Спасибо

207

c++

Передача информации с Combobox

Мне нужно передавать информацию(1) (что я выбрал в комбобоксе в свою функцию) а потом результат функции записываю в Edit (2)Но почемуто не записывается...

217

c++

Добавить классы в массив

У меня есть куча классовЯ в цикле хочу создать объект каждого класса и вызвать у него определенный метод

165