Selection Sort Algorithm

In this tutorial, you will learn how selection sort works. Additionally, you will discover working instances of selection sort in C, C++, Java, and Python.

In this article, you will learn-

1 What is Selection Sort?
2 How Selection Sort Works?
3 Selection Sort Algorithm
4 Python, Java, and C/C++ Examples
5 Complexity
- 5.1 Time Complexities:
- 5.2 Space Complexity:
6 Selection Sort Applications

What is Selection Sort?

Selection SORT is a comparison sorting algorithm that is used to sort a random list of items in ascending order. The comparison doesn’t need a great deal of additional space. It just requires one additional memory space for the temporal variable.

This is known as in-place sorting. The determination sort has a period complexity of O(n²) where n is the complete number of items in the list. The time complexity quantifies the number of iterations needed to sort the list. The list is divided into two partitions: The first list contains sorted items, while the second list contains unsorted items.

By default, the sorted list is unfilled, and the unsorted list contains all the elements. The unsorted list is then examined for the minimum value, which is then positioned in the sorted list. This process is repeated until all the values have been analyzed and sorted.

Selection sort is an algorithm that chooses the littlest element from an unsorted list in every iteration and places that element toward the start of the unsorted list.

How Selection Sort Works?

Set the first element as minimum.

2. Compare the minimum with the second element. In the event that the second element is smaller than the minimum, assign the second element as least.

Compare least and the third element. Once more, in the event that the third element is smaller, appoint least to the third element in any case do nothing The process goes on until the last element.

3. After every iteration, least is put in the front of the unsorted list.

4. For every iteration, indexing begins from the first unsorted element. Stage 1 to 3 are repeated until all the elements are set at their right positions.

selectionSort(array, size)
  repeat (size - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
end selectionSort

Python, Java, and C/C++ Examples

Python

# Selection sort in Python


def selectionSort(array, size):
   
    for step in range(size):
        min_idx = step

        for i in range(step + 1, size):
         
            # to sort in descending order, change > to < in this line
            # select the minimum element in each loop
            if array[i] < array[min_idx]:
                min_idx = i
         
        # put min at the correct position
        (array[step], array[min_idx]) = (array[min_idx], array[step])


data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)

Java

// Selection sort in Java

import java.util.Arrays;

class SelectionSort {
  void selectionSort(int array[]) {
    int size = array.length;

    for (int step = 0; step < size - 1; step++) {
      int min_idx = step;

      for (int i = step + 1; i < size; i++) {

        // To sort in descending order, change > to < in this line.
        // Select the minimum element in each loop.
        if (array[i] < array[min_idx]) {
          min_idx = i;
        }
      }

      // put min at the correct position
      int temp = array[step];
      array[step] = array[min_idx];
      array[min_idx] = temp;
    }
  }

  // driver code
  public static void main(String args[]) {
    int[] data = { 20, 12, 10, 15, 2 };
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(data);
    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

// Selection sort in C

#include <stdio.h>

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

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++) {

      // To sort in descending order, change > to < in this line.
      // Select the minimum element in each loop.
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // put min at the correct position
    swap(&array[min_idx], &array[step]);
  }
}

// function to print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

// driver code
int main() {
  int data[] = {20, 12, 10, 15, 2};
  int size = sizeof(data) / sizeof(data[0]);
  selectionSort(data, size);
  printf("Sorted array in Acsending Order:\n");
  printArray(data, size);
}

C++

// Selection sort in C++

#include <iostream>
using namespace std;

// function to swap the the position of two elements
void swap(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++) {

      // To sort in descending order, change > to < in this line.
      // Select the minimum element in each loop.
      if (array[i] < array[min_idx])
        min_idx = i;
    }

    // put min at the correct position
    swap(&array[min_idx], &array[step]);
  }
}

// driver code
int main() {
  int data[] = {20, 12, 10, 15, 2};
  int size = sizeof(data) / sizeof(data[0]);
  selectionSort(data, size);
  cout << "Sorted array in Acsending Order:\n";
  printArray(data, size);
}

Complexity

Cycle	Number of Comparison
1st	(n-1)
2nd	(n-2)
3rd	(n-3)
…	…
last	1

Number of comparisons: (n – 1) + (n – 2) + (n – 3) + ….. + 1 = n(n – 1)/2 almost equivalents to n².

Complexity = O(n2)

Likewise, we can analyze the complexity by just noticing the quantity of loops. There are 2 loops so the complexity is n*n = n².

Time Complexities:

Worst scenario Complexity: O(n²)

On the off chance that we need to sort in ascending order and the array is in descending order at that point, the worst scenario happens.

Best Case Complexity: O(n²)

It happens when the array is sorted

Average Case Complexity: O(n²)

It happens when the elements of the array are in jumbled order (neither ascending nor descending).

The time complexity of the selection sort is the equivalent of the whole cases. At each progression, you need to locate the minimum element and put it in the right spot. The minimum element isn’t known until the finish of the array isn’t reached.

Space Complexity:

Space complexity is O(1) on the grounds that an additional variable temp is used.

Selection Sort Applications

The selection sort is used when:

a little list is to be sorted
cost of swapping doesn’t make any difference
checking of all the elements is compulsory
cost of writing to memory matters like in flash memory (number of composes/swaps is O(n) as compared with O(n²) of the double sort)

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.