Как посчитать количество обменов и сравнений при сортировке слиянием? - 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.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д