Selection Sort | CrackEase

Selection Sort

Selection sort is a simple comparison-based sorting algorithm. The list is conceptually divided into two parts: the sorted part at the left end and the unsorted part at the right end. The algorithm repeatedly selects the smallest (or largest, for descending order) element from the unsorted portion and moves it to the end of the sorted portion.

Steps for Selection Sort

Select the smallest value in the unsorted portion.
Swap that smallest value with the first element of the unsorted portion (i.e., place it at the boundary between sorted and unsorted).
Move the boundary one position to the right (exclude the newly placed element) and repeat until the array is sorted.

Approach of Selection Sort

You are given an unsorted array which we will convert into a sorted array using selection sort. At each iteration you find the smallest element in the unsorted portion and swap it with the element at the current starting index of the unsorted portion.

For example, with array [72, 50, 10, 44, 8, 20], first find the smallest (8) and swap it with index 0 (72). Next, exclude index 0 and find the next smallest (10) and swap with index 1 (50). Continue until all elements are placed.

This repeats until the entire array is sorted (smallest to largest).

Code

  
// C program for implementation of selection sort
// Time Complexity : O(n^2)
// Space Complexity : O(1)
// Best, Avg, Worst Cases : All O(n^2)
#include <stdio.h>

/* Display function to print values */
void display(int array[], int size) 
{ 
    int i; 
    for (i = 0; i < size; i++)
        printf("%d ", array[i]);

    printf("\n"); 
}

// The main function to drive other functions 
int main() 
{ 
    int array[] = {72, 50, 10, 44, 8, 20}; 
    int size = sizeof(array)/sizeof(array[0]);

    printf("Before sorting: \n"); 
    display(array, size);

    int i, j, min_idx, temp;  

    // Loop to iterate over the array 
    for (i = 0; i < size-1; i++)  
    {  
        // Assume current index is the minimum
        min_idx = i;  
        for (j = i + 1; j < size; j++){
            if (array[j] < array[min_idx])  
                min_idx = j;  
        }
        // Swap the found minimum element with the first element of unsorted part             
        temp = array[min_idx];
        array[min_idx] = array[i]; 
        array[i] = temp;
    }
    printf("\nAfter sorting: \n"); 
    display(array, size); 

    return 0; 
}

  
// Selection sort in C++
#include <iostream>
using namespace std;

// function to swap positions of two elements
void swapValues(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

// function to print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; i++) {
    cout << array[i] << " ";
  }
  cout << endl;
}

void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) {
      // Select the minimum element in each loop.
      if (array[i] < array[min_idx])
        min_idx = i;
    }
    // put min at the correct position
    swapValues(&array[min_idx], &array[step]);
  }
}

// driver code
int main() {
  int data[] = {72, 50, 10, 44, 8, 20};
  int size = sizeof(data) / sizeof(data[0]);

  cout << "Before Sorting:\n";
  printArray(data, size);

  selectionSort(data, size);

  cout << "After Sorting:\n";
  printArray(data, size);

  return 0;
}

  
// Java Program for Selection Sort
// Time Complexity : O(n^2)
// Space Complexity : O(1)
class Main
{
    // Main method
    public static void main(String args[])
    {
        int arr[] = {72, 50, 10, 44, 8, 20};

        System.out.println("Before Sorting:");
        printArray(arr);

        selectionSort(arr);

        System.out.println("After Sorting:");
        printArray(arr);
    }

    static void selectionSort(int a[])
    {
        int len = a.length;      

        // One by one move boundary of unsorted sub-array
        for (int i = 0; i < len - 1; i++)
        {
            // Find the minimum element in unsorted array
            int min = i;
            for (int j = i + 1; j < len; j++)
                if (a[j] < a[min])
                    min = j;

            // Swap the found minimum element with the first element
            int temp = a[min];
            a[min] = a[i];
            a[i] = temp;
        }
    }

    // Prints the array
    static void printArray(int a[])
    {
        for (int i = 0; i < a.length; ++i)
            System.out.print(a[i] + " ");
        System.out.println();
    }
}

	
Before sorting: 
72 50 10 44 8 20
After sorting: 
8 10 20 44 50 72

Performance

Selection sort runs in O(n²) time for best, average and worst cases because of the two nested loops (search for min and swap). It performs well for small arrays or for use-cases where memory writes are costly (it performs at most n swaps).

Strengths

Performance does not depend on initial ordering of elements (always O(n²)).
Performs minimal number of swaps (useful where writes are expensive).

Weaknesses

Number of comparisons is O(n²), which is inefficient for large n.

Time Complexity Summary

Best	Average	Worst	Space Complexity
O(n²)	O(n²)	O(n²)	O(1)

Footer Content | CrackEase

→

←

Courses

Chapters

Data Structure

Sorting

Linked List

Stack

Queue

Tree

Selection Sort

Selection Sort