Selection sort is one of the simplest sorting algorithms in data structures. It operates by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning. This process continues until the entire array is sorted.
How Does Selection Sort Work?
The working of selection sort can be understood through the following steps:
- Step 1: Find the minimum element in the unsorted portion of the array.
- Step 2: Swap this minimum element with the first element in the unsorted portion.
- Step 3: Move to the next position and repeat steps 1 and 2 until all elements are sorted.
The selection sort algorithm divides an array into two portions: sorted and unsorted. Initially, the sorted portion is empty, while the unsorted portion contains all elements. With each iteration, an element from the unsorted portion is selected and placed at its correct position in the sorted portion.
Example:
To illustrate how selection sort works, let’s consider an array [7, 4, 2, 9, 1].
- First iteration:
- The minimum element in [7, 4, 2, 9, 1] is ‘1’.
- ‘1’ is swapped with ‘7’, resulting in [1, 4, 2, 9, 7].
- Second iteration:
- The minimum element in [4, 2, 9, 7] is ‘2’.
- ‘2’ is swapped with ‘4’, resulting in [1, 2, 4, 9, 7].
- Third iteration:
- The minimum element in [4, 9, 7] is ‘4’.
- ‘4’ is already in its correct position.
- Fourth iteration:
- The minimum element in [9, 7] is ‘7’.
- ‘7’ is swapped with ‘9’, resulting in [1, 2, 4, 7, 9].
After performing all iterations and sorting the array using selection sort, the final sorted array is [1, 2, 4, 7, 9].
Time Complexity of Selection Sort:
The time complexity of selection sort is O(n^2), where ‘n’ is the number of elements in the array. This algorithm performs a quadratic number of comparisons and swaps to sort the array.
Advantages and Disadvantages of Selection Sort:
Advantages:
- Simple implementation and easy to understand.
- No extra space required other than the input array itself.
Disadvantages:
- Inefficient for large datasets due to its time complexity.
- The number of comparisons remains the same even if the array is already sorted.
Overall, selection sort is a basic sorting algorithm that can be useful for small datasets or as an educational tool to understand the concept of sorting.
It’s important to note that there are more efficient sorting algorithms available, such as merge sort and quicksort, which have better time complexities for large datasets.