Selection Sort

Selection Sort

A selection sort is a sorting techniqlue in which successive elements are selected in order and paced into their proper sorted positions.

By starting from the first element and using a nest of for loops, a pass through the array is made to locate the minimum value.

Once this is found, it 1s placed in the first position of the array (position 0). Then the remaining elements is made to find the

next smallest element, which is placed in the second position (position 1), and so on. Once the next to last element is

compared with the last element, all the elements have been sorted into ascending order.

The algorithm works as follows:

• Find the minimum value in the list.
• Swap it with the value in the first position.
• Repeat the above steps for the remainder of the list (starting at the second position and advancing each time).

Algorithm for Selection Sort

This algorithm sorts the array list with n elements

1. Initialization,
2. Set loc=o
3. Repeat through step 7 while loc
   
4. Set j=loc+1
5. Repeat through step 6 while j
   
6. If list[loc]>list[j]
7. Interchange list[loc] and list[ j ]
8. i=i+1
9. loc=loc+1
10. Exit

Efficiency of Selection Sort

In the selection sort, the first pass requires (n-1) comparisons to fix the minimum element to its location i.e. location o, the second pass requires (n-2) comparisons to fix the next minimum element to location 1, ..., kth pass requires (n-k) comparisons to fix the kth minimum element at its location (k-1) and the last pass requires only one comparison to be fixed at the last position of the array.
Therefore total number of comparisons:
f(n) = (n-1) + (n-2) +  + (n-k) +  + 3 + 2 + 1 = n*(n-1)/2
Thus,  f(n)= O(n^2).
In case of selection sort,
Worst case complexity = Best case complexity = Average case complexity = O(n^2).

C Program For Selection Sort

#include <stdio.h>
void selection_sort(int[], int);
int main()
{
    int list[100], n, i;
    printf("\nHow many elements in the array:");
    scanf("%d", &n);
    scanf("%d", &n);
    printf("\nEnter %d values to sort:", n);
    for (i = 0; i < n; i++)
        scanf("%d", &list[i]);
    selection_sort(list, n);
    printf("\nThe sorted list is:");
    for (i = 0; i < n; i++)
        printf("%d\t", list[i]);
    return 0;
}
void selection_sort(int list[], int n)
{
    int temp, loc, j;
    for (loc = 0; loc < n - 1; loc++)
    {
        for (j = loc + 1; j < n; j++)
        {
            if (list[loc] > list[j])
            {
                temp = list[loc];
                list[loc] = list[j];
                list[j] = temp;
            }
        }
    }
#include <stdio.h>
    void selection_sort(int[], int);
    int main()
    {
        int list[100], n, i;
        printf("\nHow many elements in the array:");
        scanf("%d", &n);
        scanf("%d", &n);
        printf("\nEnter %d values to sort:", n);
        for (i = 0; i < n; i++)
            scanf("%d", &list[i]);
        selection_sort(list, n);
        printf("\nThe sorted list is:");
        for (i = 0; i < n; i++)
            printf("%d\t", list[i]);
        return 0;
    }
    void selection_sort(int list[], int n)
    {
        int temp, loc, j;
        for (loc = 0; loc < n - 1; loc++)
        {
            for (j = loc + 1; j < n; j++)
            {
                if (list[loc] > list[j])
                {
                    temp = list[loc];
                    list[loc] = list[j];
                    list[j] = temp;
                }
            }
        }
    }

Related Posts

Insertion Sort

Merge Sort

Bubble Sort

Selection Sort

Quick Sort

C Program For Bubble Sort | C Programming

C Program For Selection Sort | C Programming

C Program For Quick Sort | C Programming

C Program For Merge Sort | C Programming

C Program for Insertion Sort | C Programming