Comparison Counting using C++

[peachslasher]

Hey guys,

I need to write a C++ program that use to compare sorting algorithm. I've tried to implement counter on each of <.>, = operations I've encounter in the function (currently i am working on selection sort), however the sum of the counter doesn't really match big O selection sort equation which is O=(n^2)

right now if n = 10 gives result of 64

My problem is I am unsure where to insert my counter in my function to counts the comparison properly?

I'll attach my program below

Thanks heaps for your help =D

#include <iostream>
#include <time.h>

using namespace std;

int data[5000];
int first[5000];
int second[5000];
int co=0;

void selectionSort(int count);
void BubbleSort(int count);
void fillArray(int count);
void swap(int & m, int & n);
void printArray(int count, int input[]);


void swap(int & m, int & n){
	int temp = m;
	m = n;
	n = temp;
	//co++;
}

void fillArray(int count){
	int i;
	// example theres 10 element inside the array
	for(i=0;i < count; i++){
		data[i] = rand();
		//cout << data[i] << endl;
	}
}

void selectionSort(int count){
	//select the smallest number and swap it to the front
	int pass, i, min;
		for(pass=0; pass<count-1;pass++){
			min = pass; 
			co++;
			for(i = pass+1; i < count; i++){
				co++;
				if(data[i] < data[min]){
					min = i;
					co++;
				}
			}
			swap(data[min],data[pass]);
		}
}

void BubbleSort(int count){
	bool swapping;
	int i;
	swapping = true;
	while (swapping) {
	swapping = false;
		for (i = 0; i < count - 1; i++) { // don’t look at the last one
			if (data[i] > data[i + 1]) { // a comparison here
				swap(data[i], data[i + 1]);
			swapping = true;
			}
		}
	}
}

void printArray(int count, int input[]){
	int i;
	for(i=0;i<count;i++){
		cout <<input[i] << endl;
	}
}

void halfArray(int count){
	int i, n;
	for(i=0;i<count;i++){
		for(n=0;n<count/2;n++){
			first[n]=data[n];
		}
	second[i] = data[n+i];
	}
} 

int main(){
	//fillArray(10);
	selectionSort(10);
	//BubbleSort(10);
	//printArray(10,data);
	cout << co << endl;

	
}

[Radical Edward]

> I am unsure where to insert my counter in my function to counts the comparison properly?
Anywhere you compare the data that's being sorted, increment the counter. Here's one way Edward would do it:

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <vector>

template <typename T>
struct CompareCount {
  unsigned long count;
  CompareCount(): count(0) {}
  bool less(T a, T b) { ++count; return a < b; }
};

template <typename T>
struct SwapCount {
  unsigned long count;
  SwapCount(): count(0) {}
  void swap(T& a, T& b) {
    ++count;
    std::swap(a, b);
  }
};

template <typename Container>
void bubblesort(Container& c)
{
  CompareCount<Container::value_type> cmp;
  SwapCount<Container::value_type> swp;

  for (Container::size_type i = 0; i < c.size(); ++i) {
    for (Container::size_type j = c.size() - 1; j > i; --j) {
      if (cmp.less(c[j], c[j - 1]))
        swp.swap(c[j], c[j - 1]);
    }
  }

  std::cout << "Comparisons: " << cmp.count << '\n';
  std::cout << "Swaps:       " << swp.count << '\n';
}

int main()
{
  std::vector<int> v(10);

  std::srand(std::time(0));

  std::generate(v.begin(), v.end(), std::rand);
  std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << '\n';
  bubblesort(v);
  std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << '\n';
}