Quick sort
Quick sort sorts a list based on the divide and conquer strategy.
In quick sort algorithm we divide the list into two sub-list, sort these sub-lists and recursively until the list is sorted,
The basic steps of quick sort algorithm are as follows;
Step 1: Choose a key element in the list which is called a key.
Step 2: Reorder the list with the rule that all elements which are less than the key comes before the pivot and so that all elements greater than the key come after it, after the partitioning the key in its final position
Step 3: Recursively re,order two sub-lists the sub-list of lesser elements and the sub-list of greater elements.
Quick Sort Code in C
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 10
int arr[size];
void create()
{
int i;
for(i=0;i<size;i++)
{
arr[i]=random(1000);
}
}
void display()
{
int i;
for(i=0;i<size;i++)
{
printf("%d\t",arr[i]);
}
}
void quick(int lb,int ub)
{
int i,j,key,temp;
int flag=0;
i=lb+1;
j=ub;
key=arr[lb];
while(flag==0)
{
if(lb<ub)
{
while(arr[i]<key)
{
i=i+1;
}
while(arr[j]>key)
{
j=j-1;
}
if(i<j)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
else
{
flag=1;
temp=arr[lb];
arr[lb]=arr[j];
arr[j]=temp;
}
}
else
{
return;
}
}
quick(lb,j-1);
quick(j+1,ub);
}
void main()
{
int lb=0;
int ub=size-1;
create();
display();
quick(lb,ub);
display();
}
* Special Thanks to Maulin & Naresh & Also Using Reference Book Data Structures by Tremblay
----------------------------
RAJ SOLUTION'S
www.rajsolution.com
www.sahinraj.blogspot.com
No comments:
Post a Comment