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(n²) 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,
  
• 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(n ⋅ 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;

}

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