반응형
- 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함.
- 배열의 두 번째 데이터 부터 연산을 시작함.
- 시간복잡도 : O(n^2)
package algorithm.sort;
public class Insertion {
public static void main(String[] args) {
int[] arr = {3,6,1,9,2, 7,4,8,5,0, 14,23,98,45,76, 34};
insertionSort(arr);
System.out.println("===========================");
for(int item : arr){
System.out.print(item);
System.out.print("|");
}
System.out.println();
System.out.println("===========================");
}
private static void insertionSort(int[] arr){
int j = 0;
for(int i = 1 ; i < arr.length ; i++){
int tmp = arr[i];
for(j = i-1 ; j >= 0 ; j--){
if(arr[j] > tmp){
arr[j+1] = arr[j];
}else{
break;
}
}
arr[j+1] = tmp;
}
}
}
반응형
'Algorithm' 카테고리의 다른 글
[Sort] Quick (0) | 2020.07.12 |
---|---|
[Sort] Merge (0) | 2020.07.07 |
[Sort] Bubble (0) | 2020.07.06 |
[Sort] Selection (0) | 2020.07.05 |