Как посчитать количество обменов и сравнений при сортировке слиянием? - C (СИ)
Формулировка задачи:
Дан массив: 33 66 82 85 15 17 74
слияние происходит насколько я погимаю так:
66 33 85 82 17 15 74
85 82 66 33 74 17 15
85 82 74 66 33 17 15
Но как подсчитать кол-во обменов и сравнений,я не понимаю
Решение задачи: «Как посчитать количество обменов и сравнений при сортировке слиянием?»
textual
Листинг программы
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int temp[7], cpy = 0, cmp = 0;
void merge(int *array, int l, int q, int r) {
int pl = l, pr = q + 1, i = 0, size = r - l + 1, active = 1;
while (active)
if (array[pl] > array[pr]) {
temp[i] = array[pl];
cpy++;
i++;
pl++;
if (pl > q) {
while (pr <= r) {
temp[i] = array[pr];
cpy++;
i++;
pr++;
}
active = 0;
}
cmp++;
}
else {
temp[i] = array[pr];
cpy++;
i++;
pr++;
if (pr > r) {
while (pl <= q) {
temp[i] = array[pl];
cpy++;
i++;
pl++;
}
active = 0;
}
cmp++;
}
memcpy(&array[l], &temp[0], (r - l + 1) * sizeof(int));
cpy++;
}
void mergesort(int *array, int l, int r) {
int q;
if (l < r) {
q = (l + r) / 2;
mergesort(array, l, q);
mergesort(array, q + 1, r);
merge(array, l, q, r);
}
}
int main(int argc, char **argv) {
int array[] = { 33, 66, 82, 85, 15, 17, 74 }, n = sizeof(array) / sizeof(int);
printf("Trying to sort an array: ");
for (int i = 0; i < 7; i++) {
printf("%d ", array[i]);
}
printf("\n\n");
mergesort(array, 0, n - 1);
printf("Comparisons: %d\n", cmp);
printf("Copy Operations: %d\n\n", cpy);
printf("The sorted array: ");
for (int i = 0; i < 7; i++) {
printf("%d ", array[i]);
}
printf("\n");
return EXIT_SUCCESS;
}
Объяснение кода листинга программы
- Создается массив temp для временного хранения данных во время сортировки.
- Инициализируются переменные cpy и cmp, которые будут отслеживать количество копий и сравнений соответственно.
- Функция merge выполняет сортировку слиянием на массиве temp.
- В функции mergesort выполняется рекурсивная сортировка слиянием.
- В функции main создается тестовый массив и выводится его исходное состояние.
- Вызывается функция mergesort для сортировки массива.
- Выводится количество сравнений и копий, выполненных во время сортировки.
- Выводится отсортированный массив.
- Программа возвращает EXIT_SUCCESS.