Selection Sort

Idea#

The idea is to select the smallest element of remaining array and then swap it to the front.

Visualization#


Implementation#

  • scan array, find the minimum element's index min_idx
  • swap the element to the index i, then incrememnt i
public class SelectionSort{
void selectionSort(int arr[]) {
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++) {
// Find the minimum element in the input array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the ith element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
}

Time and Space Analysis#

  • Time O(n^2)
  • Space O(1)