선택 정렬

선택 정렬

주어진 데이터 중 최소값을 찾음
해당 최소값을 맨 앞과 교체
맨 앞을 제외한 나머지 데이터를 동일 한 방법으로 교체

 

선택 정렬

 

데이터가 두 개일 때 선택 정렬

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편 - 패스트캠퍼스