Добрый день всем кто читает! Возник вопрос с пониманием самого слияния в сортировке слиянием, каким образом это происходит в данном примере кода, и за что отвечает каждый цикл 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, а именно за какие случаи отвечают форы и вайлы.
Благодарю заранее за помощь!!
В первом цикле 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 просто переписывает отсортированные значения из второго в первый массив. Кстати, не совсем понятно зачем изначально передается два массива, т.к. второй массив не несет полезной информации, которая могла бы быть использована за пределами ф-ции сортировки. Это просто буфер. Можно избавится от него в определении ф-ции и просто добавить динамическое выделение необходимой памяти под второй массив прямо в ф-ции.
Сборка персонального компьютера от Artline: умный выбор для современных пользователей