Searching and Sorting 579
Thus, the number of comparisons is proportional to (n2). The time complexity of bubble sort is
0 (n2).
16.9 QUICKSORT
It is also known as partition exchange sort. It was invented by C A R Hoare. It is based on partition.
Hence, the method falls under divide and conquer technique. The main list of element is divided
into two sub-lists. For example, suppose a list of X elements are to be sorted. The quick sort marks
an element in a list called as pivot or key. Consider the first element / as a pivot. Shift all the
elements whose value is less than J towards the left and elements whose value is grater than J to
right of J. Now, the key element divides the main list in to two parts. It is not necessary that
selected key element must be at middle. Any element from the list can act as key element. However,
for best performance preference is given to middle elements. Time consumption of the quick sort
depends on the location of the key in the list.
Consider the following example in which five elements 8, 9, 7, 6, 4 are to be sorted using quick
sort. Fig. 16.6 illustrates it.
Consider Pass 1 under which the following iterations are made. Similar operations are done in
Pass 2, Pass 3, etc.
In Iteration 1 the first element 8 is marked as pivot one. It is compared with the last element
whose value is 4. Here 4 is smaller than 8 hence the numbers are swapped. Iteration 2 shows the
swapping operation.
In the Iteration 3 and 4, the position of 8 is fixed. In Iteration 2, 8 and 9 are compared and
swapping is done after Iteration 2.
In Iteration 3,8 and 6 are compared and necessary swapping is done. After this, it is impossible
to swap. Hence, the position of 8 is fixed. Because of fixing the position of 8 the main list is divided
into two parts. Towards left of 8 elements having smaller than 8 are placed and towards the right
greater than 8 are placed.
Towards the right of 8 only one element is present hence there is no need of further swapping.
This may be considered under Pass 2.
However towards the left of 8 there are three elements and these elements are to be swapped as
per the procedure described above. This may be considered under Pass 3.
Pass 1
Fig. 16.6 Quick sort
Iteration 2
Iteration 3
Iteration 4
Iteration 1
580 Programming and Data Structures
16.7 Write a program to sort the array element using quick sort.
#in clu de<stdio. h>
#include <conio.h>
main()
{
in t nums[1 5 ],num,j=0;
in t q _ s o rt (in t * , in t ,in t );
in t show(int * , i n t , in t );
c l r s c r ( ) ;
p rin tf("E n te r the number of elements: " ) ;
sc a n f( "%d", &num);
p rin tf ("n Enter %d elements: ”,num);
while (j<num)
scanf("%d”,&nums[j++]);
q_sort(num s,0,num-1);
p r in tf("S o rte d l i s t is : n n) ;
show (nums, 0, num-1) ;
}
q _ s o r t(in t item s[ ] , in t low e r,in t upper)
{
in t key, temp, 1, r, key_placed®0;
in t show(int * , i n t , in t );
1=lower;
r=upper;
key=lower;
i f ( lower>=upper) return 0;
while (key_placed==0)
{
w h ile ( item s[key ]< sitem s[r] && key!=r)
r - - ;
i f ( key==r ) k ey_p laced=l;
i f ( item s[key] > items [r] )
{
temp=items [key] ;
items [key] =items [r ] ;
items [r] =temp;
key=r;
}
Searching and Sorting 581
w h ile ( items [ke y]>*item s[1] && 11*key ) 1++;
i f (key «=l) k ey_placed »l;
i f ( items[key] < items [1] )
{
tem p*item s[key];
items[key]aitems [1 ];
items [1] * temp;
ke y «l;
}
}
p r i n t f (" * Key Placed is %d -> ", item s[k ey ]) ;
show (items, lower, upper) ;
p r i n t f (" n " ) ;
q_sort (item s,.lower, k ey-1) ;
q_sort(item s,k ey +1 ,u pp er);
return 0;
}
show(int item s[ ] , in t lo w e r,in t upper)
{
w h ile (lower<supper)
prin tf("% d ", item s[lo w er++]) ;
return 0;
>
OUTPUT:
Enter the number of elements: 5
Enter 5 elements: 8 9 7 6 4
* Key Placed is 8 -> 4 6 7 8 9
* Key Placed is 4 -> 4 6 7
* Key Placed is 6 -> 6 7
Sorted list is: 4 6 7 8 9
Explanation In the above program the functions q _ s o r t () and show () are defined. In q _ s o r t
() elements are passed by value and address. The base address of an array nums is passed to
function q _ s o r t () . The variable num holds total number of elements. The q s o rt () function is
invoked recursively In the first execution of q _ s o r t (), value 0 is taken as lower key and (n - 1)
is taken as upper key If value of lower is greater than upper, the q _ s o r t () function terminates.
The value of upper variable is assigned to r. The value of r is decremented continuously until it
reaches to key value. When the value of variables key and r are same the key is placed to one and
the w h ile loop is terminated. The ' i f () ' statement carries swapping if element positioned at
value key is greater than element positioned at value r. The same procedure is carried out when
key is placed at one and swapping is carried out.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.