Selection Sort is a simple sorting algorithm that divides the input list into a sorted and an unsorted region. The algorithm repeatedly selects the smallest (or largest, depending on the order) element from the unsorted region and swaps it with the first element in the unsorted region.

1. Divide the list into a sorted and an unsorted region.
2. Find the minimum (or maximum) element in the unsorted region.
3. Swap the found element with the first element in the unsorted region.
4. Expand the sorted region and repeat steps 2-3 until the entire list is sorted.

   Insertion-Sort(A, N)
1. for k <--- 1 to N - 1
2.     Min( A, K, N, LOC )
3.         exchange A[ k ] <---> A[ LOC ]
4. Stop

   Min(A, K, N, LOC)
1. Min = A[ k ]
2. LOC = k
3. for j <--- k + 1 to N
4.     if ( Min > A[ j ] )
5.         Min = A[ j ]
6.         Loc = j
7. Return LOC

#include <stdio.h>

int array[10];

void input_array(int[], int);
void print_array(int[], int);
void selection_sort(int[], int);
int minimum(int[], int, int);

void main()
{
    input_array(array, 5);
    selection_sort(array, 5);
    print_array(array, 5);
}

void input_array(int A[], int N)
{
    int i;

    printf("Enter the values for sorting :-\n");
    for (i = 1; i <= N; i++)
    {
        printf("Value %d :", i);
        scanf("%d", &A[i]);
    }
}

void print_array(int A[], int N)
{
    int i;

    printf("\nSorted array is : {");
    for (i = 1; i <= N; i++)
    {
        printf("%d, ", A[i]);
    }
    printf("}");
}

void selection_sort(int A[], int N)
{
    int k;
    int loc;
    int temp;

    for (k = 1; k <= N - 1; k++)
    {
        loc = minimum(A, k, N);
        temp = A[k];
        A[k] = A[loc];
        A[loc] = temp;
    }
}

int minimum(int A[], int K, int N)
{
    int j;
    int min = A[K];
    int loc = K;

    for (j = K + 1; j <= N; j++)
    {
        if (min > A[j])
        {
            min = A[j];
            loc = j;
        }
    }

    return loc;
}

1. Initialization:

   • Divide the list into two regions: a sorted region (initially empty) and an unsorted region (the entire list).

2. Selection:

   • Find the minimum (or maximum) element in the unsorted region.

3. Swap:

   • Swap the found element with the first element in the unsorted region, expanding the sorted region.

4. Iteration:

   • Repeat steps 2-3 for the remaining unsorted elements until the entire list is sorted.

Consider an example:

Original List: 5, 3, 8, 4, 2

Pass 1:

• Find the minimum (2) and swap it with the first element (List: 2, 3, 8, 4, 5)

Pass 2:

• Find the minimum (3) in the unsorted region (List: 2, 3, 8, 4, 5)

Pass 3:

• Find the minimum (4) and swap it with the first element in the unsorted region (List: 2, 3, 4, 8, 5)

Pass 4:

• Find the minimum (5) and swap it with the first element in the unsorted region (List: 2, 3, 4, 5, 8)

• Worst, average, and best case: O(n^2)

• O(1) - Selection Sort is an in-place sorting algorithm.

• Selection Sort is not stable, meaning the relative order of equal elements may change after sorting.

Feel free to use or modify this Markdown document as needed!