Selection sort(선택 정렬)

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