[Java] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

• 선택 정렬은 한 번의 배열 탐색에서 가장 작은 원소의 위치를 찾고, 그 위치와 배열의 가장 첫 번째 원소부터 차례로 바꿔주는 방식을 사용하는 정렬 방식이다.
• 가장 큰 원소나 작은 원소를 선택하고 그 위치를 바꿔주기 때문에 선택 정렬이라는 이름을 사용한다.
• 시간 복잡도는 O(N^2)이므로 실전에서 사용되기 힘든 정렬이다.

코드 구현

// 오름차순 정렬
private static <T extends Comparable<T>> T[] sort(T[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[minIndex].compareTo(arr[j]) > 0) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            T temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return arr;
}

// 내림차순 정렬
private static <T extends Comparable<T>> T[] sort(T[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int maxIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[maxIndex].compareTo(arr[j]) < 0) {
                maxIndex = j;
            }
        }
        if (maxIndex != i) {
            T temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
    }
    return arr;
}

References

https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/SelectionSort.java

https://st-lab.tistory.com/168