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

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

Восстановить пароль Регистрация
 
RiMpel2
0 / 0 / 0
Регистрация: 04.10.2010
Сообщений: 22
05.03.2013, 18:23     Счетчик сравнений для быстрой сортировки #1
Добрый вечер. Взял сортировку из википедии
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++ Тонкости быстрой сортировки
Алгоритм быстрой сортировки - посчитать количество перестановок и сравнений элементов массивов C++
C++ Два счетчика для обмена и сравнений для сортировки массива
Найти количество сравнений после сортировки массива C++
Количество произведенных сравнений в Быстрой Сортировке C++
Куда в программе добавить счетчик для поиска количества перестановок и сравнений? C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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
Для других сортировок счетчики сделал, ради одной быстрой создавать классы итд не буду. Попробую первый вариант. спасибо.
Yandex
Объявления
05.03.2013, 19:03     Счетчик сравнений для быстрой сортировки
Ответ Создать тему
Опции темы

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