Skip to content

Instantly share code, notes, and snippets.

@mbalayil
Created May 2, 2011 18:12
Show Gist options
  • Star 9 You must be signed in to star a gist
  • Fork 9 You must be signed in to fork a gist
  • Save mbalayil/952063 to your computer and use it in GitHub Desktop.
Save mbalayil/952063 to your computer and use it in GitHub Desktop.
Quick Sort using recursion in C
/** 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);
}
}
@talwinder777
Copy link

//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;}

}

if(data[j]<=pivot)
    return(j);
else
return(j-1);

}

@talwinder777
Copy link

//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);

}

@o-dka
Copy link

o-dka commented Jan 12, 2022

How does it exit the recursion?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment