5 / 5 / 5
Регистрация: 16.12.2013
Сообщений: 463
1

Как посчитать количество обменов и сравнений при сортировке слиянием?

04.02.2014, 17:06. Показов 9690. Ответов 10
Метки нет (Все метки)

Дан массив: 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
Но как подсчитать кол-во обменов и сравнений,я не понимаю
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.02.2014, 17:06
Ответы с готовыми решениями:

Ошибка при сортировке слиянием
подскажите что не так в программе почему то выдает ошибку одну когда начинается сортировка слиянием...

В пузырьковой сортировке посчитать количество перестановок и сравнения
В пузырьковой сортировке посчитать количество перестановок и сравнения //point.c # include...

Ошибка в сортировке слиянием
#include<stdio.h> #include<conio.h> #include<stdlib.h> #define N 100 void sliv(int a,int...

Как теоретически (не программно) посчитать количество сравнений и обменов в пузырьковой сортировке?
как теоретически посчитать количество сравнений и обменов в пузырьковой сортировке?не программно

10
Музыка нас Связала
232 / 232 / 52
Регистрация: 26.03.2008
Сообщений: 616
04.02.2014, 19:17 2
В Мерджсорте ("Mergesort") нет обменов, ибо Алгоритм работает не in-Place. Скорее всего нужно кол-во копий посчитать?

На счет сравнений (П.С. Сортируют обычно по возрастанию), сравнивайте кол-во сравнений при слиянии:
Пример:

33 | 66 | 82 | 85 -> Входные
33 66 | 82 85 -> 2 Сравнения (33 с 66 и 82 с 85)
33 66 82 85 -> 2 Сравнения (33 с 82, 66 с 82)

Но если же вопрос всё же имеет что-то общее с Си, то просто добавьте в код переменные которые будут инкрементироваться при сравнениях.
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.02.2014, 20:42 3
Цитата Сообщение от Fonduee Посмотреть сообщение
В Мерджсорте ("Mergesort") нет обменов, ибо Алгоритм работает не in-Place. Скорее всего нужно кол-во копий посчитать?
Спорный момент.. Когда Вы сливаете массивы, то Вы сравниваете элементы.. именно эти сравнения и нужно подсчитать, наверное..
0
Музыка нас Связала
232 / 232 / 52
Регистрация: 26.03.2008
Сообщений: 616
04.02.2014, 20:55 4
Ромаха, Речь про обмены, а не про сравнения.
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.02.2014, 20:56 5
Fonduee, речь и про сравнения и про обмены
0
Музыка нас Связала
232 / 232 / 52
Регистрация: 26.03.2008
Сообщений: 616
04.02.2014, 21:00 6
Ромаха, Про сравнения я дал ответ, а обменов нету в Мерджсорте. В нём элементы копируются в отдельный массив, а из него уже обратно, создавая тем самым отсортированый список в определенном диапазоне.

П.С. Под обменом обычно понимают обмен позициями двух элементов a и b.
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
04.02.2014, 21:05 7
Цитата Сообщение от Fonduee Посмотреть сообщение
Ромаха, Про сравнения я дал ответ
Прошу простить.. снова косячу.. проглядел.. думал Вам 1-ый пост именно про обмен..
0
5 / 5 / 5
Регистрация: 16.12.2013
Сообщений: 463
04.02.2014, 21:11  [ТС] 8
Задание следующие:записать состояние массива при сортировке слиянием по убыванию. Указать кол-во сравнений и кол-во обменов элементов. Я не знаю,как считать эти сравнения и обмены
Fonduee , до того момента как массив разбивается на "четверки",я еще понимаю,но дальше какие сравнения идут,я не понимаю
0
Музыка нас Связала
232 / 232 / 52
Регистрация: 26.03.2008
Сообщений: 616
04.02.2014, 21:39 9
33-66-82-85-15-17-74 -> Входные данные
Начинаем Разбив на полупроблемы: Если левый поинтер меньше правого, производим вызов mergesort(l, (l+r)/2) и mergesort(((l+r)/2)+1, r), где n - размер массива.

33-66-82-85 | 15-17-74
33-66 | 82-85 |15-17 | 74
33 | 66 | 82 | 85 | 15 | 17 | 74

Теперь сливаем всё обратно!
66-33 | 85-82 | 17-15 | 74 -> имеем 3 Сравнения (33 с 66, 82 с 85 и 15 с 17). 74 не нужно сортировать.
Каждая часть уже отсортирована, нужно лишь опять слить всё вместе.
85-82-66-33 | 74-17-15 -> Сравниваем 85 с 66 (+1), далее 82 с 66 (+1) и всё. Втарая часть полумассива пуста, а первая отсортирована. Также поспупаем и с правой частью. (+1).

И в конце получаем

85-82-74-66-33-17-15 (+5). Результат имеем всего 11 Сравнений.

П.С. Вы должны посмотреть как работает мерджсорт и понять его, а также немного теории не помешает. Максимум сравнений выливается в асимптотику O(n * log n).
0
5 / 5 / 5
Регистрация: 16.12.2013
Сообщений: 463
04.02.2014, 22:24  [ТС] 10
Fonduee,спасибо за подробное объяснение. Обменов я насчитала 9,верно?
0
Музыка нас Связала
232 / 232 / 52
Регистрация: 26.03.2008
Сообщений: 616
05.02.2014, 00:17 11
Нет, как я уже сказал, обменов в данном алгоритме нет, есть создание копий! Берутся 2 простые проблемы, у нас пусть это будут 33 и 66, и как уже я выше описал, сравниваем их. Самый большой копируем в выделенный для этих целей массив размером n (как и изначальный массив), и только потом 33. Итог -> имеем отсортированый массив из 2 элементов. Они же копируются обратно в изначальный массив. Копирование было произведено 3 раза, и это было только для первых двух элементов. Так, что высчитывайте, скольков всего будет операций.

Добавлено через 1 час 4 минуты
Trying to sort an array: 33 66 82 85 15 17 74

Comparisons: 11
Copy Operations: 26

The sorted array: 85 82 74 66 33 17 15

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.02.2014, 00:17
Помогаю со студенческими работами здесь

Количество сравнений и обменов при сортировке матрицы разными способами
Необходимо создать однородную таблицу. Затем применить три метода сортировки: Бинарным включением,...

Количество сравнений/перестановок в сортировке естественным слиянием
Добрый день ! Никак не могу понять как создать счётчик и куда его вставить , лазил по форумах и не...

Быстрая сортировка: посчитать количество сравнений и обменов
помогите, пожалуйста ) нужно посчитать количество сравнений и обменов в алгоритме &quot;быстрой&quot;...

Как посчитать количество итераций в сортировке слиянием?
void merge(int l, int r) { if (r == l) return; if (r - l == 1) { if (a &lt; a) swap(a,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru