E Systematic Approach to Data Structures using C-

11.13
yoid merge_sort(int a[], int low, int high)
int mid;
if(low <high)
mid =(low + high)/2; /* Divide the array into equal parts /
merge _sort (a, low, mid); * Sort the left part of array /
merge _sort (a, mid + 1, high); /* Sort the right part of the array "/
simple_merge(a, low, mid, high); *Merge left part and right part /

void main(O,
{
int a[MAX]; I/Elements to be sorted
int n; I/Number of elements to sort
int ||Used as an index to access the elements

endI;
cout << "Enter the number of elements to sort" <<
cin >>n;

<< endl;
cout << "Enter the elements to sort"
for (i=0;i<n; i+t)
cin >> a[Ü:
merge_sort(a, 0, n-1);
is" << endl;
cout <<"The sorted vector
for (i=0; i<n; itt) endl;
cout <<ai] <<

exchange sort)
11.5 Quick sort (Partition technique is to
on large set of data. The first step in this
works very well of the key elenent
This sorting technique into two sub-tables such that theelements towards lelt greater than key
partition the given table element are
and elements towards rightof the key in the let sub
are less than the k¹y
element
partitioned into two sub tables. The elentents
array is For example,
element. Afler this sten, the right sub table are greater than the key elennent.
elements in the
lable are lesser and partition may look liko shown
below:
afier
he array obtained
72 65 98 88 78
36: 37 11 10 42 42
42
11.14 P Sorting and searching
4637D 10 272 GS 45g23
low i j, high
42 37 11 98 36 72 65 10 88 78 (42 >37 so, increment i)
42 37 11 98 36 72 65 10 88 78 (42 > 11 so, increment i)
i
j: high
42 37 11 98 36 72 65. 10 88 78 (Since 42 <98 stop
incrementing iand 05]> oLi1
compare 42 with a] which is
78)41c4
42 37 11 98 36 72 65 10 88 78(42 <78 so, decrement j)
42 37 11 98 36 72 65 10 88 78( 42 <88 so, decrement j)
i
42 37 11 98 36 72 65 10 88 78 (since 42<10 is false
stop decrementing j)
Since i <j, exchange a[i] with a[i] and repeat the proess
42 37 11 10 36 72 65 98 88 78 (42 > 10 so, increment i)

42 37 11 10 36 72 65 98 88 78 (42 >36 so, increment i)

i
42 37 11 10 36 72 65 98 88 78 (42 > 72 is false so
stop incrementingiand
compare 42 with ai]ie., 98)
ij
42 37 11 10 36 72 65 98 88 78 (42 <98 so, decrement j)
i j
42 37 11 10 36 72 65 98 88 78 (42 < 65 so, decrement j)
42 37 11 10 36 72 65 98 88 78(42 < 72 so, decrement j)
j i
42 37 11 10 36 72 65 98 88 78 (42 < 36 is false.)

Since i exceedsj, exchange a[low] with a•i]. Now, the contents of the array will be
36 37 11 10 42 72 65 98 88 78
<42 42
Fig, 11.5.1 Tracing of partitioning the array
Here, the elements towards left of the key item 42 are less than 42 and elenments towards ng
1 are gyeater. Now, sort the lefl 'sub-table and right-sub-table. After sorting the left and rngat su
tables the position of the key item i.e., 42 is not changed and the entire array is sorted. 1he s
process is repeatedly applied for the left sub-table and right-sub tables, till the elements u ce
the sub tables are in their appropriate positions so that the entire array is sorted.
 SystematicApproach to Data Structures using C- 11.15
the array into two sub tables,two index variables i andj are used. The index variable
To partition
e ts to low+/ where low points to the first element and the index variable j points to high
hich points to the last element. The item a[low] is used as a key element. This key item has to
ke nlaced in a position j such that a[k] <* ai] for low <= k<jand ai] a[] for j+1 <1<+
hich. This can be achieved by comparing the item key with a[i] and aj]. Keep incrementing the
index i whenever key a[i]. Immediately when this condition fails, keep decrementing the
index j whenever key < a[j]. At this stage if i is less than j, exchange a[i] with a[j] and repeat the
process. If iis greater than or equal to j then exchange a[low] with aj] and return j lesswhich gives
the position of the partitioned element. Now the elements towards left of a[i] are all than a[i]
andelemnents towards right of it are greater. Consider the elements shown below:
37 11 98 36 72 65 10 88 78

In a table or sub-table, the leftmost element is considered to be a key element always. In the items
shown above, 42 is the key item. Manipulate this table such that elements towards left of 42 are
lesser and elements towards right of it are greater. The fig. 11.5.1 shows how partition can be done
for the above elements. This can be done by keep incrementing i byl whenever key is greater than
statement is
or equal to a[i] and while updating i, it should not exceed high and the equivalent
shown below:
while (i<high && key > a[i) it;
Once this condition is false, keep decrementingj by l as long as key is less than a[i]. This can be
achieved using the statement
while (key < aj] ) j-;
Once the control comes out of this loop, if i is less than j, exchange a[i] with ai]. Otherwise,
exchange a[low] with a[i] and returnj as the position of the partitioning item. The complete C
function to partition the array as explained is shown below:
Example 11.5.1: Function to partition the array for quick sort
int partition(int a[],int low,int high)
int ij,temp,key;
key a[low], i= lowt1,j =high;
while(1)
while (i< high && key >= a[i]) it+;
while (key <aj] ) j
if (i<j)
temp a[i], a[i] = a[j], ai]=temp;
else

temp =alow], a[low]=a), ai]=temp;

return j;
 11.16 D Sorting and searching
After partitioning, the original table is partitioned into two sub tables as shown below:
{36 37 11 10 } and {72 65 98 88 78 }
The same procedure is applied to each of these sub tables repeatedly until the table is completely
sorted. This method of sorting is called partition exchange sort or quick sort. The divide
and
conquer approach is used to sort each of these sub-tables as discussed in merge sort. Using this
approach, after partitioning the table into two sub-tables, sort the left sub-table recursively and
theD sort the right sub-table recursively. Note that as in merge sort, there
the left sub-table and right sub-table. The C function to sort using quick sortisisno need of merging
shown below:
Example 11.5.2: Function to sort the numbers in ascending order using quick sort
void quicksort(int a(]. int low, int high)
int j;
if (low <high )
jpartition(a,low high); Partition the array into 2 subtables */
quicksort(a,lowj-l ): 1*Sort the left part of the array
quicksort(aj+1high); Sort the right part ofthe array /

The complete C program to arrange numbers in ascending order using quick

sort is shown below:
Example 11.5.3: Cprogram to sort the numbers in ascending order using quick
sort
#include <stdio.h>
/* Inchude: Example 11.5.1: Function to partition the
array for quick sort */
7 Include: Example 11.5.2: Function to sort the numbers in ascending order using quick sort *
void main()
int i,n,a(20};
printf("Entr the value for nln");
scanf("%d",&n);
printf("Enter the numbers to be sortedn");
for (i-0; i<n, it) scanf("%d",&ail);
quicksort(a,0,n-1);
printf("Thesorted array isln");
for(i-0;i<n, it) printf("%dn",ali]);