When it comes to sorting algorithms, one of the fundamental methods you might encounter is Selection Sort. It’s straightforward yet effective for small datasets. Let’s dive into how it works and why it’s useful.
How Selection Sort Works
Selection Sort operates by dividing the input array into two parts: the sorted part at the beginning and the unsorted part at the end. It repeatedly finds the smallest (or largest, depending on the order desired) element from the unsorted part and swaps it with the leftmost unsorted element. This process continues until the entire array is sorted.
Step-by-Step Breakdown
Let’s take a closer look at the Selection Sort algorithm implemented in C#:
public static void SelectionSort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
// Assume the element at index i is the smallest.
int minIndex = i;
// Find the index of the smallest element among the remaining elements.
for (int j = i + 1; j < array.Length; j++)
{
if (array[j] < array[minIndex])
{
minIndex = j;
}
}
// Swap the smallest element with the current element at index i, if necessary.
if (minIndex != i)
{
(array[minIndex], array[i]) = (array[i], array[minIndex]);
}
}
}
- Initialization: Start with assuming the first element as the smallest (
minIndex = i
). - Finding the Minimum: Iterate through the unsorted part of the array to find the index (
minIndex
) of the smallest element. - Swapping: If the found minimum element's index (
minIndex
) is not the same asi
, swap the elements at these indices. - Repeat: Continue this process for each element in the array until the entire array is sorted.
Example Application
Let’s apply Selection Sort to an example array and see how it sorts:
int[] array = { 18, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 };
// Output
// Initial array: 18 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// After sorting:
// Sorted array: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18