Number of comparision quick sort

[mishaelsp]

Tryying to coun the numeber of comparicion but dont know how to count them

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

using namespace std;

//funcion para dividir el array y hacer los intercambios
int dividir (int *array, int inicio, int fin){

  int comp=0;
  int izq;
  int der;
  int pibote;
  int temp;

  pibote = array[inicio];
  izq = inicio;
  der = fin;

  //Mientras no se cruzen los índices
  while (izq < der){
      comp++;
    while (array[der] > pibote){
      der--;
    }

    while ((izq < der) && (array[izq] <= pibote)){
      izq++;
    }

    // Si todavia no se cruzan los indices seguimos intercambiando
    if(izq < der){
      temp= array[izq];
      array[izq] = array[der];
      array[der] = temp;
    }
  }

  //Los indices ya se han cruzado, ponemos el pivote en el lugar que le corresponde
  temp = array[der];
  array[der] = array[inicio];
  array[inicio] = temp;

  //La nueva posición del pivote
  return der;

}

//funcion recursiva para hacer el ordenamiento
void quicksort( int *array, int inicio, int fin)
{
  int pivote;
  if(inicio < fin){
    pivote = dividir(array, inicio, fin );
    quicksort( array, inicio, pivote - 1 );//ordeno la lista de los menores
    quicksort( array, pivote + 1, fin );//ordeno la lista de los mayores
  }
}

int main()
{
  int tamanyo,c;
  int a[]={1,2,3,4};
  int comp;
  cout << "Ingresa tamanyo " << endl;
  cin >> tamanyo;

  cout << "Array antes de ordenarse: " << endl;
  for (int i=0; i < tamanyo; i++){
    cout << a[i] << " ";
  }

  cout << endl << endl;

  quicksort(a, 0, tamanyo - 1 );
  printf("Numero de comparaciones %d\n", comp);
  cout << "Array ordenado " << endl;

  for (int i=0; i < tamanyo; i++ ){
    cout << a[i] << "-";
  }
  cout << endl << endl;
  c=getch();
  return 0;
}

[rubberman]

From the Wikipedia quicksort article:

Quicksort, or partition-exchange sort, is a sorting algorithm that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms.[1] Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space.[2]

[rubberman]

One thing you are missing is the comparison function. If you use such, then you can easily count the number of times it is called. The standard system call for quicksort is called qsort. Here is the Linux signature for it:

void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));