Selection Sort

Data structure: Array

Worst case performance: O(n^{2})

Best case performance: O(n^{2})

Average case performance: O(n^{2})


Example:

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists,

For a list with n elements the number of passes required to sort will be n-1 with the smallest element placed in the leftmost position (for ascending order sort) in the first pass. Therefore, for a list with k sorted elements, passes required will be n - k

// selecton sort algo for ascending order
selsort(arr)
for every element i in arr{
minIndex = i //assume starting with first element to be the minimum
for every i+1 element in arr{
if(arr[i] > arr[i+1]){
minIndex = i+1 //set next index as new min
}
}

if(i != minIndex){
swap(arr[i], arr[minIndex])
}

}


http://www.java2novice.com/java-sorting-algorithms/selection-sort/
https://en.wikipedia.org/wiki/Selection_sort
http://www.cs.armstrong.edu/liang/animation/web/SelectionSort.html