Sensort - Learn Selection Sort

A sorting algorithm which splits the input array in 2 parts, the sorted part and the unsorted part. In every iteration, the minimum element is found from the unsorted array and appended to the sorted array.

Selection Sort is a basic and simple sorting algorithm. It is named so, as in every iteration, the correct element to be inserted next in the sorted array is selected from the unsorted array and then added to it.

Selection sort starts sorting the array from left to right. The last element left in the unsorted array is assumed to be at the sorted position.

Characteristic	Value	Notes
Average Time Complexity	O(n²)	Same for worst case
Best Time Complexity	O(n²)	For a sorted array as well
Space Complexity	O(1)	No extra storage required

Advantages:

Easier to understand and more intuitive

Disadvantages:

Inefficient for arrays with large input due to poor time complexity and no possible optimization.

Implementation

Selection sort should be easy to visualize from the animations. In every iteration the smallest bar of the unsorted array(red) is picked(green) and added at the end of the sorted array(pink). The logic of the selection_sort() function is pretty simple, it works with 2 iterators:

itr_1: Holds the index of the end of sorted array after which the the unsorted array will begin
itr_2: Traverses the unsorted array to find the smallest element from the unsorted array.

> Initially, end of sorted array = -1^th index. And the traversal will begin from the 0^th index of array to the last.
> Traverse itr_2 in the unsorted array and find the minimum value among them
> Swap this smallest value with the end of sorted array to replace the last element.
> Repeat continuously for the next element of the unsorted array.

Code for the following in C++:

            
// function for selection sort
void selection_sort(int arr[], int n) {

	// i = itr_1 , j = itr_2
  for(int i = 0; i < n - 1; ++i) {

	int min_idx = i;

    // traverse the un-sorted array
    for(int j = i + 1; j < n; ++j) {
      if(arr[j] < arr[min_idx]) {
        min_idx = j;
      }
    }

    // swap the values
    swap(arr[i], arr[min_idx]);    
  }
	return;
}