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
|
|
04.02.2014, 17:06 | |
Ответы с готовыми решениями:
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
|
Музыка нас Связала
232 / 232 / 52
Регистрация: 26.03.2008
Сообщений: 616
|
|
04.02.2014, 20:55 | 4 |
Ромаха, Речь про обмены, а не про сравнения.
0
|
Музыка нас Связала
232 / 232 / 52
Регистрация: 26.03.2008
Сообщений: 616
|
|
04.02.2014, 21:00 | 6 |
Ромаха, Про сравнения я дал ответ, а обменов нету в Мерджсорте. В нём элементы копируются в отдельный массив, а из него уже обратно, создавая тем самым отсортированый список в определенном диапазоне.
П.С. Под обменом обычно понимают обмен позициями двух элементов a и b.
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
0
|
05.02.2014, 00:17 | |
Помогаю со студенческими работами здесь
11
Количество сравнений и обменов при сортировке матрицы разными способами Количество сравнений/перестановок в сортировке естественным слиянием Быстрая сортировка: посчитать количество сравнений и обменов Как посчитать количество итераций в сортировке слиянием? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |