Selection sort is a sorting algorithm, which allows you to arrange elements in a particular order.
Video Reference
Algorithm
steps to implement selection sort
- start
- pick smallest element index.
- swap with first element with smallest.
- again find out smallest element index out of remaining array elements.
- swap with second element with new smallest element.
- continue this process until we will get sorted array.
- end
Pseudo Code
selection_sort(arr, n) {
for i=0 to i=n-1
curr_min=i
for j=i+1 to j=n-1
if arr[curr_min]>arr[j]
curr_min=j
swap(arr[i], arr[curr_min])
}Time Complexity – O(n^2)
Best – O(n^2)
Worst – O(n^2)
Average – O(n^2)
Space Complexity – O(1)
Implementation C++/Java/Python
/**
* author: Heera Singh
* desc: Selection Implementation
*/
#include <iostream>
using namespace std;
void selection_sort(int arr[], int n) {
for (int i = 0; i < n; i++) {
int curr_min = i;
for (int j = i + 1; j < n; j++) {
if (arr[curr_min] > arr[j]) {
curr_min = j;
}
}
// swap
int t = arr[i];
arr[i] = arr[curr_min];
arr[curr_min] = t;
}
}
int main() {
int[] arr = { 14, 3, 2, 4, 1 };
int n = sizeof(arr)/sizeof(arr[0);
selectionSort(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
/**
* author: Heera Singh
* desc: Selection Implementation
*/
public class Main {
/**
* @param arr - array
* @param n - size
*/
static void selectionSort(int[] arr, int n) {
for (int i = 0; i < n; i++) {
int curr_min = i;
for (int j = i + 1; j < n; j++) {
if (arr[curr_min] > arr[j]) {
curr_min = j;
}
}
// swap
int t = arr[i];
arr[i] = arr[curr_min];
arr[curr_min] = t;
}
}
public static void main(String[] args) {
int[] arr = { 14, 3, 2, 4, 1 };
int n = arr.length;
selectionSort(arr, n);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}def selectionSort(arr, n):
for i in range(0, n):
curr_min=i
for j in range(i+1, n):
if arr[curr_min]>arr[j]:
curr_min=j
# swap
arr[curr_min],arr[i]=arr[i],arr[curr_min]
arr = [14, 3, 2, 4, 1]
n = len(arr)
print(*arr)