정렬 알고리즘(1) - Selection Sort(선택 정렬)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public static void sort(int[] arr){         for(int i = 0 ; i< arr.length-1; i++){             int minIdx = i; // 최소값을 저장할 인덱스 (Yellow)             for(int j = i+1; j< arr.length ; j++){                 // j 는 비교대상 인덱스 (Blue)                 if(arr[j]<arr[minIdx])//현재 인덱스(Yellow)의 값보다 비교하는 값(Blue)이 작을때                     minIdx = j; // 최소값의 인덱스를 변경             }             int temp = arr[i];             arr[i] = arr[minIdx];             arr[minIdx] = temp;         }     }

n-1번 + n-2번 + n-3번 .... + 1번 비교를 진행한다.

따라서 시간복잡도는

공간복잡도는 하나의 배열에서만 진행하므로 을 가지게 된다.

Best Case 와 Worst 케이스 모두 복잡도는 동일하다.

* 실행 시간이 입력 데이터의 배치와 무관

* 데이터 이동이 최소화

* 제자리 정렬 (부가적인 저장 공간이 필요 없다.)