Selection sort(선택 정렬)
- 1원칙: i 위치에 채워질 최저/최대값을 i 뒤에서 찾는다.
- 2원칙: i보다 가장 작은수를 찾는다.
- 3원칙: 있다면 i와 자리를 바꾼다.
Best case: O() == Worst case: O() : 어차피 다 확인해야 한다.
public class SelectionSort {
public void sort(Comparable[] array) {
for (int i = 0; i < array.length; i ++) {
int lowestIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[lowestIndex].compareTo(array[j]) > 0) {
lowestIndex = j;
}
}
// swap
if (i != lowestIndex) {
Comparable temp = array[i];
array[i] = array[lowestIndex];
array[lowestIndex] = temp;
}
}
}
}
Referenced from: https://en.wikipedia.org/wiki/Selection_sort
'Algorithms > Sorting' 카테고리의 다른 글
Quick sort(퀵 정렬) (0) | 2017.06.24 |
---|---|
Merge sort(병합 정렬) (0) | 2017.02.08 |
Insertion sort(삽입 정렬) (0) | 2017.02.06 |
Bubble sort(거품? 정렬) (0) | 2017.02.06 |