QUICK SORT USING C PROGRAM





Source code of simple quick sort implementation using array ascending order in c programming language

#include<stdio.h>

void quicksort(int [10],int,int);

int main(){
  int x[20],size,i;

  printf("Enter size of the array: ");
  scanf("%d",&size);

  printf("Enter %d elements: ",size);
  for(i=0;i<size;i++)
    scanf("%d",&x[i]);

  quicksort(x,0,size-1);

  printf("Sorted elements: ");
  for(i=0;i<size;i++)
    printf(" %d",x[i]);

  return 0;
}

void quicksort(int x[10],int first,int last){
    int pivot,j,temp,i;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);

    }
}

Output:
Enter size of the array: 5
Enter 5 elements: 3 8 0 1 2
Sorted elements: 0 1 2 3 8






1. Write a c program for bubble sort.
5. Write a c program for heap sort.
7. Write a c program for shell sort.

69 comments:

Debayan said...

Thanks, its working! But while executing the program, the 'Run' window is disappearing before showing the result. Although, I have fixed it. If anyone is having the same problem then see below:

In the main function, put "getch();" before the "return 0" statement.

To run the program on a fresh screen:
include this header file at the top--> #include
and inside main function type "clrscr();" just after the variable declaration is done.

Thanks...

Debayan said...

Sorry, I havn't completed the header file name above..
To run on a new window include this header file>>
#include
and inside main function type "clrscr();" just after the variable declaration is done.

Hope it works!!
Thanks...

debayan said...

conio.h

Anonymous said...

debaan every1 can understand that much if he is trying this program

AJJU said...

can u please explain how it works?

Anonymous said...

working well but difficult to understand. Can anyone send discription at lovababu.golthi@gmail.com

Thanks in advance.

Anonymous said...

if you want to show the result without getch()
go to window--->output

Anonymous said...

Add prototype "int quicksort(int,int,int);" after the header files also add "#include" too to use gtech();

Anonymous said...

/*Add prototype "int quicksort(int,int,int);" after the header files also add "#include" too to use gtech();*/

Anonymous said...

Add prototype "int quicksort(int,int,int);" after the header files also add "conio.h" header file too to use getch();

Unknown said...

//easy to understand

#include
#include
void quicksort(int [],int,int);
int main()
{
int x[20],size,i;

printf("Enter size of the array [<20]: ");
cin>>size;
printf("Enter %d elements: ",size);
for(i=0;i>x[i];
}
quicksort(x,0,size-1);

cout<<"Sorted elements: ";
for(i=0;i<size;i++)
cout<<x[i]<<" ";
getch();
return 0;
}
void quicksort(int x[],int first,int last)
{

int pivot,j,temp,i;
pivot=last;
for(i=first;i<pivot;i++)
{
if(x[pivot]<x[i])
{
temp=x[i];
x[i]=x[pivot-1];
x[pivot-1]=x[pivot];
x[pivot]=temp;
}
quicksort(x,first,pivot-1);
quicksort(x,pivot+1,last);
}
}

mukul rawal said...

if any one is looking to execute quick_sort using linked list , here's the code:

#include
#include
#include
struct linked_list
{
int data;
struct linked_list *link;
struct linked_list *prev;
};
typedef struct linked_list node;
void create(node *first);
void print(node *first);
node *quick_sort(node *first);
int count(node *first);
main()
{
node *first;
int x,n,i,j=0,m;
clrscr();
first=(node *)malloc(sizeof(node));
first->prev=0;

create(first);
printf("the numbers you have entered are :\n");
print(first);
n=count(first);
printf("\n the number of elements you have entered are: %d\n",n);
for(i=0;idata);
printf( " do you want to add more?(y=1/n=2)\n");
scanf("%d",&x);
if(x==2)
{
first->link=0;
}
else
{
first->link= (node *)malloc(sizeof(node));
first->link->prev=first;
create(first->link);
}
return;
}


void print(node *list)
{
if(list->link!=0)
{
printf("%d-> ",list->data);

if(list->link->link==0)
printf("%d",list->link->data);
print(list->link);
}
}



node *quick_sort(node *first)
{
node *save,*temp,*pivot,*p;
pivot=first;
temp=pivot->link;
while(temp!=0)
{
if(pivot->data > temp->data)
{
if(temp->link==0)
{
temp->prev->link=0;
temp->link=first;
first->prev=temp;
temp->prev=0;
first=temp;
break;
}
else
{
temp=temp->link;
temp->prev->link=first;
temp->prev->prev->link=temp;
first->prev=temp->prev;
temp->prev=temp->prev->prev;
first->prev->prev=0;
first=first->prev;
}
}

else
temp=temp->link;
}

pivot=pivot->link;
while(pivot->link!=0)
{
temp=pivot->link;
while(temp!=0)
{

if(pivot->data > temp->data)
{
if(temp->link==0)
{
temp->prev->link=0;
temp->link=pivot;
pivot->prev->link=temp;
temp->prev=pivot->prev;

break;
}
else
{
p=pivot->prev;
temp=temp->link;
temp->prev->link=pivot;
temp->prev->prev->link=temp;
pivot->prev=temp->prev;
temp->prev=temp->prev->prev;
pivot->prev->prev=p;
pivot->prev->prev->link=pivot->prev;

}
}

else
temp=temp->link;
}
pivot=pivot->link;
}
printf("\n first=%d\n",first->data);
return(first);
}


int count(node *first)
{
node *save=first;
int n=0;
while(save!=0)
{
n++;
save=save->link;
}
return(n);
}

keerthika said...

i want to write a program to sort weather condition for past 3 years for 5 cities using multi dimenstional arrays......

Anonymous said...

any one can know the program ...you please explain that....

siree said...

can u explain this program

Anonymous said...

easy to understand

Anonymous said...

it cant work....

ravi jadhav said...

#include
#include
void quick_sort(int*,int,int);
int partision(int*,int,int);
void main()
{
int i,n,j,a[50],lower=0,upper;
clrscr();
printf("Enter the size of an array=");
scanf("%d",&n);
upper=n-1;
printf("Enter the array elements=");

for(i=0;ilower)
{
i= partision(a,lower,upper);
quick_sort(a,lower,i-1);
quick_sort(a,i+1,upper);
}
}
int partision(int a[],int lower,int upper)
{
int i,p,q,temp;
p=lower+1;
q=upper;
i=a[lower];
while(q>=p)

{

while(a[p]i)

{

q--;
}
if(q>p)

{
temp=a[p];
a[p]=a[q];
a[q]=temp;
}
}
temp=a[lower];
a[lower]=a[q];
a[q]=temp;
return q;
}

varun kaulwar said...

void main()
{
char c=125;
pritnf("%d",c);
}

Anonymous said...

What is the time Complexity of this program???

Anonymous said...

please tell me program for quick sort in descending order.

Anonymous said...

u can press ctrl f5 or alt f5 to see the output in turboc without need of getch

Anonymous said...

what's the ending condition763

Anonymous said...

unable to open include file 'stdio.h' and 'conio.h'. what to do if this error comes?

Anonymous said...

this is not working.... wtf...!!!!

Anonymous said...

can you plss help me?.our final project is to make a program that implementing bubble, sort,insertion,quick and selection in one program.

Anonymous said...

buddy..msg me at anand.sinha85@gmail.com for any help on sorting(The guy who posted it as final year project).Although the project is one of the easiest you can get stil if you need any help kindly let me know.

Anonymous said...

is it working???

Anonymous said...

hey u forgot to include the exit condition for recursion so its going in an infinite loop

Anonymous said...

what is the space complexity of the main code(quick sort)....anybody pls help....

Sreehari H said...

Hi, thanks for the code.
Is there a way to find the position of the minimum from this?
If yes, please post that.
Thank you.

Anonymous said...

this will work if the numbers are identical...

Anonymous said...

after sorting, first element of the array is minimum

Anonymous said...

try this :
#include
#include

void display(int*,int);

void swap(int *a, int *b)
{
*a = *a - *b;
*b = *b + *a;
*a = *b - *a;
}

int partition(int *arr, int start, int end) //Partition the array
{
int pivot = start;
int left = start , right = end;
int i , pivotVal = arr[pivot];

while(left < right)
{
while(arr[left] <= pivotVal && left <=end )
left++;
while(arr[right] > pivotVal && right >= 0)
right--;
if(left < right)
swap(&arr[left], &arr[right]);
}

arr[start] = arr[right];
arr[right] = pivotVal;

return right;
}

void quick(int *arr, int start, int end)
{
int m;
if(start < end)
{
m = partition(arr,start,end); //Pivot
quick(arr,start,m-1);
quick(arr,m+1,end);
}
}



void display(int *arr,int nmem)
{
int i;
for(i = 0; i < nmem;i++)
printf("%d ",arr[i]);
printf("\n");
}

int main()
{
int arr[]={12,32,2,56,34,23,67,122};
int nmem = sizeof(arr)/sizeof(int);

quick(arr, 0, nmem - 1);
display(arr,nmem); //Sorted array
}

Anonymous said...

add these headers"stdio.h" and "stdlib.h"

Anonymous said...

o(n)

Anonymous said...

no it isnt going as the recursive calls are included in if condition, examine the codwe carefully

Anonymous said...

That's the spirit kid, Bharat Patidar

Anonymous said...

Your code is in a straight vertical line, like a arrow in an eye.
Above code is well formated.

Bharat Patidar

Anonymous said...

Hi there,
Trying to be smart ha,
I don't think anybody is going to read that code
But well done. Keep it

Bharat Patidar

Unknown said...

while(x[i]<=x[pivot]&&i<last)

here if we replace i<last with i<=last...will it make much of a difference.?

Unknown said...

time complexity is O(1)

Anonymous said...

FUnny its called a project,we call it a single Lab work !

Anonymous said...

ha..ha..funny!

Anonymous said...

buddy..msg me at anand.sinha85@gmail.com for any help on sorting(The guy who posted it as final year project).Although the project is one of the easiest you can get stil if you need any help kindly let me know.

Unknown said...

can anyone explain the quick sort program which is given above plzz

Unknown said...

An arrow in the eye

Unknown said...

how to run bubble sort program in c++? i need the exact code of the program.

Unknown said...

This program works in recursive manner. At first you need to know how recursive function works

Unknown said...

How to make source code of simple quick sort implementation using array descending order in c programming language?

Unknown said...

I need your Help someone.

Chandan said...

Obtain the passenger details for a railway reservation system. Sort the passenger records based on train number and destination city using quick sort.

tamasha said...

#include
#include
void quicksort(int [],int,int);
int main()
{
int x[20],size,i;

printf("Enter size of the array [<20]: ");
scanf("%d",&size);
printf("Enter %d elements: ",size);
for(i=0;i<size;i++)
{
scanf("%d",&x[i]);
}

quicksort(x,0,size-1);
printf("Sorted elements: ");
for(i=0;i<size;i++)
printf("%d",x[i]);
return 0;
}
void quicksort(int x[],int first,int last)
{

int pivot,j,temp,i;
pivot=last;
for(i=first;i<pivot;i++)
{
if(x[pivot]<x[i])
{
temp=x[i];
x[i]=x[pivot-1];
x[pivot-1]=x[pivot];
x[pivot]=temp;
}
quicksort(x,first,pivot-1);
quicksort(x,pivot+1,last-1);
}
}

Unknown said...

Go to option then directories and remove include and lib from last that's it

Unknown said...

not understand

GunnerUjjwol said...

what other modification in the code would I need to make if i initialise 'pivot=a[first]' (as the element itself)
rather tha 'pivot=first'(which sets the index value to pivot)

Unknown said...

plz tell me abt these two lines in brief...
quicksort(x,first,j-1);
quicksort(x,j+1,last);

Unknown said...

why to use c




Bobo said...

Please write finished work qsort..

Unknown said...
This comment has been removed by the author.
Unknown said...

//plz check my mistake in this quick sort program. i am not getting output
#include
int partition(int [],int ,int );
void qs(int [],int ,int );
int partition(int a[],int p,int r)
{
int i,j, t,x,temp;
x=a[r-1];
i=p-1;
printf("sid");
for(j=p;j<r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
t=a[j];
a[j]=a[i];
a[i]=t;

}

}
temp=a[i+1];
a[i+1]=a[r];
a[r]=temp;

return i+1;
}
void qs(int a[],int p,int r)
{
int q;
if(p<r)

q=partition(a,p,r);
printf("siddh");
qs(a,p,q-1);
qs(a,q+1,r);
}
int main()
{
int n,i,a[20];
printf("enter the size of array");
scanf("%d",&n);
printf("array element is");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}

printf("after sorting");
qs(a,i,n);
for(i=0;i<n;i++)
{
printf(" %d",a[i]);
}
}

Unknown said...

If you want to sort each city individually thanthan apply a sorting algorithm on each individual array. If you want to sort d full array than your better off copying the whole in another array, sorting it n copying d contents back.

Unknown said...
This comment has been removed by the author.
Unknown said...

//i can not find my mistake...pls any one help me...according to me there is no logical problem...bt something may me wrong in my program...pls pls help me//

#include
void quick(int [15],int,int);
void main()
{
int array[15],i,n;
printf("Enter no of elements to sort:\n");
scanf("%d",&n);
printf("Enter %d elements 1 by 1:\n",n);
for(i=0;ipivot)
{
c=array[i];
i=i+1;
}

if(c<pivot)
{
temp=array[index];
array[index]=c;
c=temp;
index++;
c=array[i];
i=i+1;
}
}
temp=array[index];
array[index]=c;
c=temp;

quick(array,left,index-1);
quick(array,index+1,right);
}

Unknown said...

//i can not find my mistake...pls any one help me...according to me there is no logical problem...bt something may me wrong in my program...pls pls help me//

#include
void quick(int [15],int,int);
void main()
{
int array[15],i,n;
printf("Enter no of elements to sort:\n");
scanf("%d",&n);
printf("Enter %d elements 1 by 1:\n",n);
for(i=0;ipivot)
{
c=array[i];
i=i+1;
}

if(c<pivot)
{
temp=array[index];
array[index]=c;
c=temp;
index++;
c=array[i];
i=i+1;
}
}
temp=array[index];
array[index]=c;
c=temp;

quick(array,left,index-1);
quick(array,index+1,right);
}

Unknown said...

Incorrect code ! Used cin function on c language

:D said...

thank you dude, JesusQuick

Unknown said...

i want the program code for quick sort without usinf function or recursion.i want function code of quick sort only in main function plzzzz any one can help me.

murugesan openssl said...

I have viewed following page on Wed 31-Jan-2024 IST
https://www.cquestions.com/2008/01/c-program-for-quick-sort.html
We can replace temporary variable using XOR operator to swap values:
temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
with:
if ( j != pivot )
{
arr[pivot] ^= arr[j];
arr[j] = arr[pivot] ^ arr[j];
arr[pivot] ^= arr[j];
}
...
arr[i] ^= arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] ^= arr[j];
...
Sample using double My Profile:
// /usr/bin/gcc.exe -g -Wall Quick_Sorting.c -o ./a.out
double murugesan = 900000000.2004;
double openssl = 900000000.2018;
printf( "murugesan %012.04f openssl %012.04f\n", murugesan, openssl);
*(int*)&murugesan ^= *(int*)&openssl;
*(int*)&openssl ^= *(int*)&murugesan;
*(int*)&murugesan ^= *(int*)&openssl;
printf( "murugesan %012.04f openssl %012.04f\n", murugesan, openssl);
/*
$ ./a.out
murugesan 900000000.2004 openssl 900000000.2018
murugesan 900000000.2018 openssl 900000000.2004
*/