삽입정렬(Insertion sort)

binary·2020년 6월 12일

삽입정렬 알고리즘 자료구조

Algorithm

목록 보기

2/2

삽입정렬 알고리즘의 특징

왼쪽에 배열를 유지하며 한 칸씩 늘려가며 정렬합니다
한 칸 늘릴 대 새로 삽입된 데이터를 왼쪽에 정렬된 배열에서 맞는 자리로 위치시킵니다.
탐색범위
- Outer: 1 > n
  - 정렬된 배열을 유지할 때 시작 값 2로 설정
- Inner: j ≥ 0 && arr[j] > temp
  - 정렬된 배열을 끝까지 탐색 안 했고 (그리고)
  - 현재 값 보다 temp가 더 작으면 >> 왼쪽으로 이동합니다

삽입정렬 알고리즘 구현방식

구현되는 방식을 살펴보겠습니다.

테이블 기준값

[6,5,3,1,8,7,2,4] 5 왼쪽 배열 [6] 에서 5가 6 보다 작으므로 6 왼쪽으로

[5,6,3,1,8,7,2,4] 3 왼쪽 배열 [,5,_6,] 에서 3이 5,6 보다 작으므로 5 왼쪽으로

[3,5,6,1,8,7,2,4] 1 왼쪽 배열 [3_5_6] 에서 1이 3,5,6 보다 작으므로 3 왼쪽으로

[1,3,5,6,8,7,2,4] 8 왼쪽 배열 [1_3_5_6] 에서 8이 1,3,5,6 보다 크므로 6 오른쪽으로

[1,3,5,6,8,7,2,4] 7 왼쪽 배열 [1_3_5_6_8] 에서 7이 1,3,5,6 보다 크고 8보다작으로 6 오른쪽으로

....

[1,2,3,4,5,6,7,8] 정렬 완료

코드로 구현하기

function insertionSort(arr) {
	let i, j, temp;
	// 인덱스 0은 이미 정렬된 것으로 여기고 인덱스 1부터 비교한다
	for (i = 1; i < arr.length; i++) {
		// 뒤에서 j값이 들어갈 위치를 찾는 탐색을 구현하다보면
		// 값을 덮어쓰는 방식으로 구현되기 때문에 
		// 미리 비교 값을 임시 값에 담아둔다.
		temp = arr[i] 
		// 현재 왼쪽에 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
		// j값은 음수가 아니어야 하고
		// temp 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 덮어씌운다
		for (j = i-1; j >= 0 && temp < arr[j]; j--) {
			arr[j+1] = arr[j]	// 레코드의 오른쪽으로 이동시킨다. 
		}
		// innner 탐색을 마치고 나면 arr[j+1] 부분은 arr[j]값이 들어와있다.
		// 이를 탐색 전에 temp에 담아 두었던 값으로 바꾸어준다.
		arr[j+1] = temp;
	}
	return arr
}

console.log(insertionSort([6,5,3,1,8,7,2,4])) // [1,2,3,4,5,6,7,8]