2
\$\begingroup\$

I have reimplemented the quicksort algorithms that takes a list and sorts it in non-decreasing order:

void qsort(int* l, int len)
{
        if(len <= 1) return;
        int pivot=0;
        for(int i = 0; i<len; i++)
        {
                if(l[i]<l[pivot])
                {
                        swap(l+i, l+pivot);
                        pivot=i;
                }
        }
        qsort(l, pivot);
        qsort(l+x+1, len-x);
}
void swap(int* x, int* y)
{
        *x +=*y;
        *y = *x -*y;
        *x-= *y;
}

Here is a simple implementation:

#include <stdio.h>
void qsort(int* l, int len);
void swap(int* x, int* y);
int main()
{
        int x;
        scanf("%i",&x);
        int l[x];
        for(int i=0; i<x; i++) scanf("%i",l+i);
        qsort(l ,x);
        for(int i=0; i<x; i++) printf("%i\n",l[i]);
}
void qsort(int* l, int len)
{
        if(len <= 1) return;
        int pivot=0;
        for(int i = 0; i<len; i++)
        {
                if(l[i]<l[pivot])
                {
                        swap(l+i, l+pivot);
                        pivot=i;
                }
        }
        qsort(l, pivot);
        qsort(l+pivot+1, len-pivot);
}
void swap(int* x, int* y)
{
        *x +=*y;
        *y = *x -*y;
        *x-= *y;
}

I want to know if my implementation is correct or not. Assuming that it is correct, how can the algorithm do better?

The conquering step takes linear time \$\mathcal{O}(n^2)\$ because the for loop takes linear time, adding and subtracting takes another linear time, and dividing takes time of \$\mathcal{O}(log(n))\$, so it is of time \$\mathcal{O}(n^2 log_2 n)\$.

How can I optimize the code in order to decrease it to take conquer \$\mathcal{O}(n)\$ instead of \$\mathcal{O}(n^2)\$?

\$\endgroup\$
  • \$\begingroup\$ Have you tested this code yourself? \$\endgroup\$ – Simon Forsberg Jan 27 '15 at 10:28
  • \$\begingroup\$ yes I tested the code on 5 and 10 and 15 inputs and it worked correctly but I am afraid that maybe I have missed a corner case \$\endgroup\$ – oddcoder Jan 27 '15 at 10:36
4
\$\begingroup\$

Your Big O interpretation is a bit flawed, This is only O(n) per recursion step (single loop with every operation in the loop being O(1)) leading to the normal O(n log n).

The first optimization you can do is

if(len <= 5) {
    insertionSort(l, len);
}

Insertion sort on short arrays is much faster than quick sort, we can use this to make the last recursion steps quicker.

The second optimization option is pivot selection. Your first element is the pivot is very slow against already sorted arrays. Something like getting the middle element would then be better.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ doesn't the adding and subtracting take linear time theta(n) \$\endgroup\$ – oddcoder Jan 27 '15 at 11:14
  • \$\begingroup\$ @AhmedAbdElMawgood in the swap? no. if you are afraid of that then just use a temp variable swap: int temp = *x; *x = *y; *y = temp; \$\endgroup\$ – ratchet freak Jan 27 '15 at 11:17
1
\$\begingroup\$

In addition to what @ratchet freak mentioned. After deep testing the above code is proven to be inaccurate. It only sort a very limited form of lists (non increasing lists) nothing more.But sorting a list as this 4 3 5 2 1 7 8 9 6 10 will prove that there is a flaw in the code. to be precise I mean this part

 for(int i = 0; i<len; i++)
        {
                if(l[i]<l[pivot])
                {
                        swap(l+i, l+pivot);
                        pivot=i;
                }
        }

which is responsible for bucketing the elements into greater than and smaller than the pivot. And the correct form of this part is the following

int pointer = pivot +1;
for(int j = pivot+1 ; j<len ; j++)
{
        if(l[pivot] > l[j])
        {
                swap(l+pointer, l+j);
                pointer++;
        }
}
pointer --;
swap(l+pointer, l+pivot);

also the swapping routines broke down when testing the code with the list 2 1 the output is 0 2 instead of 1 2 for some unknown reasons while using the traditional swapping with temp solved the problem.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.