## 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 1,355

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 1,355

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 *));
``````