Created
May 2, 2011 18:12
-
-
Save mbalayil/952063 to your computer and use it in GitHub Desktop.
Quick Sort using recursion in C
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** Divide : Partition the array A[low....high] into two sub-arrays | |
* A[low....j-1] and A[j+1...high] such that each element | |
* of A[low....j-1] is less than or equal to A[j], which | |
* in turn is is less than or equal to A[j+1...high]. Compute | |
* the index j as part of this partitioning procedure. | |
* Conquer : Sort the two sub-arrays A[low....j-1] and A[j+1....high] | |
* by recursive calls to quicksort | |
**/ | |
#include<stdio.h> | |
int main() | |
{ | |
int arr[20], n, i; | |
printf("Enter the size of the array\n"); | |
scanf("%d", &n); | |
printf("Enter the elements to be sorted\n"); | |
for(i = 0; i < n; i++) | |
scanf("%d", &arr[i]); | |
quicksort(arr, 0, n-1); | |
printf("Sorted array\n"); | |
for(i = 0; i < n; i++) | |
printf("%d ", arr[i]); | |
return 0; | |
} | |
void quicksort(int *arr, int low, int high) | |
{ | |
int pivot, i, j, temp; | |
if(low < high) { | |
pivot = low; // select a pivot element | |
i = low; | |
j = high; | |
while(i < j) { | |
// increment i till you get a number greater than the pivot element | |
while(arr[i] <= arr[pivot] && i <= high) | |
i++; | |
// decrement j till you get a number less than the pivot element | |
while(arr[j] > arr[pivot] && j >= low) | |
j--; | |
// if i < j swap the elements in locations i and j | |
if(i < j) { | |
temp = arr[i]; | |
arr[i] = arr[j]; | |
arr[j] = temp; | |
} | |
} | |
// when i >= j it means the j-th position is the correct position | |
// of the pivot element, hence swap the pivot element with the | |
// element in the j-th position | |
temp = arr[j]; | |
arr[j] = arr[pivot]; | |
arr[pivot] = temp; | |
// Repeat quicksort for the two sub-arrays, one to the left of j | |
// and one to the right of j | |
quicksort(arr, low, j-1); | |
quicksort(arr, j+1, high); | |
} | |
} |
//plz see the problem with my quicksort code..
include<stdio.h>
int n;
main()
{
int data[20],i;
scanf("%d",&n);
fflush(stdin);
for(i=0;i<n;i++)
{
scanf("%d",&data[i]);
}
fflush(stdin);
qsort(data,0,n-1);
for(i=0;i<n;i++)
{
printf("%d ",data[i]);
}
}
qsort(data,start,end)
int data[],start,end;
{
int p;
if(start>=end)return;
else {
p=partition(data,start,end);
qsort(data,start,p);
qsort(start,p+1,end);}
}
int partition(data,left,right)
int data[],left,right;
{
int i=left,j=right,pivot=data[left];
int temp;
while(i<j){
while((i<j)&&(data[i]<pivot))i++;
while((i<j)&&(data[j]>=pivot))j--;
if(i<j){
temp=data[i];
data[i]=data[j];
data[j]=temp;}
}
if(data[j]<=pivot)
return(j);
else
return(j-1);
}
How does it exit the recursion?
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
//plz see the problem in the followi
ng code of quick sort
include<stdio.h>
int n;
main()
{
int data[20],i;
scanf("%d",&n);
fflush(stdin);
for(i=0;i<n;i++)
{
scanf("%d",&data[i]);
}
fflush(stdin);
qsort(data,0,n-1);
for(i=0;i<n;i++)
{
printf("%d ",data[i]);
}
}
qsort(data,start,end)
int data[],start,end;
{
int p;
if(start>=end)return;
else {
p=partition(data,start,end);
qsort(data,start,p);
qsort(start,p+1,end);}
}
int partition(data,left,right)
int data[],left,right;
{
int i=left,j=right,pivot=data[left];
int temp;
while(i<j){
while((i<j)&&(data[i]<pivot))i++;
while((i<j)&&(data[j]>=pivot))j--;
if(i<j){
temp=data[i];
data[i]=data[j];
data[j]=temp;}
}