Selection Sort

Pseudocode:

• Take element in 0th position
• From 1st to (n-1)th position, find the smallest element and its index.
• If we found a smallest element, swap it with 0th position
• Repeat the above for all the positions
• NOTE: Selection sort basically means, fill the position of each index (starting from 0) by it's appropriate value (by choosing the minimum amount in the remaining indexes in each loop)

Psuedocode flow:

SelectionSort (A, n)

{

    for i = 0 to n -1 // we can do it till n-2, as n-1 will automatically have biggest element in its position

    {

        iMin = i
        for j = i+1 to n-1

         {

            if (A[j] < A[iMin])

                iMin = j
           }

            swap (A[iMin], A[i])

    }

}

C Code:

#include <stdio.h>

#define NELEMS(x) (sizeof (x)/sizeof(x[0]))

void swap(int *x, int *y)
{
    int t = *x;
    *x = *y;
    *y = t;
}

void display(int arr[], int size)
{
    int i;
    for (i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void selection(int arr[], int n)
{
    int i, j, iMin;

    for (i = 0; i < n - 1; ++i) { // no need for last iteration, as the biggest number will be there anyways (due to previous operation)
        iMin = i; // find the right element for this position
        for (j = i + 1; j < n; ++j) {
            if (arr[j] < arr[iMin]) {
                iMin = j;
            }
        }
        swap(arr + iMin, arr + i);
        display(arr, 7); // NELEMS wont' work as it will be converted as pointer _here_
    }
}

int main()
{
    int arr[] = { 21, 5, 22, 74, 0, 99, 18 };

    printf("UnSorted: ");
    display(arr, NELEMS(arr));

    selection(arr, NELEMS(arr));

    printf("Sorted: ");
    display(arr, NELEMS(arr));
    return (0);

}

Output:

UnSorted: 21 5 22 74 0 99 18

0 5 22 74 21 99 18

0 5 22 74 21 99 18

0 5 18 74 21 99 22

0 5 18 21 74 99 22

0 5 18 21 22 99 74

0 5 18 21 22 74 99

Sorted: 0 5 18 21 22 74 99

[NOTE that, each index starting from 0 (referred by iMin), will pull the appropriate value, by going through the loop]