[알고리즘] 삽입정렬

package test_java;
 
import java.io.IOException;

 
public class Main {
 
    public static void main(String[] args) throws IOException {
        
        int[] arr= {4,2,5,6,1,3};
        insertSort(arr);
        
        for(int result : arr) {
            System.out.println(result);
        }
 
    }
    
    public static int[] insertSort(int[] arr) {
        
        for (int i = 1; i < arr.length; i++) {
        
            int standard = arr[i]; // 기준
            int compare = i - 1; // 비교
 
            while (compare >= 0 && standard < arr[compare]) {
                arr[compare + 1] = arr[compare]; // 비교대상이 더크면 idex을 증가시켜 넣어둠
                compare--;
            }
 
            arr[compare + 1] = standard;
        }
 
        return arr;
    }
    
}// CLASS END

삽입정렬이란?

- 각 구간별 하나씩 삽입하면서 정렬하는 것

예제

4 2 5 6 1 3

1회전 2 4 5 6 1 3

2회전 2 4 5 6 1 3

3회전 2 3 4 5 6 1

4회전 2 3 4 5 6 1

5회전 1 2 3 4 5 6

*시간복잡도

=> O(n^2)