Today's special moments become memories of tomorrow.

Algorithm & DS/정렬

단순 삽입 정렬(Straight Insertion Sort)

lotus lee 2021. 2. 16. 23:30

단순 삽입 정렬(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;
		}
	}

'Algorithm & DS > 정렬' 카테고리의 다른 글

힙 정렬(Heap Sort)  (0) 2021.02.22
병합 정렬(Merge Sort)  (0) 2021.02.20
퀵 정렬(Quick Sort)  (2) 2021.02.17
단순 선택 정렬(Straight Selection Sort)  (0) 2021.02.16
버블 정렬(Bubble Sort)  (0) 2021.02.16