삽입정렬 Insertion Sort

삽입 정렬

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

 

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

 

시간복잡도

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

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)) {			
                	//현재값이 이전 위치의 값보다 같거나 작으면 이전 위치(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;
	}

출처

• 컴퓨터 알고리즘 기초 4강 삽입정렬,  T아카데미