삽입정렬(Insertion Sort)

삽입정렬: 필요할때만 적절한 위치에 삽입하는 정렬

(앞의 요소들은 정렬이 되어있다고 가정한다)

 

Java code

import java.util.*;


public class InsertionSort {
	public static void main(String[] args) {
		int i,j,temp;
		int []arr= {1,10,5,8,7,6,4,3,2,9};
		for(i=0;i<arr.length-1;i++) {
			while(arr[i]>arr[i+1]) { //앞의 원소가 뒤의 원소보다 작을때 까지 while문 실행
				temp=arr[i];
				arr[i]=arr[i+1];
				arr[i+1]=temp;
				i--;
			}
		}

		for(int k=0;k<arr.length;k++)
			System.out.print(arr[k]+" ");

	}
}

 

정렬 과정

 

1 10 5 8 7 6 4 3 2 9

 

(1)

1 (10)

1 (5) 10 

1 5 (8) 10 

1 5 (7) 8 10

1 5 (6) 7 8 10

1 (4) 5 6 7 8 10

1 (3) 4 5 6 7 8 10

1 (2) 3 4 5 6 7 8 10

1 2 3 4 5 6 7 8 (9) 10

 

삽입정렬도 최악의 상황으로는 버블정렬과 선택정렬과 마찬가지로 

10+9+8 ...+2+1=N(N+1)/2=O(N^2)의 시간복잡도를 갖는다

 

그러나 데이터가 이미 거의 정렬된 상태에서 정렬을 계속 실행하기 때문에 버블정렬보과 선택정렬보다 훨씬 빠르다