QUICK SORT

If you have any queries please leave a message here
Your Message
×


Quick sort is based on the divide-and-conquer approach based on the idea of choosing one element as a pivot element and partitioning the array around it such that : Left side of pivot contains all the elements that are less than the pivot element and Right side contains all the elements greater than the pivot element.

There are many different ways to choose the pivot value, we will simply use the first item in the list.



At the point where rightmark becomes less than leftmark, we stop. The position of rightmark is now the split point. The pivot value can be exchanged with the contents of the split point and the pivot value is now in place. In addition, all the items to the left of the split point are less than the pivot value, and all the items to the right of the split point are greater than the pivot value.


The list can now be divided at the split point and the quick sort can be invoked recursively on the two halves.




Quick Sort Programming in C
#include<stdio.h>

//Global function declaration
void QuickSort(int a[],int start,int end);
int Partition(int a[],int start,int end);

void main()
{
int array[]={54, 25, 92, 18, 84, 45, 56, 20};
int i;
QuickSort(array,0,7);
for(i=0; i<8; i++)
{
printf("\t%d",array[i]);
}
}

//QuickSort( ) function
void QuickSort(int a[],int start,int end)
{
int pivot_pos;
if(start < end)
{
pivot_pos = Partition(a, start, end );
//Sorts the left side of pivot.
QuickSort(a, start, pivot_pos-1);
//Sorts the right side of pivot.
QuickSort( a, pivot_pos+1, end);
}
}

//Partition( ) function
int Partition(int a[],int start,int end)
{
int pivot, leftmark, rightmark, temp;
leftmark = start+1;
rightmark = end;

//Make the first element as pivot element.
pivot = a[start];

while(leftmark < rightmark)
{
while(leftmark <= rightmark && a[leftmark] <= pivot)
leftmark = leftmark + 1;
while(leftmark <= rightmark && a[rightmark] >= pivot)
rightmark = rightmark - 1;
if (leftmark <= rightmark)
{
temp = a[leftmark];
a[leftmark] = a[rightmark];
a[rightmark] = temp;
}
}
//Put the pivot element in its proper place.
temp = a[start];
a[start] = a[rightmark];
a[rightmark] = temp;

//Return the position of the pivot
return rightmark;
}





Alternet Partition( ) function

int Partition(int a[],int start,int end)
{
int i, j, pivot, temp;
i=start+1;
//Make the first element as pivot element.
pivot = a[start];

for(int j=start+1 ; j <= end ; j++)
{
/* Rearrange the array by putting elements which are less than pivot on one side and which are greater than on other. */
if ( a[j] < pivot)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i=i+1;
}
}
//Put the pivot element in its proper place.
temp=a[start];
a[start]=a[i-1];
a[i-1]=temp;

//Return the position of the pivot
return (i-1);
}


ABOUT US

QuestionSolves.com is an educational website that helps worldwide students in solving computer education related queries.

Also, different software like Visual Studio, SQL Server, Oracle etc. are available to download in different versions.

Moreover, QuestionSolves.com provides solutions to your questions and assignments also.


MORE TOPIC


Windows Command

UNIX Command

IGNOU Assignment Solution

IGNOU Question Paper Solution

Solutions of Different Questions


WHAT WE DO


Website Devlopment

Training

Home Learning

Provide BCA, MCA Projects

Provide Assignment & Question Paper Solution


CONTACT US


Follow Us