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)