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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
Fiasco
0 / 0 / 0
Регистрация: 28.10.2010
Сообщений: 23
10.05.2011, 14:53     Количество перестановок #1
Здравствуйте!
Как подсчитать количество сделанных перестановок в результате сортировки массива методом вставки?
Буду очень благодарен.

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;
   }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2011, 14:53     Количество перестановок
Посмотрите здесь:

C++ Задача на количество перестановок
C++ Как определить количество перестановок и сравнений
Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов C++
C++ Подсчитать Количество перестановок при сортировке массива по возрастанию
C++ Сортировка слиянием: подсчитать количество перестановок
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LineStown
 Аватар для LineStown
63 / 63 / 3
Регистрация: 04.08.2010
Сообщений: 399
10.05.2011, 15:15     Количество перестановок #2
Добавить счетчик в месте перестановки элементов

Добавлено через 39 секунд
Ка только меняется последовательность массива - то +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. Разве это правильно?
LineStown
 Аватар для LineStown
63 / 63 / 3
Регистрация: 04.08.2010
Сообщений: 399
10.05.2011, 15:26     Количество перестановок #4
Ну как бы метод вставки так работает:
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
10.05.2011, 15:34     Количество перестановок #5
Цитата Сообщение от Fiasco Посмотреть сообщение
Тогда количество перестановок = количеству елементов массива, при любой инициализации size. Разве это правильно?
Нет, это неправильно. Потому как сложность в таком случае получается линейной. Счетчик надо ставить в обоих циклах, тогда получится примерно n^2.
Fiasco
0 / 0 / 0
Регистрация: 28.10.2010
Сообщений: 23
10.05.2011, 21:43  [ТС]     Количество перестановок #6
fasked, то есть нужно еще один щетчик ставить в цикле while...допустим это некоторая перемення m...я так понял?

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

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

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

Как подсчитать произведенное количество перестановок при быстрой сортировке? C++
Как найти в этой сортировке количество перестановок и сравнений? C++
Как найти в данной сортировке количество перестановок и сравнений? C++

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

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

Примерно вроде бы так, но мог напутать с числами, если интересно - поищите в сети, полно должно быть анализов сортировок, тема избитая.
Yandex
Объявления
11.05.2011, 00:43     Количество перестановок
Ответ Создать тему
Опции темы

Текущее время: 08:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru