CPP-programs/quicksort.c at master · Sushmitha-Deva/CPP-programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<stdio.h>


int a[200];

 void QuickSort(int ,int);
 int Partition(  int , int);

int main()
{
	int i,j,n;

	printf("\n Enter the size");
	scanf("%d",&n);


	printf("\n ENter %d Integers",n);

	for(i=0;i<n;i++)
	scanf("%d",&a[i]);


	for(i=0;i<n;i++)
	printf("%d ",a[i]);

	QuickSort(0,n-1);


   	printf("\n Sorted array\n");
    for(i=0;i<n;i++)
	printf("%d ",a[i]);

   return(0);
}


void QuickSort(int p , int q)
{
	int j;

	if(p<q)
	{
		j=Partition( p, q);
		QuickSort(p,j-1);
		QuickSort(j+1,q);
	}


}

int Partition( int beg ,int end)
{
	int pivot=a[beg];

	int i=beg, j=end ,temp;

	while(i<=j)
	{
		while((a[i]<=pivot) && (i<=end))
			i++;

		while( (a[j]>pivot) && (j>=beg))
			j--;

		//swap a[i] and a[j]

		if(i<j)
		{
			temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}

	}

	//swap pivot and a[j];
		temp=a[beg];
		a[beg]=a[j];
		a[j]=temp;

	return (j);
}