Selection Sort Algorithm - [Updated]

Problem Statement: Given an array of N integers, write a program to implement the Selection sorting algorithm.

Examples:

Example 1:
Input: N = 6, array[] = {13,46,24,52,20,9}
Output: 9,13,20,24,46,52
Explanation: After sorting the array is: 9, 13, 20, 24, 46, 52

Example 2:
Input: N=5, array[] = {5,4,3,2,1}
Output: 1,2,3,4,5
Explanation: After sorting the array is: 1, 2, 3, 4, 5

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

Approach:

Find the minimum element in the unsorted array and swap it with the element at the beginning.
The inner loop selects the minimum element in the unsorted array .
In the below dry run,

Blue color represents unsorted array elements

The yellow color represents the elements to be swapped in an unsorted array

The green color represents the sorted array elements

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;
void selection_sort(int arr[], int n) {
  // selection sort
  for (int i = 0; i < n - 1; i++) {
    int mini = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[mini]) {
        mini = j;
      }
    }
    int temp = arr[mini];
    arr[mini] = arr[i];
    arr[i] = temp;
  }

  cout << "After selection sort: " << "\n";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";

}
int main() {
  int arr[] = {13,46,24,52,20,9};
  int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Before selection sort: " << "\n";
   for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  selection_sort(arr, n);
  return 0;
}

Output:

Before selection sort:
13 46 24 52 20 9
After selection sort:
9 13 20 24 46 52

Time Complexity: O(n^2) (nested for loops)

Space Complexity: O(1)

Java Code

public class selection_sort {
  public static void main(String args[]) {
    int arr[] = {13,46,24,52,20,9};
    int n = arr.length;
    System.out.println("Before selection sort:");
    for (int i = 0; i < n; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
    //selection sort
    for (int i = 0; i < n - 1; i++) {
      int mini = i;
      for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[i]) {
          mini = j;
        }
      }
      //swap
      int temp = arr[mini];
      arr[mini] = arr[i];
      arr[i] = temp;
    }

    System.out.println("After selection sort:");
    for (int i = 0; i < n; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
}

Output:

Before selection sort:
13 46 24 52 20 9
After selection sort:
9 13 20 24 46 52

Time Complexity: O(n^2) (nested for loops)

Space Complexity: O(1)

Special thanks to Rishiraj Girmal for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article