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

[].

Get *Programming and Data Structures* now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.