Selection Sort Algorithm

Selection Sort Algorithm

Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array.

Assume that the array A=[7,5,4,2] needs to be sorted in ascending order.

The minimum element in the array i.e. 2 is searched for and then swapped with the element that is currently located at the first position, i.e. 7. Now the minimum element in the remaining unsorted array is searched for and put in the second position, and so on.

Flow Chart of Selection Sort

How Selection Sort Works?

Set the first element as minimum.

Compare minimum with the second element. If the second element is smaller than minimum, assign second element as minimum.

Compare minimum with the third element. Again, if the third element is smaller, then assign minimum to the third element otherwise do nothing. The process goes on until the last element.

After each iteration, minimum is placed in the front of the unsorted list.

For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated until all the elements are placed at their correct positions.

Complete steps for selection sort with example

Lets have the array with unsorted element.

Now look at the steps used to sort the above array.

Selection Sort Algorithm

selectionSort(array, size)
repeat (size – 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
end selectionSort

C Program example for Selection sort

// Selection sort in C
#include <stdio.h>
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int array[], int size)
{
for (int step = 0; step < size – 1; step++)
{
int min_idx = step;
for (int i = step + 1; i < size; i++)
{
if (array[i] < array[min_idx])
min_idx = i;
}
swap(&array[min_idx], &array[step]);
}
}
void printArray(int array[], int size)
{
for (int i = 0; i < size; ++i)
{
printf(“%d “, array[i]);
}
printf(“\n”);
}
int main()
{
int data[] = {20, 12, 10, 15, 2};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf(“Sorted array in Acsending Order:\n”);
printArray(data, size);
}

Complexity of Selection Sort

Number of comparisons:(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2 nearly equals to n2

Complexity = O(n2)

Also, we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is n*n = n2.

Time Complexities:

• Worst Case Complexity: O(n2)If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
• Best Case Complexity: O(n2)It occurs when the the array is already sorted
• Average Case Complexity: O(n2)

Space Complexity of selection sort:

Space complexity is O(1) because an extra variable temp is used.

Posts to Review:

write a C program to reverse the number C Program to find prime number C program to calculate simple interest using function Bar chart program in c