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

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

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

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

10.05.2011, 14:53. Просмотров 2512. Ответов 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;
   }
}
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++
Здравствуйте! Никак не могу подсчитать количество перестановок елементов массива в сортировке Хоара:( Сделал счетчик value в цикле while,...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
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
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
10.05.2011, 15:26     Количество перестановок #4
Ну как бы метод вставки так работает:
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан.
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 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
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 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++
Как найти в этой сортировке количество перестановок и сравнений? void InsertSort(int *mas, int N) //сортировка вставками { int...

Как определить количество перестановок и сравнений в выборочной сортировке - C++
void choicesSort(int* Array, int length_array) { for (int repeat_counter(0); repeat_counter &lt; length_array; repeat_counter++) ...

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

Как найти в данной сортировке количество перестановок и сравнений? - 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; ...

Нужно вставить счетчик, чтобы посчитать количество сравнений и перестановок - C++
#include &lt;iostream&gt; #include &lt;ctime&gt; using namespace std; int main() { int arr, a, b, i, size; size = 100; //...


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

Или воспользуйтесь поиском по форуму:
fasked
Эксперт С++
4933 / 2513 / 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.

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

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