582 Programming and Data Structures
Time Complexity
The efficiency of quick sort depends upon the selection of pivot. The pivot can bifurcate the list
into compartments. Sometimes, the compartments are having the same sizes or dissimilar sizes.
Assume a case in which pivot is at middle. Thus, the total elements towards lift of it and right are
equal.
We can express the size of list with the power of 2. The mathematical representation for the size
is n-2s. The value of s can be calculated as log2 n.
After the first pass is completed there will be two compartments having equal number of elements
that is, m/2 elements are on the left side as well as right side. In the subsequent pass, four portions
are made and each portion contains n/A elements. In this way, we will be proceeding further until
the list is sorted. The number of comparison in different passes will be as follows.
Pass 1 will have n comparisons. Pass 2 will have 2*(n/2) comparisons. In the subsequent passes
will have 4*(rc/4), 8*(n/8) comparisons and so on. The total comparisons involved in this case
would be O (/i)+0 (n)-fO (n)+--*+s. The value of expression will be O (n log n).
Thus time complexity of quick sort is O (n log n).
Comparison with Other Methods
1) This is the fastest sorting method among all.
2) It is somewhat complex, so a little difficult to implement than other sorting algorithms.
16.10 TREE SORT
In binary tree, we know that the elements are inserted according to the value greater or less in
betweenjiode and the root in traversing. If the value is less than traversing node then, insertion is
done at left side. If the value is greater than traversing node, it is inserted at the right side. The
elements of such a tree can be sorted. This sorting involves creation of binary tree and then in order
traversing is done. Few examples are illustrated based on the tree such as inorder tree and Heap
sort.
16.8 Write a C program to insert nodes into a binary tree and to traverse in pre-order.
# include <stdio.h>
# include cconio.h>
struct tree
{
long num;
struct tree * le ft _ t ;
struct tree *r ig h t _t ;
} ;
struct tree * node=NULL;
struct tree ^ in s e rt(str u c t tree *, long ) ;
void p r e o r d e r (struct tree * );
main ()
{
Searching and Sorting 583
int d;
c l r s c r ( ) ;
p r in tf (■n Enter a Number ( 0 to stop: " ) ;
while (1)
{
scanf ("% d",& d);
i f (da*:0) break;
n od e *in sert(n o de ,d );
}
p rin tf ("n Tree in preorder sequence: " ) ;
pre o rd er(n o de );
return 0;
)
struct tree *in sert (struct tree *node, long d ig it )
{
i f (nods*sHULL)
{
no de*(struct t re e *)m a llo c (s iz e o f(stru c t t r e e ));
node- > le f t_t*node- >right_t»NULL;
node- >num*digi t ;
}
else
i f (digit<node->num)
n o d e -> le ft_t «in s e rt (n o d e -> le ft_t, d i g i t ) ;
else i f (digit>node->num)
node- > r i g h t t ■in s e r t (node- > rig h t_ t , d ig i t ) ;
else i f (digit~«node->num)
{
p u ts( "D uplicates nodes ■ ); e x i t (0 ); }
return (no de);
}
void p r e o r d e r ( struct tree *tree)
{
i f ( tree 1-NULL)
{
p r in tf ("%41d " , tree->num );
p r e o r d e r ( t r e e - > l e f t _ t ) ;
p r e o r d e r ( tr e e -> rig h t_ t
) ;
}
>
584 Programming and Data Structures
OUTPUT;
Enter a Number ( 0 to stop: 13 4 2 9 0
Tree in preorder sequence: 1 3 2 4 9
Heap Sort
In heap sort, we use the binary tree in which the nodes are arranged in specific prearranged order.
The rule prescribes that each node should have bigger value than its child node. The following
steps are to be followed in heap sort.
1) Arrange the nodes in the binary tree form.
2) Node should be arranged as per specific rules.
3) If the inserted node is bigger than its parent node then replace the node.
4) If the inserted node is lesser than its parent node then do not change the position.
5) Do not allow entering nodes on right side until the child nodes of the left are fulfilled.
6) Do not allow entering nodes on left side until the child nodes of the right are fulfilled.
7) The procedure from step 3 to step 6 is repeated for each entry of the node.
Consider the numbers 56, 23, 10, 99, 6, 19, 45, 45, 23 for sorting using heap. Sorting process is
illustrated in Fig. 16.7.
1) At first, we pick up the first element 56 from the list. Make it as the root node.
2) Next, take the second element 23 from the list. Insert this to the left of the root node 56. Refer to
Fig. 16.7 (2).
3) Then take the third element 10 from the list for insertion. Insert it to the right of the root node.
4
) Take the fourth element 99. Insert it to the left side of node 23. The inserted element is greater
than the parent element hence swap 99 with 23. But the parent node 56 is smaller than the child
node 99 hence 99 and 56 are swapped. After swapping 99 becomes the root node. This is shown
in Fig. 16.7 (4) and (5).
5) Consider the next element 6 to insert in the tree. Insert it at the left side . There exists a left node
hence insert it to the right of 56. Refer to Fig. 16.7 (6).
6) Element 19 is inserted to the right side of 99 because the left side gets full. Insert the element 19
to the right side of node 10. However, the parent element is lesser than the child hence swap 19
with 10.
7) Now element 45 is to be inserted at the right side of 19. However, the parent element is having
value lesser than the child element hence swap 45 with 19. Refer to Fig. 16.7 (9) and (10).
8) Now the right side is fully filled hence add the next element 45 to the left. The element 45 is
inserted at the last node of left i.e., 23. However, the parent element is having value lesser than
the child element hence swap 45 with 23. Refer to Fig. 16.7 (11) and (12).
9) Insert the last element 23 to the left side node i.e. 45. The left of 45 is already filled hence insert
element 23 at the right of 45. Refer to Fig. 16.7 (13).
10) At last, we get a sorted heap tree, as shown in Fig. 16.7 (13).
Searching and Sorting 585
586 Programming and Data Structures
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.