정렬 - 삽입정렬(Insertion Sort)

삽입정렬

정렬되지 않은 첫 인덱스를 선택 후 하나씩 오른쪽으로 늘어간다.

앞쪽부터 정렬해가며 정렬되어있지 않은 새로운 값이 정렬되어있는 값과 비교하여 작다면 맞는 위치에 삽입하여 정렬한다.

 

firstUnsortedIndex = this is the first index of the unsorted partion

i = index used to traverse the sorted partiton from right to left

newElement = the value we want to insert into the sorted partion - array[firstUnsortedIndex]

 

 

 

 

java예제

 int[] intArray = {20,13, -22,7,34,1,-20};
 
 for(int firstUnsortedIndex = 1; firstUnsortedIndex < intArray.length; firstUnsortedIndex++){
    int newElement = intArray[firstUnsortedIndex];

    int i;
    for(i = firstUnsortedIndex; i > 0 && intArray[i-1] > newElement; i--){
        intArray[i] = intArray[i-1];
    }

    intArray[i] = newElement;

}

for(int i = 0; i <intArray.length; i++){
    System.out.println(intArray[i]);
}

 

 

 

 

특징

- in-place algorithm

- O(n2) time complexity - quadratic

- stable algoritm

- 배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다.

- 선택 정렬이나 거품 정렬과 같은 알고리즘에 비교하여 빠르다

- 안정 정렬이고 in-place 알고리즘이다.

 

 

References

https://algopoolja.tistory.com/19