[알고리즘] 삽입정렬 Insertion Sort

삽입 정렬이란?

Key 값과 정렬된 리스트가 주어졌을때, Key값을 정렬된 리스트의 알맞은 위치에 삽입
Key 값을 하나씩 추가하면서 정렬.

① i 위치의 값을 0~(i-1) 위치까지의 값과 비교하여 i위치의 값이 들어갈 위치를 찾음.
② i 위치의 값을 찾은 자리에 삽입

수행시간

최선의 경우 : 0 ~ i-1 배열이 이미 정렬된 경우 > 비교를 1번만 하면 됨
                  >> n-1
최악의 경우 : 0 ~ i-1 배열이 반대로 정렬된 경우 > 모든 배열 값과 다 비교해야 함.
                   >> n(n-1)

빅오표기 :  O(n²)

 

내가 구현한 소스 (JAVA)

	public int[] sort(int[] arr) {
		
		List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
		
		for(int i = 1; i < arr.length; i++) {
			Integer temp = list.get(i);
			for(int j = i-1; j > -1; j--) {
				
				if(temp<list.get(j)) {					
					if( (j==0) || (j>0 && temp>list.get(j-1) ) ) {
						list.remove(i);
						list.add(j, temp);
						break;
					}
				}
			}
		}
		
		
		arr = list.stream().mapToInt(i -> i).toArray();
		return arr;
	}