Can the following quicksort program be improved?

[Nikhar]

Ok... i ran my quicksort program on my college lab's machine (i dunno its config) and it took 4 seconds on avg to sort 1 million elements. I ran it on my lappy (4 gb RAM, Intel Core i5-2410M Processor (2.3 GHz)) and it took 0.83 seconds to run the same number of elements. So, now I'm a little confused. I'd be really obliged if you could tell me if my quicksort program can be improved and if yes, then how.

Thanks in advance.

#include<stdio.h>

void quicksort(int*,int,int);

int n;

int main()
{
	scanf("%d",&n);
	int i, a[n];
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	quicksort(a,0,n-1);
	for(i=0;i<n;i++)
		printf("%d\n",a[i]);
}

void quicksort(int *a, int start, int end)
{
	if(start>=end)
		return;
	int pivot=(start+end)/2;//choosing mid element as pivot
	a[pivot]=a[end]+a[pivot]-(a[end]=a[pivot]);//swapping it ith last element
	pivot=end;
	int hi=start,i;//hi (high index) marks the beginning index of higher elements
	for(i=start;i<end;i++)
	{
		if(a[i]<=a[pivot])
		{
			a[hi]=a[i]+a[hi]-(a[i]=a[hi]);
			hi++;
		}
	}
	a[hi]=a[pivot]+a[hi]-(a[pivot]=a[hi]);
	pivot=hi;
	hi++;
	quicksort(a,start,pivot-1);
	quicksort(a,hi,end);
}

[nezachem]

Yes.
At lines 23, 30 and 34 the behavior is undefined. The improvement is obvious.

[Nikhar]

Well, the lines 23, 30 and 34 swap the two elements in question. The behaviour is not undefined. As a matter of fact the output of my quicksort program is correct. My only concern is the time that it takes.

[deceptikon]

As a matter of fact the output of my quicksort program is correct.

Unfortunately, in C "working" is not a guarantee of correctness. The swap process is undefined. Take a[hi]=a[pivot]+a[hi]-(a[pivot]=a[hi]); as an example. In C you can't assign to a variable and then use it again for anything except to determine the new value between sequence points. First the expression assigns a[hi] to a[pivot] . That's fine. Then it tries to use the value of a[pivot] in a way that doesn't determine a[pivot] 's new value.

It's better to write boring code than to be clever. The usual three variable swap is probably going to be faster anyway because of compiler optimizations.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10
#define SWAP(a, b) do { int temp = a; a = b; b = temp; } while (0)

void quicksort(int *a, int start, int end);

int main()
{
    srand((unsigned)time(NULL));
    
    int a[N];
    
    for (int i = 0; i < N; i++)
    {
        a[i] = rand();
    }
    
    quicksort(a, 0, N - 1);
    
    for (int i = 0; i < N; i++)
    {
        printf("%d\n", a[i]);
    }
}

void quicksort(int *a, int start, int end)
{
    if (start >= end)
    {
        return;
    }
    
    int pivot = (start + end) / 2;
    int hi = start;
    
    SWAP(a[pivot], a[end]);
    pivot = end;
    
    for (int i = start; i < end; i++)
    {
        if (a[i] <= a[pivot])
        {
            SWAP(a[hi], a[i]);
            hi++;
        }
    }
    
    SWAP(a[hi], a[pivot]);
    pivot = hi++;
    
    quicksort(a, start, pivot - 1);
    quicksort(a, hi, end);
}

My only concern is the time that it takes.

If speend is a concern, I'd recommend eliminating non-tail recursion first. Compilers can optimize tail recursion into a loop, but non-tail recursion will still be generated as function calls. A bunch of function calls has more overhead and is probably slower than a loop.

If you want to look at an optimized quicksort, this code snippet looks pretty good.

[Nikhar]

@deceptikon
I get your point (a little) about the swap process. But if the process is undefined, how does it actually manage to swap the elements in question (i can swap the elements successfully using this statement with gcc compiler).

I am not exactly sure as to what non-tail recursion means but I'll google that. Thanks for the tip. :)

[deceptikon]

But if the process is undefined, how does it actually manage to swap the elements in question (i can swap the elements successfully using this statement with gcc compiler).

Undefined doesn't mean it won't work. Undefined also doesn't mean it *will* work. Undefined means anything can happen, and that's not a good trait to have in a program. ;)