current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite
1

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)\$?

share|improve this question
    
Have you tested this code yourself? –  Simon Forsberg♦ Jan 27 at 10:28
    
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 –  Ahmed Abd El Mawgood Jan 27 at 10:36

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
doesn't the adding and subtracting take linear time theta(n) –  Ahmed Abd El Mawgood Jan 27 at 11:14
    
@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; –  ratchet freak Jan 27 at 11:17
up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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