Programming and Data Structures

574 Programming and Data Structures

while(q<num)

{

r°num s[q];

fo r (p «q -l;p > «0 && r<n um s[p];p--)

nums [p+1]=nums[p];

nums [p + 1 ]«r ;

p r i n t f (" Element %d inserted in appropriate place

" # r) ;

p-0;

while (p<xuim)

p rin tf("% d ", nums[p++]);

p rin tf;

q++;

}

p rin tf("S o rt e d elements are: " ) ;

fo r (p « 0; p < num; p++)

p rin tf("% d ", nums[p]) ;

}

OUTPUT;

Enter number of elements: 5

Enter 5 elements: 4 6 2 1 8

Element 6 inserted in appropriate place 4 6 2 1 8

Element 2 inserted in appropriate place 2 4 6 1 8

Element 1 inserted in appropriate place 1 2 4 6 8

Element 8 inserted in appropriate place 1 2 4 6 8

Sorted elements are: 1 2 4 6 8

Explanation In the above program, the nested w h ile loops are used. The variable q is initialized

with 1 and p with 0. The variable r inside the w h ile loop is used to take elements from the array

and the same element is compared with the remaining elements. The ' f o r ' loop inside the whi l e

loop executes if p>=zero and r (recently assigned value of array element) less than other elements,

the insertion carried out.

16.7 SELECTION SORT

The selection sort is nearly same as exchange sort. Assume we have a list containing n elements. By

applying selection sort, the first element is compared with the remaining (n-1) elements. The smallest

element is placed at the first location. Again, the second element is compared with the remaining

(n-2) elements. If the item found is lesser than the compared elements in the remaining n-2 list

than the swap operation is done. In this type, the entire array is checked for the smallest element

and then swapped.

Figure 16.4 illustrates the process of sorting elements by selection sort. In each pass, one element

is sorted and kept at the left. Initially the elements are temporarily sorted and after next pass, they

are permanently sorted and kept at the left. Permanently sorted elements are covered with squares

and temporarily with encircles. Element inside the circle 'O' is chosen for comparing with the