삽입 정렬

 

정의

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

 

동작 과정

• 정렬은 2번째 위치(index)의 값을 temp에 저장한다.

• temp와 이전에 있는 원소들과 비교해 삽입해나간다.

• 1번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

 

 

Python 코드

def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1] = x[j]
			j = j - 1
		x[j+1] = key
	return x

 

Java 코드

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));
}

1. 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치(index)부터 탐색을 시작한다. temp에 임시로 해당 위치(index) 값을 저장하고, prev에는 해당 위치(index)의 이전 위치(index)를 저장한다.

2. 이전 위치(index)를 가리키는 prev가 음수가 되지 않고, 이전 위치(index)의 값이 1번에서 선택한 값보다 크다면, 서로 값을 교환해주고 prev를 더 이전 위치(index)를 가리키도록 한다.

3. 2번에서 반복문이 끝나고 난 뒤, prev에는 현재 temp 값보다 작은 값들 중 제일 큰 값의 위치(index) 를 가리키게 된다. 따라서, (prev+1)에 temp 값을 삽입해준다.

 

 

동작 방식(GIF)

시간 복잡도

• 모두 정렬이 되어있는 경우에는 O(n), 또한 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거 하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.

• 최악의 경우(역으로 정렬되어 있을 경우), O(n²)이다.

• 최선의 경우 O(n), 평균과 최악의 경우 O(n²)의 시간 복잡도를 갖게 된다.

공간 복잡도

• 별도의 추가 공간을 사용하지 않고 주어진 배열 안에서만 교환하므로 O(1)이다.

 

장점

• 알고리즘이 단순하다.

• 정렬되어 있는 경우, 매우 효율적이다.

• 정렬하고자 하는 배열 안에서 교환하는 방식으로, 다른 메모리 공간이 필요하지 않다(제자리 정렬

• 안정 정렬이다(중복된 값이 입력 순서와 동일하게 정렬되는 알고리즘)

단점

• 평균과 최악의 시간복잡도가 O(n²)로 비효율적이다.

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