Selection Sort

Intuition

The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning. The largest element will end up at the last index of the array.

Approach

Select the starting index of the unsorted part using a loop with i from 0 to n-1.
Find the smallest element in the range from i to n-1 using an inner loop.
Swap this smallest element with the element at index i.
Repeat the process for the next starting index.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function for selection sort
    vector<int> selectionSort(vector<int>& nums) {
        // Loop through the unsorted array
        for (int i = 0; i < nums.size() - 1; i++) {
            /*Assume the current 
            index is the smallest*/
            int minIndex = i;
            
            // Find the index of the smallest element
            for (int j = i + 1; j <nums.size(); j++) {
                /*Update minIndex if smaller 
                element is found */
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
        
            // Swap only if minIndex is changed
            if (minIndex != i) {
                swap(nums[minIndex], nums[i]);
            }
        }
        return nums;
    }
};

int main() {

    vector<int> arr = {7, 5, 9, 2, 8};
    
    cout << "Original array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // Create an instance of the Solution class
    Solution s1;

    // function call for Selection Sort
    vector<int> sortedArr = s1.selectionSort(arr);

    cout << "Sorted array: ";
    for (int num : sortedArr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}
import java.util.*;
class Solution {

  public int[] selectionSort(int[] nums) {
    // Loop through unsorted part of the array (0 to n-2)
    for (int i = 0; i < nums.length - 1; i++) {
      /*Assume current element 
      is the minimum*/
      int minIndex = i;

      // Find actual minimum in unsorted part (i+1 to n-1)
      for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] < nums[minIndex]) {
          minIndex = j;
        }
      }

      // Swap only if minIndex changed
      if (minIndex != i) {
        int temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
      }
    }

    return nums;
  }
}

public class Main {

  public static void main(String[] args) {
    int[] arr = {7, 5, 9, 2, 8};

    System.out.print("Original array: ");
    for (int num : arr) {
      System.out.print(num + " ");
    }
    System.out.println();

    // create an instance of solution class
    Solution solution = new Solution();

    // function call for selection sort
    int[] sortedArr = solution.selectionSort(arr);

    System.out.print("Sorted array: ");
    for (int num : sortedArr) {
      System.out.print(num + " ");
    }
    System.out.println();
  }
}
class Solution:
    def selectionSort(self, nums):
        # Loop through unsorted part 
        # of the array (0 to n-2)
        for i in range(len(nums) - 1):
            ''' Assume current 
            element is minimum '''
            min_index = i

            '''Find actual minimum in 
            unsorted part (i+1 to n-1) '''
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[min_index]:
                    min_index = j

            ''' Swap only if minIndex 
            changed (optimization) '''
            if min_index != i:
                nums[i], nums[min_index] = nums[min_index], nums[i]

        return nums

# Main function to test the selection sort
if __name__ == "__main__":
    solution = Solution()
    nums = [64, 25, 12, 22, 11]
    sorted_nums = solution.selectionSort(nums)
    print("Sorted array:", sorted_nums)
class Solution {
    selectionSort(nums) {
        // Loop through unsorted part of the array (0 to n-2)
        for (let i = 0; i < nums.length - 1; i++) {
            // Assume current element is the minimum
            let minIndex = i;

            // Find actual minimum in unsorted part (i+1 to n-1)
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap only if minIndex changed (optimization)
            if (minIndex != i) {
                [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
            }
        }

        return nums;
    }
}

// Example usage:
const solution = new Solution();
console.log(solution.selectionSort([64, 25, 12, 22, 11]));

Complexity Analysis

Time Complexity: O(N²) where N is the length of the input array. The outer loop runs through each element, and the inner loop finds the smallest element in the unsorted portion of the array.

Space Complexity: O(1) as it is an in-place sorting algorithm and does not require additional storage proportional to the input size.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code