578 Programming and Data Structures
16.6 Write a program to sort a given array by using the exchange sort.
#include<Btdio.h>
#include<conio.h>
main()
{
int a [ 5 ] , i , j , temp;
c l r s c r ( ) ;
p r i n t f ( "Enter the elements of an array: ”);
fo r (i * 0 ;i< 5 ;i+ + )
sc a n f( "%d", & a[i] );
fo r (i«=0;i<5;i++ )
{
f o r (j = i ; j< 4 ;j + + )
{
i f ( a [ i ] > a [ j + l ] )
{
temp=a [ i ] ;
a [i ] »a [j+1 ] ;
a [j+1] =temp;
}
}
}
p r i n t f ( "Sorted elements in ascending ord er: ;
fo r(i = 0 ;i< 5 ;i+ + )
p r i n t f (" %d ”, a [ i ] ) ;
}
OUTPUT:
Enter the elements of an array: 9 5 14 3
Sorted elements in ascending order: 1 3 4 5 9
Explanation In the above program an array of five elements is declared. The variable j and i are
loop variables. The variable i is used in the outer loop and j is used in the inner loop. The
' i f () ' statement checks the number, it compares every current element denoted by Ith location
with (/+l)th element. If the number z-th is greater, it is assigned to temp. The smaller number is
assigned to /th location and temp (holds larger number) assigned to (/+l)th location. Thus, by exchange
elements are sorted.
Time Complexity
The performance of bubble sort in worst case is n (n-1)/2. This is because in the first pass n -1
comparisons or exchanges are made; in the second pass n - 2 comparisons are made. This is carried
out until the last exchange is made. The mathematical representation for these exchanges will be
equal to (/?-!)+( /t-2)+...+(rt-(/7-2)). Thus the expression becomes n*(n-l)/2.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.