단순 삽입 정렬(Straight Insertion Sort)

단순 삽입 정렬(Straight Insertion Sort)

선택한 요소를 그보다 앞쪽의 나열된 요소들 중, 알맞은 위치에 '삽입하는' 알고리즘

 

선택한 요소의 앞부분은 정렬이 완료된 상태이다.

삽입된 위치 이후의 요소들은 한칸씩 뒤로 밀려나게 된다.

 

 

알고리즘 : 

배열의 두번째 요소부터 시작하여 하나씩 요소를 선택한다.

선택된 요소(arr[n])를 tmp 변수에 임시저장한다.

* 변수 tmp에 임시저장하는 이유 : 

   왼쪽의 요소들을 한칸씩 오른쪽으로 미는 과정에서 선택된 요소(arr[n])가 있던 n번째 자리가

   다른 값으로 채워지게 된다. 그렇게 되면 뒤에가서 arr[n]의 원래있던 값이 필요할 때 가져올 수 없으므로

   tmp에 저장해둔다. 

 

선택된 요소(tmp)보다 앞쪽에 있는 요소들(arr[0] ~ arr[n-1])을 뒤에서부터 차례대로 탐색하여

선택된 요소(tmp)와 비교한다.

 

- 선택된 요소(tmp)가 특정 요소(arr[m-1])보다 작다면, arr[m-1]을 한칸뒤로 옮긴다. arr[m] = arr[m-1]

- 선택된 요소(tmp)가 특정 요소(arr[m-1])보다 크다면, arr[m-1] 다음에 선택된 요소(tmp)을 삽입한다.

   arr[m]=tmp

 

위 과정을 마지막 위치의 요소까지 반복한다.

 

 

시간 복잡도 : O(N²)

버블 정렬, 선택 정렬과 마찬가지로 N²의 시간복잡도이므로 비효율적이다.

 

 

 

[예제]

배열 arr의 요소가 차례대로 5 2 3 8 1 4 6 일 때, 이 배열을 오름차순으로 정렬하기

 

먼저, 1번 인덱스에 있는 두번째 요소부터 선택한다.

1번 인덱스보다 왼쪽에 있는 요소는 arr[0] = 5 한개이다.

2와 비교했을 때, 5가 더 크므로 5를 오른쪽으로 한칸 옮기고, 그 자리에 2를 삽입한다.

 

 

2번 인덱스에 있는 3이 선택된다.

왼쪽에 나열된 2 5 에서 오름차순으로 정렬되기 위해 3이 들어가야 하는 위치는 1번째 인덱스이다.

5를 한칸 오른쪽으로 옮기고 1번째 인덱스에 3을 삽입한다.

 

3번째 인덱스에 있는 8이 선택된다.

8보다 왼쪽에 있는 2 3 5는 정렬된 상태이다.

2 3 5와 차례대로 비교했을 때 8이 들어갈 위치는 5 다음이 되기 때문에 결과적으로 위치의 변화가 없다.

 

4번째 인덱스에 위치한 1이 선택된다.

왼쪽에 정렬된 2 3 5 8 과 비교했을 때, 1이 들어갈 위치는 2보다 왼쪽이다.

2 3 5 8을 한칸씩 오른쪽으로 옮기고 0번째 위치에 1을 삽입한다.

 

 

5번째 인덱스에 위치한 4가 선택된다.

4 왼쪽에 정렬된 1 2 3 5 8 과 비교했을 때, 4가 들어갈 위치는 3과 5 사이이다.

5와 8을 한칸씩 오른쪽으로 옮기고 3번째 위치에 4를 삽입한다.

 

 

마지막 6번째 위치의 6을 선택한다.

6의 왼쪽에 정렬된 1 2 3 4 5 8 중에서 6이 들어갈 위치를 찾는다.

6이 들어갈 위치는 5와 8 사이이므로 8을 한칸 오른쪽으로 밀고 5번째 위치에 6을 삽입한다.

 

마지막 요소까지 모두 삽입을 마쳤으므로 정렬이 완료되었다.

 

소스 코드 : 

	public static void insertSort(int[] arr, int n) {

		// 두번째 요소부터 선택하므로 i의 초기값은 1로 설정
		for (int i = 1; i < n; i++) {
			int j;
			int tmp = arr[i]; // 선택한 요소를 임시저장
			for (j = i; j > 0; j--) {
				if (arr[j - 1] < tmp)
					break;
				arr[j] = arr[j - 1];
			}
			arr[j] = tmp;
		}
	}