[Algorithm] Basic Sort Algorithm - Insertion Sort (삽입 정렬)

Insertion Sort(삽입 정렬) 란?

아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식

Insertion 단계

- item to insert 전의 데이터들은 정렬이 되있는 상태

- item to insert를 정렬 데이터들의 뒤부터 비교하는 것이 효율적! -> 배열에 저장되어있기 때문

Insertion

public void insertSort(int[] arr) {
	if (arr.length == 0) {
		return;
	}
	
	System.out.print("[정렬할 원소] ");
	print(arr);
	
	for (int i=1; i<arr.length; i++) {		// 1
		for (int j=i-1; j>=0; j++) {
			int temp = arr[i];
			
			// 2
			if (arr[i] > arr[j]) {
				arr[j+1] = temp;
				break;
			}
			
			arr[j+1] = arr[j];		
		}
		

		System.out.print(i + "단계 : ");
		print(arr);
	}
}

 

실행시간

1번의 for 루프는 n-1번 반복

2번의 삽입은 최악의 경우 i-1번 비교

 

최악의 경우 시간복잡도:  T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

 

 

 

 

Ref. https://www.youtube.com/watch?v=0dG7xTt5IfQ