[알고리즘]정렬-삽입정렬(Insertion Sort)

삽입정렬 : 2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 자리에 자료를 삽입하여 정렬하는 알고리즘 

과정(오름차순 기준)

1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나갑니다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.

그림으로 보는 삽입정렬

 

Java Code - 오름차순 기준

void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    // 2.
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}

gif로 이해하는 삽입정렬

 

시간복잡도와 공간복잡도

시간복잡도 : 최악의 경우(역으로 정렬되어 있을 경우) 선택정렬과 마찬가지로, (n-1) + (n-2) + .... + 2 + 1 = n(n-1)/2 즉, O(n^2) 입니다. 모두 정렬되어 있을 경우에는 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 됩니다. 

공간복잡도 : 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.

🔈 시간복잡도, 공간복잡도가 뭔지 모르겠다면?

2020/02/11 - [기술면접] - [알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도

[알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도

 

장점과 단점

장점

• 알고리즘이 단순하다.
• 대부분의 원소가 정렬되어 있는 경우라면 매우 효율적이기 때문에 다른 정렬 알고리즘의 일부로 쓰이기도 한다.
• 제자리 정렬이다.
• 안정 정렬이다.
• 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

단점

• 최악의 경우 시간 복잡도가 O(n^2) 으로 비효율적이다.
• 배열의 길이가 길어지면 비효율적이다.

 

자료출처 및 참고 사이트

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%82%BD%EC%9E%85%20%EC%A0%95%EB%A0%AC%20(Insertion%20Sort).md#%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC-insertion-sort

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

https://jinhyy.tistory.com/9

https://zeddios.tistory.com/20#recentComments