[java] 선택정렬 (Select Sort)

1. 선택정렬이란

- 선택정렬이란, 초기상태의 배열(정렬되지 않은 상태)에서 우선순위가 가장 높은 요소를

선택해 배열의 맨 앞으로 이동시키는 정렬 방법이다.

​

예시)

​

2. 시간복잡도

선택정렬의 장점

1.구현이 간단하고

2. 두 개의 반복문을 사용하여 비교 횟수가 정해져잇다.

​

단점

1. 반복문이 돌기 전에 정렬이 끝나도, 배열의 끝 요소까지 비교를 체크한다.

​

따라서 선택정렬의 시간복잡도는 O(n2)로 매우 느리다.

선택 정렬 구현 방법

ex)

int arr[] = {1, 3, 5, 4, 2 };

for(int i=0;i<arr.length-1;i++){
    int index = i;
    for(int j=i+1;j<arr.length; j++){
        if(arr[j] < arr[index])
             index = j;
    }

    int temp = arr[i];
    arr[i] = arr[index];
    arr[index] = temp;
}