Selection Sort
Description
Selection Sort is a simple and intuitive sorting algorithm that works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning. The algorithm maintains two subarrays: one that is already sorted and another that is unsorted. In every iteration, the minimum element from the unsorted subarray is picked and moved to the sorted subarray.
How It Works
- Initialize the sorted portion as empty and unsorted portion as the entire array
- Find the minimum element in the unsorted portion
- Swap the found minimum element with the first element of the unsorted portion
- Move the boundary between sorted and unsorted portions one element to the right
- Repeat steps 2-4 until the entire array is sorted
Visualization
Click Start to begin visualization
Implementation
def selection_sort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Find the minimum element in remaining unsorted array
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap the found minimum element with the first element
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# Usage example
if __name__ == "__main__":
arr = [64, 34, 25, 12, 22, 11, 90]
print("Original array:", arr)
selection_sort(arr)
print("Sorted array:", arr)
#include <iostream>
#include <vector>
class SelectionSort {
public:
static void sort(std::vector<int>& arr) {
int n = arr.size();
// One by one move boundary of unsorted subarray
for (int i = 0; i < n - 1; i++) {
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// Swap the found minimum element with the first element
if (min_idx != i) {
std::swap(arr[min_idx], arr[i]);
}
}
}
};
// Usage example
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
std::cout << "Original array: ";
for (int num : arr) std::cout << num << " ";
std::cout << std::endl;
SelectionSort::sort(arr);
std::cout << "Sorted array: ";
for (int num : arr) std::cout << num << " ";
std::cout << std::endl;
return 0;
}
public class SelectionSort
{
public static void Sort(int[] arr)
{
int n = arr.Length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n - 1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[min_idx])
{
min_idx = j;
}
}
// Swap the found minimum element with the first element
if (min_idx != i)
{
(arr[min_idx], arr[i]) = (arr[i], arr[min_idx]);
}
}
}
// Usage example
public static void Main(string[] args)
{
int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
Console.WriteLine("Original array: " + string.Join(" ", arr));
Sort(arr);
Console.WriteLine("Sorted array: " + string.Join(" ", arr));
}
}
Complexity Analysis
| Case | Time Complexity |
|---|---|
| Best | O(n²) |
| Average | O(n²) |
| Worst | O(n²) |
Advantages and Disadvantages
Advantages
- Simple and easy to understand
- Performs well on small arrays
- In-place algorithm - requires no extra space
- Minimal number of swaps (O(n) swaps)
Disadvantages
- O(n²) complexity makes it inefficient for large lists
- Not stable - does not preserve the relative order of equal elements
- Does not adapt to the data in any way