When all the
items in a list are arranged in order, the middle value which divides the items
into two parts with equal number of items on either side is called the median.
Odd number of items have just one middle value while even number of items have
two middle values. The median for even number of items is therefore designated
as the average of the two middle values.
The major steps
for finding the median are as follows:
1. Read the items into an array while keeping a
count of the items.
2. Sort the items in increasing order.
3. Compute median.
The program and sample output are shown in
Fig.7.7. The sorting algorithm used is as follows:
1. Compare the first two elements in the
list, say a[1], and a[2]. If a[2] is smaller than a[1], then interchange their
values.
2. Compare a[2] and a[3]; interchange them if a[3] is smaller than a[2].
3. Continue this process till the last two
elements are compared and interchanged.
4. Repeat the above steps n-1 times.
In repeated
trips through the array, the smallest elements 'bubble up' to the top. Because
of this bubbling up effect, this algorithm is called bubble sorting. The
bubbling effect is illustrated below for four items.
During the first
trip, three pairs of items are compared and interchanged whenever needed. It
should be noted that the number 80, the largest among the items, has been moved
to the bottom at the end of the first trip. This means that the element 80 (the
last item in the new list) need not be considered any further. Therefore,
trip-2 requires only two pairs to be compared. This time, the number 65 (the
second largest value) has been moved down the list. Notice that each trip
brings the smallest value 10 up by one level.
The number of
steps required in a trip is reduced by one for each trip made. The entire
process will be over when a trip contains only one step. If the list contains n
elements, then the number of comparisons involved would be n(n-1)/2.
PROGRAM TO SORT A LIST AND FIND ITS MEDIAN
Program
#define N 10
main( )
{
int i,j,n;
float median,a[N],t;
printf("Enter the number of
items\n");
scanf("%d", &n);
/* Reading items into array a */
printf("Input %d values
\n",n);
for (i = 1; i <= n ; i++)
scanf("%f",
&a[i]);
/* Sorting begins */
for (i = 1 ; i <= n-1 ; i++)
{
/* Trip-i begins */
for (j = 1 ; j <= n-i ; j++)
{
if (a[j] <= a[j+1])
{ /* Interchanging values */
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
else
continue ;
}
} /* sorting ends */
/* calculation of median */
if ( n % 2 == 0)
median = (a[n/2] + a[n/2+1])/2.0
;
else
median = a[n/2 + 1];
/*
Printing */
for (i = 1 ; i <= n ; i++)
printf("%f ", a[i]);
printf("\n\nMedian is %f\n",
median);
}
Output
Enter the number of items
5
Input 5 values
1.111
2.222 3.333 4.444
5.555
5.555000
4.444000 3.333000 2.222000
1.111000
Median is 3.333000
Enter the number of items
6
Input 6 values
3
5 8 9
4 6
9.000000
8.000000 6.000000 5.000000
4.000000 3.000000
No comments:
Post a Comment