Searching and Sorting 575
other elements marked in a circle and sorted temporarily. Sorted elements inside the square 'y' are
shown.
Time Complexity
The performance of sorting algorithm depends upon the number of iterations and time to compare
them. The first element is compared with the remaining n- 1 elements in pass 1. Then n-2 elements
are taken in pass 2. this process is repeated until the last element is encountered. The mathematical
expression for these iterations will be equal to
(n-l)+(n-2 )+...+(n- (n -1)). Thus the expression
become n*(n-1)/2.
Thus, the number of comparisons is proportional to (n2). The time complexity of selection sort is
O (n2).
Comparison with Other Methods
1) This method requires more number of comparisons than quick sort and tree sort.
2) It is easier to implement than other methods such as quick sort and tree sort. The performance
of the selection sort is quicker than bubble sort.
Consider the elements 2, 6, 4, 8, and 5 for sorting under selection sort method.
1) In pass 1, select element 2 and check it with the remaining elements 6, 4, 8, and 5. There is no
smaller value than 2 hence the element 2 is placed at the first position.
2) Now, select element 6 for comparing with remaining (n-2) elements i.e., 4,8, and 5. The smaller
element is 4 than 6. Hence we swap 4 and 6 and 4 is placed after 2.
3) Again we select the next element 6 and compared it with the other two elements 8,5 and swapping
is done between 6 and 5.
4) In the next pass element 8 is compared with the remaining one element 6 . In this case, 8 is
swapped with 6.
5) In the last pass the 8 is placed at last because it is the highest number in the list.
Fig. 16.4 Selection sort
576 Programming and Data Structures
16.5 Write a program to sort elements of an array using selection sort.
#include <stdio.h>
# include cconio.h>
main()
{
int nums[15], p«0,q,r,num,t,small;
clrscr();
printf("How many elements to sort?: ");
scanf("%d",&num);
printf("Enter %d elements: ",num);
while (pcnum)
scanf("%d", &nums[p++]);
for (p*0; pcnum-1; p++)
{
small a p;
for(r*p+l; rcnum;r++)
if (nums [small] > nums [r])
small a r ;
if ( p la small )
{
t a nums [p];
nums [p] a nums[small];
nums [small] a t ;
}
printf("nAft«r %d pass elements are: n,p+l);
qaO;
while (q< num)
printf(" %d ", nums[q++]);
}
printf("nSorted elements are: ");
P=0;
while( p c num)
printf("%d ", nums[p++]);
}
OUTPUT:
How many elements to sort?: 5
Enter 5 elements: 8 6 4 2 5
After 1 pass elements are: 2 6 4 8 5
After 2 pass elements are: 2 4 6 8 5
After 3 pass elements are: 2 4 5 8 6
After 4 pass elements are: 2 4 5 6 8
Sorted elements are: 2 4 5 6 8
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.