삽입정렬(Insertion sort) Java 구현

삽입정렬(Insertion sort) Java 구현

삽입정렬

• 삽인정렬은 선택한 요소를 그 보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘이다.

• 정렬되지 않은 배열의 첫번째 요소를 i라고 했을때 0부터 i-1까지의 부분의 값과 비교하여 i값은 알맞은 위치에 삽입한다.

임의의 배열 arr = [6, 4, 1, 7, 3, 9, 8]이 있을때 순서는

step 1. [4, 6, 1, 7, 3, 9, 8]

step 2. [1, 4, 6, 7, 3, 9, 8]

step 3. [1, 4, 6, 7, 3, 9, 8]

step 4. [1, 3, 4, 6, 7, 9, 8]

step 5. [1, 3, 4, 6, 7, 9, 8]

step 6. [1, 3, 4, 6, 7, 8, 9]

정렬된 부분의 값의 범위가 0부터 i-1이고 정렬되지 않은 부분이 i부터 n-1이라고 했을때

i는 본인의 적절한 위치를 찾은 다음에 그 위치를 기준으로 값들의 인덱스가 한칸씩 밀려나야한다.

class InsertionSort{
    static void insertionSort(int[] a, int n){
        for(int i=1; i<n;i++){
            int j; // 옮길 값이 들어갈 인덱스
            int tmp = a[i]; // 옮길 값 저장
            for(j = i; j>0 && a[j-1] > tmp;j--){//j 인덱스는 0보다 크고 값은 a[i]보다 작을때 까지 반복한다.
                a[j] = a[j-1]; // i앞에 있는 값들을 한칸씩 땡긴다.
            }
            a[j] = tmp; 
        }
    }
}

시간복잡도는 O(n^2)