[알고리즘 개념] 삽입정렬

개념

https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

 n번째 인덱스를 선택한다. 그런다음 인덱스 n-1부터 인덱스 0까지 역순으로 순회하여 n번째 인덱스 값과 비교한다. n번째 인덱스 값보다 비교하는 인덱스(k)의 값이 크면, 비교하는 인덱스(k)를 인덱스 k+1로 옮긴다. 만약 인덱스(k)의 값이 작으면 인덱스 k+1자리에 인덱스 n을 삽입한다. 

 

구현

 기준값은 인덱스가 1부터 시작하고 리스트의 길이-1까지 순회한다. 기준값에 대한 비교값은 인덱스가 기준인덱스-1 부터 시작해서 0까지 역순으로 순회한다. 비교값이 기준값보다 크면 비교 인덱스+1에 비교값을 넣는다. 그러다 비교값이 기준값보다 작으면 while문을 빠져나오고 비교인덱스+1에 temp값을 넣는다. 

 

 삽입 정렬에서 핵심은 비교인덱스 +1 에 어떤 값을 넣느냐 인 것 같다. 기준값보다 비교값이 크면 비교인덱스+1에 비교값을 넣고 기준값보다 비교값이 작으면 비교인덱스+1에 기준값을 넣는다. 

코드

	public static void insertSortImprove(int[] list) {
		for(int stand =1; stand<list.length;stand++) {
			int temp = list[stand];
			int index = stand-1;
			while(index>=0 && list[index]>temp) {
				list[index+1] = list[index];
				index--;
			}
			list[index+1]=temp;
		}
	}

시간복잡도

 기준인덱스가 1일때 1번반복, 기준인덱스가 2일때 2번 반복 ... 기준인덱스가 k일때 k번반복한다. 따라서 데이터의 크기가 n인 리스트는 인덱스가 n-1까지 있으므로 1+2+3+...+n-1 , 즉 O(N^2)