#c #algorithm #sorting #mergesort
#c #алгоритм #сортировка #сортировка слиянием
Вопрос:
Я пытаюсь выполнить сортировку слиянием более ПРОСТЫМ СПОСОБОМ, но не получаю желаемого результата. Он показывает мне, что какой-то цикл повторяется бесконечно. Кто-нибудь поможет мне найти, где ошибка в коде?
#include <bits/stdc .h>
void merge(int arr[], int, int, int);
void mergesort(int arr[], int, int);
using namespace std;
int main() {
int n, m;
cin >> n;
int arr[n];
for (int i = 0; i < n; i )
cin >> arr[i];
mergesort(arr, 0, n);
for (int i = 0; i < n; i )
cout << arr[i] << " ";
}
void merge(int arr[], int l, int mid, int h) {
int i = l, j = mid, k = 0;
int brr[h - l];
while (i < mid amp;amp; j < h) {
if (arr[i] <= arr[j])
brr[k ] = arr[i ];
else
brr[k ] = arr[j ];
}
for(; i < mid; i )
brr[k ] = arr[i];
for(; j < h; j )
brr[k ] = arr[j];
int i = 0;
for(k = l; k < h; k )
arr[k] = brr[i ];
}
void mergesort(int arr[], int l, int h) {
if (l < h) {
int mid = l (h - l) / 2;
mergesort(arr, l, mid);
mergesort(arr, mid, h);
merge(arr, l, mid, h);
}
}
Комментарии:
1. Что именно «это» показывает вам? Пожалуйста, опубликуйте полный вывод
2. Он показывает mergesort.exe перестал работать, когда я использую инструмент отладки, я обнаруживаю, что функция сортировки слиянием выполняется бесконечно,
3. Сделайте это
if(l 1 < h)или, возможно, более четко,if (h - l > 1). Вы продолжаете сортировать одноэлементные подпоследовательности бесконечно.4. Вы будете рады услышать, что вам не нужна ничья помощь, чтобы разобраться в этом, просто инструмент, который у вас уже есть: ваш отладчик! Это именно то, для чего нужен отладчик. Он запускает вашу программу по одной строке за раз и показывает вам, что происходит. Знание того, как использовать отладчик, является необходимым навыком для каждого разработчика C , без исключений. С помощью вашего отладчика вы сможете быстро найти все ошибки в этой и всех будущих программах, которые вы пишете, не обращаясь ни к кому за помощью. Вы уже пробовали использовать свой отладчик? Если нет, то почему бы и нет? Что вам показал ваш отладчик?
5. Спасибо @IgorTandetnik создание if(l 1
Ответ №1:
Алгоритм верен, за исключением теста в mergesort : if (l < h) должно быть if (h - l >= 2)
Тест l < h используется в when h является индексом последнего элемента в срезе. В C и C гораздо проще и более идиоматично считать h исключенную верхнюю границу. Следовательно, минимальный фрагмент для разделения mergesort должен иметь длину не менее 2 : h - l >= 2 .
Обратите внимание, что выделение массивов как VLA рискованно для больших массивов: это может вызвать переполнение стека. C не поддерживает VLA (массивы переменной длины, т. Е. Автоматические массивы, Размер которых не является выражением времени компиляции), ваш компилятор поддерживает их как расширение.
Обратите также внимание, что последний for цикл в merge можно опустить, поскольку элементы, которые он копирует, уже находятся в правильном положении.
Вот модифицированная версия:
#include <bits/stdc .h>
void merge(int arr[], int, int, int);
void mergesort(int arr[], int, int);
using namespace std;
int main() {
int n, m;
cin >> n;
int arr[n];
for (int i = 0; i < n; i )
cin >> arr[i];
mergesort(arr, 0, n);
for (int i = 0; i < n; i )
cout << arr[i] << " ";
cout << endl;
return 0;
}
void merge(int arr[], int l, int mid, int h) {
int i = l, j = mid, k = 0;
int brr[h - l];
while (i < mid amp;amp; j < h) {
if (arr[i] <= arr[j])
brr[k ] = arr[i ];
else
brr[k ] = arr[j ];
}
for(; i < mid; i )
brr[k ] = arr[i];
for(i = 0, k = l; k < j; k , i )
arr[k] = brr[i];
}
void mergesort(int arr[], int l, int h) {
if (h - l >= 2) {
int mid = l (h - l) / 2;
mergesort(arr, l, mid);
mergesort(arr, mid, h);
merge(arr, l, mid, h);
}
}