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

[알고리즘] 삽입정렬 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 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(temp0 && temp>list.get(j-1) ) ) { list.remove(i); list.add(j, temp); break; } } } } arr = list.stream().mapToInt(i -> i).toArray(); return arr; }

반응형

from http://hodubab.tistory.com/351 by ccl(S) rewrite - 2021-09-06 05:27:25