Quick Sort – GCC Program for Ubuntu

Click following links to download Quick Sort PPTs.

QuickSort – PPT 1

QuickSort – PPT 2

 

Implementation

//**************************************************************************
// Implementation of Quick Sort Algorithm using Divide & Conquer Method.
//**************************************************************************

#include<stdio.h>
#include<stdlib.h>

#define SIZE 10

void quick(int a[SIZE],int,int);
int partition(int a[SIZE],int,int);
void swap(int a[SIZE],int *,int *);
int n;

int main()
{
int i;
int a[SIZE];

printf(“\n************** Quick Sort Algorithm **************\n”);
printf(“\nEnter total numbers to sort:”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(“\n Enter %dth number: “,i+1);
scanf(“%d”,&a[i]);
}
quick(a,0,n-1);
printf(“\n\n*********** Sorted Array Is.. ****************\n”);
for(i=0;i<n;i++)
printf(“\t%d”,a[i]);
printf(“\n”);
return 0;
}

void quick(int a[SIZE],int low, int high)
{
int m,i;
if(low<high)
{
m=partition(a,low,high);
quick(a,low,m-1);
quick(a,m+1,high);
}
}

int partition(int a[SIZE],int low,int high)
{
int pivot=a[low],i=low,j=high;
while(i<=j)
{
while(a[i]<=pivot)
i++;
while(a[j]>pivot)
j–;
if(i<j)
swap(a,&i,&j);
}
swap(a,&low,&j);
return j;
}

void swap(int a[SIZE],int *i,int *j)
{
int temp;
temp=a[*i];
a[*i]=a[*j];
a[*j]=temp;
}