Selection Sort in Data Structure
Free Data Structures and Algorithms courses with real-time projects Start Now!!
Selection sort is a simple sorting where the control searches for the smallest element and puts it in the first index. In each iteration, it searches for the smallest element and puts it in its correct final position. The position of sorted elements does not change after swapping.
- Selection sort is an unstable algorithm
- Modification of Selection sort is possible to be a stable algorithm.
Procedure for Selection Sort
1. Swap the first element with the smallest element in the array. We have now n-1 elements to sort
2. Find the smallest element in array from array[1] to array [n-1] and swap it with the second position
3. For the next element, find the smallest element in the remaining array and swap it.
Selection Sort Algorithm
Step 1: for k = 1 to n-1 step 2: set small = arr[k] step 3: set pos = k step 4: repeat for j = k+1 to n -1 if small > arr[j] set small = arr[j] set pos = j [end of if] [end of loop] step 5: swap a[k] with arr[pos] [end of loop] step 6: Stop
Pseudocode for Selection Sort
selectionSort(array): for i=0 to length(array): Minimum element = array[0] for each unsorted elements: if element < Minimum element element = new minimum swap minimum element with first unsorted position end selectionSort
Working of Selection Sort
Let’s Sort the following array by the insertion sort technique.
1st Iteration:
2nd Iteration:
3rd Iteration:
4th Iteration:
5th Iteration:
6th Iteration:
7th Iteration:
8th Iteration:
In the above example, we can see the change in the order of three elements with the same value of ‘9’ after sorting. Hence we can conclude that selection sort is not a stable algorithm.
Selection sort implementation in C
#include<stdio.h> int smallest_element(int[],int,int); void main () { int a[] = {32, 6, 76, 52, 29, 11, 94, 62, 73, 81}; int i,pos,temp; for(i=0;i<10;i++) { pos = smallest_element(a,10,i); temp = a[i]; a[i]=a[pos]; a[pos] = temp; } printf("sorted array:\n"); for(i=0;i<10;i++) { printf("%d ",a[i]); } } int smallest_element(int a[], int n, int i) { int smallest,position,j; smallest = a[i]; position = i; for(j=i+1;j<10;j++) { if(a[j]<smallest) { smallest = a[j]; position=j; } } return position; }
Selection sort implementation C++
#include<iostream> using namespace std; int smallest_element(int[],int,int); int main () { int a[] = {32, 6, 76, 52, 29, 11, 94, 62, 73, 81}; int i,pos,temp; for(i=0;i<10;i++) { pos = smallest_element(a,10,i); temp = a[i]; a[i]=a[pos]; a[pos] = temp; } cout << "sorted array:\n"; for(i=0;i<10;i++) { cout << " " << a[i]; } } int smallest_element(int a[], int n, int i) { int smallest,position,j; smallest = a[i]; position = i; for(j=i+1;j<10;j++) { if(a[j]<smallest) { smallest = a[j]; position=j; } } return position; }
Implementation of Selection Sort in JAVA
public class SelectionSort { void selectionSort(int array[]) { int len = array.length; for (int j = 0; j < len - 1; j++) { int min_pos = j; for (int i = j + 1; i < len; i++) { if (array[i] < array[min_pos]) { min_pos= i; } } int temp = array[j]; array[j] = array[min_pos]; array[min_pos] = temp; } System.out.println("Sorted Array: "); for (int i = 0; i < len; i++) { System.out.print(array[i] +" "); } } public static void main(String args[]) { int[] array = { 32, 6, 76, 52, 29, 11, 94, 62, 73, 81 }; SelectionSort ss = new SelectionSort(); ss.selectionSort(array); } }
Selection sort implementation in Python
def selectionSort(array, length): for i in range(length): min_pos = i for j in range(i + 1, length): if array[j] < array[min_pos]: min_pos = j (array[i], array[min_pos]) = (array[min_pos], array[i]) array = [32, 6, 76, 52, 29, 11, 94, 62, 73, 81] length = len(array) selectionSort(array, length) print('Sorted Array:') print(array)
Complexity of Selection Sort
iteration | comparisons |
1 | (n-1) |
2 | (n-2) |
3 | (n-3) |
. | . |
. | . |
. | . |
n-1 | 1 |
Total number of comparison :
(n-1) + (n-2) + (n-3) ………. + 1
= n(n-1)/2 ≈ n^2 ( complexity)
1. Best Case Complexity
Array is already sorted.
2. Average Case Complexity
elements in the array are jumbled i.e. they are neither in ascending or descending order.
3. Worst-Case Complexity
Array is sorted in the opposite of the required order.
4. Space complexity
An extra variable, temp, is used to swap the variables.
scenario | complexity | |
Time Complexity | Average case | O(n^2) |
Best case | O(n^2) | |
Worst case | O(n^2) | |
Space complexity | O(1) |
Applications of Selection Sort
Selection sort can be used:
1. when a small dataset needs to be sorted
2. in algorithms where the cost of swapping does not matter.
3. in scenarios where there is a need to check all elements.
4. In situations where the cost of writing in flash memory matters. It has a write/swap complexity of O(n) while that of bubble sort is O(n^2).
Conclusion
Selection sort is an unstable algorithm that is good for sorting small datasets. Time taken by this algorithm is more but it is beneficial to scenarios where we have memory limitations. Selection sort is simple and easy to implement. In further articles, we see other sorting techniques which are based on different algorithms techniques.
You give me 15 seconds I promise you best tutorials
Please share your happy experience on Google