Selection Sort (선택 정렬)

선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다.

 

 

① 가장 작은 데이터인 1을 가장 앞에 위치한 15와 교환한다. 가장 작은 데이터가 가장 앞에 위치하게 된다.

 

② 첫 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 3을 두 번째 데이터인 11과 교환한다.

 

③ 첫 번째, 두 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 8을 세 번째 데이터인 15와 교환한다.

 

④ 첫 번째, 두 번째, 세 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 11을 네 번째 데이터인 11과 교환한다. 같은 데이터이므로 위치의 변화는 없다.

 

⑤ 데이터들에 대한 정렬이 완료된다.

 

 

JAVA Code

int index = 0;
int temp;
int min;
int arr[] = { 15, 11, 1, 3, 8 };
for (int i = 0; i < arr.length; i++) {
    min = 100;
    for (int j = i; j < arr.length; j++) {
        if (min > arr[j]) {
            min = arr[j];
            index = j;
        }
    }
    temp = arr[i];
    arr[i] = arr[index];
    arr[index] = temp;

}
for (int i = 0; i < arr.length; i++)
    System.out.print(arr[i] + " ");

선택 정렬의 시간 복잡도는 O(n^2)이다.

 

[참조문서]
https://terms.naver.com/entry.naver?docId=2270435&cid=51173&categoryId=51173