삽입 정렬

삽입 정렬

두 번째 인덱스부터 시작
해당 인덱스 (key 값) 앞에 있는 데이터 (B)부터 비교해서 값이 작으면, B 값을 뒤 인덱스로 복사
key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

 

삽입 정렬

 

데이터가 두 개일 때 삽입 정렬

import java.util.*;

ArrayList<Integer> list = new ArrayList<>();

list.add(5);
list.add(2);

if(list.get(1) < list.get(0)) {
    Collections.swap(list, 1, 0);
}

System.out.println(list);    // [2, 5]

 

데이터가 세 개일 때 삽입 정렬

import java.util.*;

ArrayList<Integer> list = new ArrayList<>();

list.add(10);
list.add(7);
list.add(3);

for(int i = 0; i < list.size() - 1; i++) {
    for(int j = i + 1; j > 0; j--) {
        if(list.get(j) < list.get(j - 1)) {
            Collections.swap(list, j, j - 1);
            
        } else {
            break;
        }
    }
}


System.out.println(list);    // [3, 7, 10]

 

구현

import java.util.*;

public class InsertionSort {
    public ArrayList<Integer> sort(ArrayList<Integer> list) {
        for(int i = 0; i < list.size() - 1; i++) {
            for(int j = i + 1; j > 0; j--) {
                if(list.get(j) < list.get(j - 1)) {
                    Collections.sort(list, j, j - 1);
                    
                } else {
                    break;
                }
            }
        }
        
        return list;
    }
}

 

시간 복잡도

• O(n^2)

 

 

 

 

 

 

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스