Insertion Sort

 

 

 

Insertion Sort 삽입정렬

 

Insert an element in the sorted subarray to its left. 

두번째 Index를 시작으로 자신보다 앞 쪽 (왼쪽) 의 값과 계속 비교해가면서 자리를 옮겨나가는 알고리즘이다. 

 

 

 

 

 

How the Insertion array works

 

int arr[] = [3,5,1,4,2] 

 

partial sorted subarray	partial unsorted array
[3]	[5,1,4,2]
[3,5]	[1,4,2]
[3,5,1] -> [3,1,5] -> [1,3,5]	[4,2]
[1,3,5,4] -> [1,3,4,5]	[2]
[1,3,4,5,2] -> [1,3,4,2,5] -> [1,3,2,4,5] -> [1,2,3,4,5]	[]

 

 

 

 

 

Solution in Java

 

public class Main {
 
    public static void main(String[] args) {
        int arr[] = {3,5,1,4,2};
 
        Insertion insertion = new Insertion();
        insertion.sort(arr);
    }
}
 
public class Insertion {
 
    public void sort(int arr[]) {
 
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int sort = i - 1;
            while (sort >= 0 && key < arr[sort]) { //key 값이 앞의 element보다 크면 while실행
                arr[sort + 1] = arr[sort]; //값이 바뀌어도 원래값은 key에 저장되어 있기때문에 문제가 없다.
 
                sort--; //계속 앞으로 돌아가서 비교 
            }
            arr[sort + 1] = key;
        }
        print(arr);
    }
 
    public static void print(int[] arr) {
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k] + ", ");
        }
    }
}

 

Output

1, 2, 3, 4, 5,

 

 

 

Solution in JavaScript

function insertionSort(arr) {
    const len = arr.length;

    for (let i = 1; i < len; i++) {
        let key = arr[i];
        let j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }

    console.log(arr);
}

insertionSort([4,2,1,5,3]);

 

 

 

 

Reference

https://www.youtube.com/watch?v=iqf96rVQ8fY

https://www.geeksforgeeks.org/insertion-sort/

https://marobiana.tistory.com/85