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

@RiMpel2 · Регистрация: 04.10.2010

Author24 — интернет-сервис помощи студентам

Добрый вечер. Взял сортировку из википедии

C++

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);
  }

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

@diagon · 05.03.2013, 18:52

Я бы не стал добавлять счетчик прямо в функцию. Вместо этого я вижу 2 варианта:
1) Передавать в функцию сортировки предикат, который будет сравнивать два элемента, и затем просто посчитать число вызовов этого предиката.
2) Заменить int на шаблон и создать свой класс инта с перегруженными операторами. Это слегка муторно, но при этом код собственно сортировки вообще не изменится. Причем для других сортировок нужно будет также всего лишь поменять параметры функции на шаблоны. В принципе, для такого класса хватит лишь перегрузки операторов сравнения и неявного приведения к инту.

@RiMpel2 · 05.03.2013, 19:03 **[ТС]**

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

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	05.03.2013, 18:52	2
	Я бы не стал добавлять счетчик прямо в функцию. Вместо этого я вижу 2 варианта: 1) Передавать в функцию сортировки предикат, который будет сравнивать два элемента, и затем просто посчитать число вызовов этого предиката. 2) Заменить int на шаблон и создать свой класс инта с перегруженными операторами. Это слегка муторно, но при этом код собственно сортировки вообще не изменится. Причем для других сортировок нужно будет также всего лишь поменять параметры функции на шаблоны. В принципе, для такого класса хватит лишь перегрузки операторов сравнения и неявного приведения к инту. 1

@RiMpel2 0 / 0 / 0 Регистрация: 04.10.2010 Сообщений: 22
	05.03.2013, 19:03 [ТС]	3
	Для других сортировок счетчики сделал, ради одной быстрой создавать классы итд не буду. Попробую первый вариант. спасибо. 0