Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
Fiasco
0 / 0 / 0
Регистрация: 28.10.2010
Сообщений: 23
#1

Количество перестановок - C++

10.05.2011, 14:53. Просмотров 2669. Ответов 8
Метки нет (Все метки)

Здравствуйте!
Как подсчитать количество сделанных перестановок в результате сортировки массива методом вставки?
Буду очень благодарен.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class T>
void TArray <class T> :: sort ()
{
   for (int i = 0; i < size; i++)
   {
      int x = mas [i];
      int j = i - 1;
      while (x < mas [j])
      {
     mas [j + 1] = mas [j];
     j--;
      }
      mas [j + 1] = x;
   }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2011, 14:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Количество перестановок (C++):

Задача на количество перестановок - C++
На вход подаем число предметов, которые человек берет с разных мест. На выход должно выдать число - количество способов вернуть каждое из...

Как определить количество перестановок и сравнений - C++
У меня есть алгоритм Quicksort как определить количество перестановок и сравнений?? #include &lt;iostream&gt; #include &lt;conio.h&gt; #include...

Количество перестановок при сортировке массива - C++
Как вывести число количества перестановок после сортировки массива, допустим выбору?

Сортировка слиянием: подсчитать количество перестановок - C++
Привет всем. Дана задача: подсчитать количество перестановок при сортировке массива. Нужен быстрый алгоритм, желательно алгоритм сортировки...

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

Посчитать количество сравнений и перестановок в сортировке выбором - C++
Доброго времени суток, столкнулся с проблемой, не знаю куда поставить счетчики на сравнения и перестановки в сортировке выбором, уже всяко...

8
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
10.05.2011, 15:15 #2
Добавить счетчик в месте перестановки элементов

Добавлено через 39 секунд
Ка только меняется последовательность массива - то +1
1
Fiasco
0 / 0 / 0
Регистрация: 28.10.2010
Сообщений: 23
10.05.2011, 15:21  [ТС] #3
Вы имеете ввиду так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class T>
void TArray <class T> :: sort ()
{
   int n = 0;
   for (int i = 0; i < size; i++)
   {
      int x = mas [i];
      int j = i - 1;
      while (x < mas [j])
      {
         mas [j + 1] = mas [j];
         j--;
      }
      mas [j + 1] = x;
      n++;   
   }
   cout << "Количество перестановок = " << n << endl;
}
Тогда количество перестановок = количеству елементов массива, при любой инициализации size. Разве это правильно?
0
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
10.05.2011, 15:26 #4
Ну как бы метод вставки так работает:
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан.
1
fasked
Эксперт С++
4942 / 2522 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
10.05.2011, 15:34 #5
Цитата Сообщение от Fiasco Посмотреть сообщение
Тогда количество перестановок = количеству елементов массива, при любой инициализации size. Разве это правильно?
Нет, это неправильно. Потому как сложность в таком случае получается линейной. Счетчик надо ставить в обоих циклах, тогда получится примерно n^2.
1
Fiasco
0 / 0 / 0
Регистрация: 28.10.2010
Сообщений: 23
10.05.2011, 21:43  [ТС] #6
fasked, то есть нужно еще один щетчик ставить в цикле while...допустим это некоторая перемення m...я так понял?

и чему тогда будет равно количество перестановок?
0
fasked
Эксперт С++
4942 / 2522 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
10.05.2011, 21:50 #7
Цитата Сообщение от Fiasco Посмотреть сообщение
то есть нужно еще один щетчик ставить в цикле while...допустим это некоторая перемення m...я так понял?
тот же самый счетчик, в цикле while сделать n++ тоже.
1
Fiasco
0 / 0 / 0
Регистрация: 28.10.2010
Сообщений: 23
10.05.2011, 23:20  [ТС] #8
fasked, спасибо...

кстати смотрел в книге Седжвика "Фундаментальные алгоритмы на С/С++", там количество (приблизительное) перестановок равно size * size / 4

от того метода, что посоветовали Вы результат отличается приблизительно на 0-40 перестановок
0
fasked
Эксперт С++
4942 / 2522 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
11.05.2011, 00:43 #9
Цитата Сообщение от Fiasco Посмотреть сообщение
кстати смотрел в книге Седжвика "Фундаментальные алгоритмы на С/С++", там количество (приблизительное) перестановок равно size * size / 4
от того метода, что посоветовали Вы результат отличается приблизительно на 0-40 перестановок
количество перестановок сильно зависит от конкретного содержимого массива. Для сортировки вставками в наилучшем случае (когда массив уже отсортирован) потребуется size-1 сравнений, в наихудшем случае (массив отсортированном в обратном порядке) потребуется size*(size-1)/2. Что в среднем как раз и даст size* size / 4.

Примерно вроде бы так, но мог напутать с числами, если интересно - поищите в сети, полно должно быть анализов сортировок, тема избитая.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.05.2011, 00:43
Привет! Вот еще темы с ответами:

Как найти в этой сортировке количество перестановок и сравнений? - C++
Как найти в этой сортировке количество перестановок и сравнений? void InsertSort(int *mas, int N) //сортировка вставками { int...

Подсчитать Количество перестановок при сортировке массива по возрастанию - C++
Привет всем. Мне нужно написать программу, которая подсчитывает минимальное количество перестановок при сортировке массива по возрастанию....

Быстрая сортировка, подсчитать количество перестановок элементов массива - C++
Здравствуйте! Никак не могу подсчитать количество перестановок елементов массива в сортировке Хоара:( Сделал счетчик value в цикле while,...

Как найти в данной сортировке количество перестановок и сравнений? - C++
void quicksort(int *mas, int first, int last) { int mid, count, m=0; int f=first, l=last; int count_compare=0, count_swap=0; ...


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

Или воспользуйтесь поиском по форуму:
9
Yandex
Объявления
11.05.2011, 00:43
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru