삽입 정렬 - Insertion Sort

개념

---

선택 정렬과 유사하지만 좀 더 효율적인 알고리즘이다.

2번째 원소부터 시작하여 그 앞의 원소들과 비교하고 삽입할 위치를

지정한 후 원소를 뒤로 옮기고 지정된 자료를 삽입하여 정렬한다.

 

동작 과정

---

- 2번째 위치의 값을 temp에 저장 (첫번째 원소 앞에는 어떤 원소도 없기 때문)

- temp와 이전 원소들을 비교하며 삽입해 나간다

- 위치 값을 저장하고 반복한다.

 

Code

---

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

 

시간 복잡도

---

수열이 역으로 정렬되어 있는 최악의 경우 선택 정렬과 마찬가지로 O(n^2)의 시간 복잡도를 갖는다.

하지만 수열이 모두 정렬 되어 있는 경우 한번씩만 비교하면 되기 때문에 O(n)의 시간 복잡도를 갖는다.

 

장점

---

- 단순한 알고리즘이다.

- 원소가 정렬되어 있으면 있을수록 효율적인 알고리즘이다.

- 다른 메모리 공간이 필요 없는 제자리 정렬 알고리즘이다.

- 선택 정렬, 버블 정렬보다 상대적으로 빠르다.

 

단점

---

- 평균, 최악의 경우에 시간 복잡도가 O(n^2)로 비효율적이다.

- 배열 길이가 길어질수록 비효율적이다.

 

 

 

출처 : https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html