Selection sort is an in-place comparison sort algorithm which has
Algorithm
- Find minimum in unsorted list.
- Swap minimum with left most element in unsorted list.
- Shift boundaries of unsorted list to right by one.
Complexity Analysis
Due to the fact that selection sort is not adaptive ( number of cycles doesn’t change due to given order) it takes
Time | Space | ||
---|---|---|---|
Best case | Worst case | Average case | Worst case |
|
|
|
|
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class SelectionSort {
public int[] selectionSort(int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[j] < numbers[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(i, minIndex, numbers);
}
}
return numbers;
}
private void swap(int i, int j, int[] numbers) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
Comments powered by Disqus.