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

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

Войти
Регистрация
Восстановить пароль
 
RiMpel2
0 / 0 / 0
Регистрация: 04.10.2010
Сообщений: 22
#1

Счетчик сравнений для быстрой сортировки - C++

05.03.2013, 18:23. Просмотров 1054. Ответов 2
Метки нет (Все метки)

Добрый вечер. Взял сортировку из википедии
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void qSort(int arr7[], int first, int last) {
      k = first;                
      l = last;
      x = arr7[(first+last)/2];  
      do {
          while(arr7[k] > x){ k++; }  
          while(arr7[l] < x){ l--; }  
          if(k <= l){           
              
              tmp = arr7[k];   
              arr7[k] = arr7[l];
              arr7[l] = tmp;
              pr5=pr5+1;  //перестановки+1 после перевертыша
              if(k==l || arr7[k]==arr7[l]){ pr5=pr5-1;} // минус один если перевернутые объекты совпадали
              k++; l--;           
          }
      } while(k < l);
      if(first < l) qSort(arr7, first, l);
      if(k < last) qSort(arr7, k, last);
  }
Изменил для убывания и подставил счетчик перестановок. По идее он должен работать верно. Интересует счетчик сравнений - не знаю куда поставить, помогите пожалуйста.
ПС считать на бумажке алгоритм с рекурсией для подсчета сравнений вручную очень муторно, поэтому прошу помочь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.03.2013, 18:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Счетчик сравнений для быстрой сортировки (C++):

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

Куда в программе добавить счетчик для поиска количества перестановок и сравнений? - C++
void InsertSort(int *mas, int N) //сортировка вставками { int i,key=0,temp=0; int count_compare=0, count_swap; for (i=0; i&lt;N-1;...

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

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

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

Почему число сравнений в быстрой сортировке ( Хоара) различно? - C++
Сортирую один и тот же массив, но в различной степени упорядоченности, почему число сравнений различно, ведь всегда должно NlogN выходить? ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
05.03.2013, 18:52 #2
Я бы не стал добавлять счетчик прямо в функцию. Вместо этого я вижу 2 варианта:
1) Передавать в функцию сортировки предикат, который будет сравнивать два элемента, и затем просто посчитать число вызовов этого предиката.
2) Заменить int на шаблон и создать свой класс инта с перегруженными операторами. Это слегка муторно, но при этом код собственно сортировки вообще не изменится. Причем для других сортировок нужно будет также всего лишь поменять параметры функции на шаблоны. В принципе, для такого класса хватит лишь перегрузки операторов сравнения и неявного приведения к инту.
RiMpel2
0 / 0 / 0
Регистрация: 04.10.2010
Сообщений: 22
05.03.2013, 19:03  [ТС] #3
Для других сортировок счетчики сделал, ради одной быстрой создавать классы итд не буду. Попробую первый вариант. спасибо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2013, 19:03
Привет! Вот еще темы с ответами:

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

Как определить количество сравнений и перестановок в быстрой сортировке массива - C++
Пробовал сделать счётчики, но они выводили кол-ва для сортировке всех подмассивов, а как вывести кол-во всех перестановок и сравнений за...

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

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


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

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

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