478 Programming and Data Structures
num[k] anum [h];
num[h] «txnp;
}
k++;
}
print£ ("n Sorted array : ");
for (k«0;k<8;++k)
printf (" %d ",num[k]);
OUTPUT:
Enter Numbers: 45879321
Sorted array: 12345789
Explanation In the above program eight numbers are entered. The while loops and for loop are
used to access the elements, compare and exchange the elements. Every element of an array is
compared with all successive elements. When a small element is found it is stored at the beginning
location in the array using tmp variable.
Time complexity: Time complexity of bubble sort is 0 (n 2). This is because in each pass the elements
that are compared are reduced by one. In the first pass n-1 comparisons are made. In the second
n -2, third n- 3 and so on. This can be expressed as (n-l)+ (n -2 )+ (n -3 )+ — +3+2+1. Thus total
comparisons made at the end of the algorithm would be n(n-1)/2. Thus average case analysis is
0(n2).
Comparison with other methods
1) This is the easiest sorting technique to implement.
2) It requires many comparisons so takes more time than quick sort and tree sort.
14.10 MER G IN G LISTS
Merging is £ process in which two lists are merged to form a new list. The new list is the sorted list.
Before merging individual lists are sorted and then merging is done. The procedure is very
straightforward. Consider the following program.
14.7 Write a program to create two array lists of integers. Sort and store elements of both of
them in the third list
# include <8tdio.h>
# include <conio.h>
# include <math.h>
main ()
{
int m,n,p,sum»0;
int listA[5],listB[5],listC[10]={0};
clrscr();
printf (”n Enter elements for first list : ");
for (ms0;m<5;m+ + )
Linear Data Structure 479
{
scanf (n%dn,&listA[m]);
if (listA[m]==0) m --;
sum=sum+abs (listA[m] ) ;
>
printf ("n Enter elements for second list : ”);
for (n=0;n<5;n++)
{
scanf ("%d", fielistB[n]);
if (listA[n]*=0) n--;
sumssumfabs(listB[n]);
}
p=n=m=0;
m*m- sum;
while (m<suxn)
{
for (n=0;n<5;n++)
{
if (m«B»listA [n] || m»«listB [n])
listC[p+ + ]*m;
if (m=«listA[n] && m«*listB[n])
listC[p++]*m;
}
m++;
}
puts (" Merged sorted list
2
");
for (n=0;n<10;++n)
printf (" %d ",listC[n]);
}
OUTPUT;
Enter elements for first list: 15 4-32
Enter elements for second list: 9 5 1 210
Merged sorted list:
-311224559 10
Explanation In the above program three arrays listA [], listB [] and listC [] are declared. Using for
loop elements in listA [] and listB [] are declared. The sum of all ten elements entered in both the lists
is taken in variable sum. The while and nested for loop check corresponding elements of both the
lists.
a) If one of the corresponding elements is same, that element is stored in the list[] array
b) If both the corresponding elements are same, they are stored in successive locations in.the listC
[].
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.