[Algorithm] 선택정렬

• 정렬 중 가장 쉽게 구현이 가능합니다.
• N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.
• 처리되지 않은 모든 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다.
• 시간복잡도는 N + (N - 1) ... + 2로 등차수열 공식에 따라서 (N^2 + N - 2)/2로 표현할 수 있습니다.
• 빅오 표기법에 따라 O(N^2)이 됩니다.

static void selectSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int minIndex = array[i];
        for (int j = i + 1; j < array.length; j++) {
            if (array[minIndex] > array[j]) {
                minIndex = j;
            }
        }

        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }

    for (int i : array) {
        System.out.print(i + " ");
    }
}

 

---

참고자료

• 나동빈 - 이코테