Quick Sort

/*
* Status: Tested OK
* Title: Quick Sort
* Name: Akshay Thakare
*/

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

int *x;

int partition(int lb, int ub)
{
	int val = x[lb], down = lb+1, up = ub,t;
	
	while(down<=up)
	{
		while(down<=up && x[down]<val)
		{
			down++;
		}
		while(x[up]>val)
		{
			up--;
		}
		if(down<up)
		{
			t = x[down];
			x[down]=x[up];
			x[up]=t;
		}
	}
	x[lb] = x[up];
	x[up] = val;
	return up;
}

void quicksort(int lb,int ub)
{
	int p;
	if (lb<ub)
	{
		p = partition(lb,ub);
		quicksort(lb,p-1);
		quicksort(p+1,ub);
	}
}

int main()
{
	int n,i;
	printf("\nEnter the number of elements to be sorted : ");
		scanf("%d",&n);
		
	x = malloc(n*sizeof(int));
	
	printf("\nEnter the elements to be sorted below\n");
	for(i=0;i<n;i++)
		scanf("%d",&x[i]);
	
	quicksort(0,n);
	
	printf("\nThe sorted elements are\n");
	for(i=0;i<n;i++)
		printf("%d ",x[i]);
	
	return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s