In the previous article, we learned about the bubble sort algorithm that iterates through a collection repetitively and arranges the items into ascending or descending order. Continuing with that, in this article, we will explore the selection sort algorithm that uses a different approach for sorting the elements. In selection sort, the algorithm selects an element, compares it with other elements, and sorts them.
Selection sort is also a basic sorting algorithm that helps you understand the fundamentals of sorting in programming. Understanding this algorithm can help you solve various complex programming problems.
Selection Sort Algorithm
The Selection Sort is another basic algorithm that sorts an unsorted collection by selecting the minimum (for ascending order) or the maximum (for descending order) item and comparing it with others repetitively to sort the collection.
Demonstration
Let’s try to understand how selection sort works by considering an array of 5 elements [4, 7, 3, 1, 9]. The items in the array are arranged randomly and must be sorted into ascending order. Let’s break down this into steps:
Round 1:
First, find the minimum value in the array, i.e., 1. It is at index 3.
Swap the element to the first index, i.e., 1 is moved to the 0 index. The array becomes [1, 7, 3, 4, 9].
Round 2:
Find the minimum value in the unsorted part of the array, i.e., 3. It is at index 3.
Move 3 to index 1. Our array becomes [1, 3, 7, 4, 9].
Round 3:
The smallest element in the unsorted array is 4 which is at index 3. Move it to the lowest index of the unsorted array i.e. 2. The array becomes [1, 3, 4, 7, 9].
Our array is already sorted in just 2 rounds. If there are more unsorted elements, the selection sort algorithm will repeat the above steps unless the collection is sorted. Now that you understand how Selection sort works in background, let’s implement it in programming:
using System;
using System.Collections.Generic;
class Sorting {
public static void SelectionSort(int[] numbers)
{
int items = numbers.Length; //Getting the length of the array
for(int i = 0; i< items-1; i++) //Looping through the array
{
int min_index = i;
for(int j = i+1; j<items; j++) //For comparing the comparing elements
{
if(numbers[j] < numbers[min_index]) //if the element at j is smaller than the element at the minimum index
{
min_index = j;//set the min_index as j
}
}
if (min_index != i) //if the smallest element is not present at index i
int temp = numbers[i];
numbers[i] = numbers[min_index]; // swap the elements
numbers[min_index] = temp;
}
}
}
static void Main() {
int[] nums = {4, 7, 3, 1, 9};
Console.WriteLine("Array Before Sorting: ");
for(int i=0; i<nums.Length; i++)
{
Console.Write(nums[i] + " ");
}
Console.WriteLine("\nArray After Sorting:");
SelectionSort(nums);
for(int i=0; i<nums.Length; i++)
{
Console.Write(nums[i] + " ");
}
}
}
In the above code, I have first declared a conditional statement to find the index of the minimum value. Once the minimum value is found, it is compared to its preceding value. If it is smaller than that, the value is swapped. Else it remains as is.
Selection Sort VS Bubble Sort
Although the Selection sort and Bubble sort algorithms have the same space and time complexities, the selection sort is a better choice when it comes to efficiency. Let’s compare both algorithms briefly.
Number of Swaps
When it comes to the swaps, the Selection sort performs fewer swaps than the Bubble sort as it swaps only once per round. On the other hand, the Bubble sort performs multiple swaps in a round which can be costly in certain situations.
Stability
Bubble Sort is a stable sorting algorithm when you implement it correctly. It only swaps the elements if they are strictly in the incorrect order. The Selection sort on the other hand is unstable algorithm as it swaps the minimum element with the current position and it can change the relative order of the equal elements.
In more practical scenarios, the merge sort, and quick sort algorithms are preferred compared to the bubble sort and selection sort. They are efficient in handling larger datasets and require less time to perform swapping and sorting operations.
In the next 2 articles, we will explore the merge sort and quick sort algorithms and see how to implement them in C#.
