Как посчитать количество обменов и сравнений при сортировке слиянием? - 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;
}

Объяснение кода листинга программы

  1. Создается массив temp для временного хранения данных во время сортировки.
  2. Инициализируются переменные cpy и cmp, которые будут отслеживать количество копий и сравнений соответственно.
  3. Функция merge выполняет сортировку слиянием на массиве temp.
  4. В функции mergesort выполняется рекурсивная сортировка слиянием.
  5. В функции main создается тестовый массив и выводится его исходное состояние.
  6. Вызывается функция mergesort для сортировки массива.
  7. Выводится количество сравнений и копий, выполненных во время сортировки.
  8. Выводится отсортированный массив.
  9. Программа возвращает EXIT_SUCCESS.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 4.091 из 5
Похожие ответы