CODEWITHSUNDEEP
c#algorithmsortingtime-complexityquicksort
Murilo Pereira
Murilo Pereira

Reputation: 109

QuickSort wrong complexity in C#

I'm doing some analysis of sorting algorithms and I faced a problem with Quick Sort. Looking for some charts on the Internet, I saw that my chart is significantly different from others charts, and I want to know why.

This is my code:

static int Particao(int[] vet, int min, int max, int modo)
{
    int i = min;
    int j = max;            
    int pivot;

    if (modo == 0)
        pivot = vet[(min + max) / 2];
    else
        pivot = vet[min];            
    while (i <= j)
    {
        while (vet[i] < pivot)
            i++;
        while (vet[j] > pivot)
            j--;
        if (i <= j)
        {
            int aux = vet[i];
            vet[i] = vet[j];
            vet[j] = aux;
            i++;
            j--;
        }
    };

    return i;
}

static void QuickSort(int[] vet, int ini, int fim)
{
    int pivo = Particao(vet, ini, fim, 0);

    if (ini < pivo - 1)
        QuickSort(vet, ini, pivo - 1);
    if (pivo < fim)
        QuickSort(vet, pivo, fim);            

}

My chart (time is in ms and multiplied by 1000):

Quick Sort

Thanks =)

Upvotes: 0

Views: 71

Answers (1)

elikoga
elikoga

Reputation: 164

Your chart is different from the other charts due to differences in measurement. The other charts had many more datapoints and many averaged measurements to keep errors out.

Your chart only has 6 datapoints with 1 measurement each and it is fairly hard to conclude anything from that.

Perhaps you could measure the amount of swaps or comparisons and extrapolate a graph from that?

Upvotes: 1

Related Questions