Sunday 21 April 2013

QUICK SORT

Quicksort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quick Sort is well known as ’the best practical sorting algorithm'. It is used on the principle of divide-and-conquer. It is often faster in practice than other O(n log n) algorithms.

  • Pick an element, called a pivot, from the list.
  • Partition the list so that all elements which are less than the pivot come before the pivot, and elements greater than the pivot come after it. For instance,
      A[1...i]  A[pivot]  A[j-+ 1...n]
  ◟  ◝◜ ◞  ◟ ◝◜  ◞  ◟   ◝◜   ◞
≤ A [pivot]           ≥ A[pivot]
  • Recursively repeat those operations to sort the sublists of lesser elements and of greater elements.







Time Complexity
The performance of Quick Sort always depends on the position of selected pivot. A bad pivot could lead to poor performance, for instance, selecting position 1 as the pivot produces a recursion tree of height n. Conversely, a good pivot would operate at best performance of O(⋅ log n) of tree height Θ(log n), pivot at the middle of the list, for instance.

SOURCE CODE #1:-

/******************************************************************************/

//RECURSIVE QUICK SORT THROUGH A SINGLE FUNCTION

#include<stdio.h>
#include<conio.h>

void quicksort(int*,int,int);

int main()
{
int n,i,*arr;
clrscr();

printf("ENTER THE MAXIMUM NUMBER OF ELEMENTS");
scanf("%d",&n);

printf("ENTER THE DATA ELEMENTS THAT YOU WANT TO SORT");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

quicksort(arr,0,n-1);

for(i=0;i<n;i++)
printf("%d\t",arr[i]);

getch();
return 1;
}

void quicksort(int*arr,int a,int b)
{
int i=a+1,j=b,tmp;

if(i>j)
return;

while(i<=j)
{
for(;arr[i]<arr[a]&&i<=b;i++);
for(;arr[j]>arr[a]&&j>=a;j--);

if(i<=j)
{
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}

tmp=arr[a];
arr[a]=arr[j];
arr[j]=tmp;

quicksort(arr,a,j-1);
quicksort(arr,j+1,b);
}
/*****************************************************************************/




SOURCE CODE #2:-
/*****************************************************************************/
#include<stdio.h>
#include<conio.h>


void quicksort(int *,int,int);
int qsort(int*,int,int);

int flag=0,abc;

int main()
{
int i,j,ploc,min,n,arr[50];
clrscr();

printf("enter the max no of elements of array\n");
scanf("%d",&n) ;
abc=n;

printf("enter the data of array\n");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

quicksort(arr,0,n-1);


for(i=0;i<n;i++)
printf("%d\t",arr[i]);

getch();
return 1;
}


void quicksort(int*arr,int min,int max)
{
int ploc;
while(max>min)
{
ploc=qsort(arr,min,max);
quicksort(arr,min,ploc-1);
quicksort(arr,ploc+1,max);
if(flag>abc)
return;
}
}


int qsort(int *arr,int min,int max)
{
int ploc,j,tmp;
ploc=min;
for(j=ploc+1;j<=max;)
if(arr[j]<arr[min])
{
ploc++;
tmp=arr[ploc];
arr[ploc]=arr[j];
arr[j]=tmp;
j=ploc+1;
}
else
j++;


tmp=arr[min];
arr[min]=arr[ploc];
arr[ploc]=tmp;
//printf("Lavish\n");
flag++;

return ploc;
}



/*******************************************************************************/


No comments:

Post a Comment