정렬 알고리즘(2) - Insertion Sort(삽입정렬)

 

1 2 3 4 5 6 7 8 9 10

public static void sort(int[] arr){         for(int i = 1 ; i < arr.length ; i++){             // arr[1] 과 arr[0] 을 먼저 비교 => arr j =i ; arr[j] 와 arr[j-1] 를 비교             for(int j = i ; j > 0 && arr[j]>arr[j-1]; j--){                 int temp = arr[j];                 arr[j] = arr[j-1];                 arr[j-1] = temp;             }         }     }

1) 2번 째 인덱스[ j ] 원소 부터 뒤에서 앞으로 가며 비교대상 인덱스[ j-1 ] 의 원소 와 비교

2) 현재 인덱스 [ j ] 원소가 비교대상[ j-1 ] 원소 보다 작으면 스왑

2-1) 현재 인덱스 [ j ] 원소가 비교대상[ j-1 ] 원소 보다 크면 반복문의 탈출

BestCase 의 시간복잡도는 정렬이 되어 있을 때 바로앞의 원소와 한번씩만 비교하기(반복문의 탈출) 때문에 => 

WorstCase 의 시간복잡도는 (n-1) + (n-2) + ... 1 이기 때문에 =>  

공간복잡도는 => 

Big-O Notation(상한을 기준) => 

* 실행 시간이 입력 데이터의 초기 배치 위치에 따라 결정