선택 정렬
주어진 데이터 중 최소값을 찾음
해당 최소값을 맨 앞과 교체
맨 앞을 제외한 나머지 데이터를 동일 한 방법으로 교체
데이터가 두 개일 때 선택 정렬
import java.util.*;
ArrayList<Integer> list = new ArrayList<>();
list.add(8);
list.add(2);
if(list.get(0) > list.get(1)) {
Collections.swap(list, 0, 1);
}
System.out.println(list); // [2, 8]
데이터가 세 개일 때 선택 정렬
import java.util.*;
ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(2);
list.add(8);
// 작은 데이터
int min = 0;
for(int i = 0; i < list.size() - 1; i++) {
min = i;
for(int j = min + 1; j < list.size(); j++) {
if(list.get(min) > list.get(j)) {
min = j;
}
}
Collections.swap(list, min, j);
}
System.out.println(list); // [2, 8, 10]
선택 정렬 구현
import java.util.*;
public class SelectionSort {
public ArrayList<Integer> sort(ArrayList<Integer> list) {
// 작은 변수
int min = 0;
for(int i = 0; i < list.size() - 1; i++) {
min = i;
for(int j = min + 1; j < list.size(); j++) {
if(list.get(min) > list.get(j)) {
min = j;
}
}
Collections.swap(list, min, j);
}
return list;
}
}
시간 복잡도
- 반복문이 두개 O(n^2)
feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스