[정렬 #1] 삽입 정렬(Insertion Sort) w. Java

삽입정렬은 자료배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

특징 및 장점

• 레코드가 적고, 이미 정렬된 자료 배열일 경우 매우 빠르다.
• 구현이 간단하다.
• 안정 정렬(중복된 값을 입력 순서와 동일하게 정렬하는 정렬 알고리즘)이다.
• in-place 알고리즘(보조 변수에 대해 약간의 추가 저장 공간이 허용되는 알고리즘)이다.

단점

• 레코드의 이동이 많이 일어나는 알고리즘이므로 레코드가 많을수록 비효율적이다.

 

Psuedo Code

INSERTION-SORT (A)
  for j <- 2 to length[A]
       do key <- A[j]
         Insert A[j] into the sorted sequence A[1 . . j - 1].
        i <- j - 1
        while i > 0 and A[i] > key
           do A[i + 1] <- A[i]
              i <- i - 1
        A[i + 1] <- key

 

Java로 구현

void insertionSort(int[] arr){
	for(int idx=1; idx < arr.length; idx++){
    	
        int temp = arr[idx];
        int aux = idx-1;
        
        while((aux>=0) && (arr[aux]>temp)){ // 앞 레코드가 해당 레코드보다 큰 경우
        	
            arr[aux+1] = arr[aux];	// 해당 레코드 값을 앞 레코드 값으로 변경
            aux--;	
        }
        arr[aux+1] = temp; // 앞 레코드를 해당 레코드의 변경 전 값으로 변경 (만약 위의 while문을 안탔다면 레코드 값은 동일)
    }
}

 

시간 복잡도

최선: n -> 이미 레코드가 정렬되어 있는 경우

평균: n^2

최악: n^2 -> 레코드가 역순으로 정렬되어 있는 경우

 

Reference

https://ko.wikipedia.org/wiki/삽입_정렬

https://www.ee.ryerson.ca/~courses/coe428/sorting/insertionsort.html