Selection Sort

The selection sort technique is based upon the extension of the minimum/maximum technique. By means of a nest of for loops a pass through the array is made to locate the minimum value. Once this found it is placed in the first position of array another the remaining elements is made to find next smallest element, which is placed in the second position and so on.

Once the next to last element is compared with the last element all the elements have been sorted into ascending order.

pass1:
find the location loc of the smallest in the list of n elements
a[1],a[2].....a[n] and then interchange a[loc]and a[1].then:

paas2:
find the location loc of the smallest in sublist of n-1 elements
a[2],a[3]...a[n] and then interchange a[loc] and a[2] then
a[1],a[2], is stored since a[1]<=a[2]

2

Pass3:
Find the location loc of the smallest in the sublist of n-2 elements
a[3],a[4]...a[n] and the interchange a[loc] and a[3] then
a[1],a[2]...a[3] is stored since a[2]<=a[3]

Pass n-1:
find the location loc of the smaller of the elements a[n-1],a[n] and the interchange
a[loc] and a[n-1] then
a[1],a[2]...a[n] is stored since a[n-1]<<=a[n]

Algorithm:

1. Set MIN to location 0
2. Search the minimum element in the list
3. Swap with value at location MIN
4. Increment MIN to point to next element
5. Repeat until list is sorted.

Example:

Take the array 35 65 30 60 20

Step1: scan 0-4, smallest is 20 , swap 35 and 20

35 65 30 60 20

Step2: scan 1-4, smallest is 30 , swap 65 and 30

20 65 30 60 35

Step3: scan 2-4, smallest is 35 , swap 65 and 35

20 30 65 60 35

Step4: scan 3-4, smallest is 60 , swap 60 and 65

20 30 35 60 65

Step1: all done here

20 30 35 60 65

Listing: Following program is showing the implementation of Selection sort Recursively.

/* 
* C Program to Implement Selection Sort Recursively 
*/ 
#include <stdio.h> 

void selection(int [], int, int, int, int); 

int main() 
{ 
    int list[30], size, temp, i, j; 

    printf("Enter the size of the list: "); 
    scanf("%d", &size); 
    printf("Enter the elements in list:\n"); 
    for (i = 0; i < size; i++) 
    { 
        scanf("%d", &list[i]); 
    } 
    selection(list, 0, 0, size, 1); 
    printf("The sorted list in ascending order is\n"); 
    for (i = 0; i < size; i++) 
    { 
        printf("%d  ", list[i]); 
    } 

    return 0; 
} 

void selection(int list[], int i, int j, int size, int flag) 
{ 
    int temp; 

    if (i < size - 1) 
    { 
        if (flag) 
        { 
            j = i + 1; 
        } 
        if (j < size) 
        { 
            if (list[i] > list[j]) 
            { 
                temp = list[i]; 
                list[i] = list[j]; 
                list[j] = temp; 
            } 
            selection(list, i, j + 1, size, 0); 
        } 
        selection(list, i + 1, 0, size, 1); 
    } 
} 

Output: 
    Enter the size of the list: 5 
    Enter the elements in list: 
    23 
    45 
    64 
    12 
    34 
    The sorted list in ascending order is 
    12  23  34  45  64