Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It divides the array into two parts: the sorted part and the unsorted part. During each iteration, the smallest (or largest) element from the unsorted part is selected and swapped with the first element of the unsorted part, expanding the sorted part by one element.

While Selection Sort is easy to understand and implement, it is not the most efficient for large datasets due to its time complexity of \(O(n^2)\).

Algorithm

Here are the steps of the Selection Sort algorithm:

  1. Start with the first element of the array as the current minimum.
  2. Compare the current minimum with the remaining unsorted elements to find the smallest element.
  3. Swap the smallest element with the first element of the unsorted part.
  4. Move the boundary between the sorted and unsorted parts one element to the right.
  5. Repeat steps 1-4 until the entire array is sorted.

Example

Let’s sort the array [5, 3, 8, 4, 2] using Selection Sort and explain each step:

Initial Array: