📖 책 정보

---

선택 정렬

아래와 같은 표가 있을 때,

🎶	PLAY COUNT
PADIOHEAD	156
KISORE KUMAR	141
THE BLACK KEYS	35
NETURAL MILK HOTEL	94
BECK	88
THE STROKES	61
WILCO	111

해당 표를 선택 정렬 해본다면?

1. 리스트의 모든 항목을 살펴보고 가장 많이 연주된 가수를 찾아 새로운 리스트에 기록한다.

SORTED	PLAY COUNT
PADIOHEAD	156

2. 그 다음으로 많이 들은 가수를 찾아서 반복한다.

SORTED	PLAY COUNT
PADIOHEAD	156
KISORE KUMAR	141

이런식으로 반복하면 정렬 된 리스트를 얻을 수 있다.

SORTED	PLAY COUNT
PADIOHEAD	156
KISORE KUMAR	141
WILCO	111
NETURAL MILK HOTEL	94
BECK	88
THE STROKES	61
THE BLACK KEYS	35

이렇게 탐색하는 선택 정렬 알고리즘은

한번 정렬할 때 마다 n번의 탐색을 하기 때문에

O(n x n) = O(n²) 시간이 소요된다.

선택 정렬은 깔끔하지만, 빠르지 않다.

퀵 정렬은 O(n log n) 시간밖에 걸리지 않는 더 빠른 정렬 알고리즘이다!

선택 정렬을 학습한 후에 퀵 정렬을 학습한다면,

훨씬 이해하기가 수월할 것이다.

코드로 구현해보기

배열을 오름차순으로 정렬하는 코드

 import java.util.Arrays;

public class SelectionSort {

    private int[] selectionSort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            changeSmallest(i, arr);
        }

        return arr;
    }

    private void changeSmallest(int nowIndex, int[] arr) {
        int minIndex = nowIndex;

        for (int i = nowIndex + 1; i < arr.length; i++) {
            if (arr[i] < arr[minIndex])
                minIndex = i;
        }

        int temp = arr[nowIndex];
        arr[nowIndex] = arr[minIndex];
        arr[minIndex] = temp;

    }
}

실행 확인!

public class SelectionSort {
    public static void main(String[] args) {
        s.selectionSort(new int[]{2,6,7,23,56,712,12,0,1,4,5,9});
    }
}

[ result ]___________🚩  [0, 1, 2, 4, 5, 6, 7, 9, 12, 23, 56, 712] , 탐색 횟수 : 66