삽입정렬 (insertion sort) 을 간단하게 알아보자.

 

삽입 정렬을 간단하게 설명하면?

손에 든 카드를 정렬하는 것처럼 새로운 값을 정렬된 배열에 올바르게 삽입하는 정렬!

 

1. 선택 정렬처럼 정렬된 배열과 정렬되지 않은 배열로 구별해서 정렬한다는 점에서 유사합니다.
2. 그러나 선택정렬과는 달리 삽입 정렬은 값이 삽입되면 정렬된 배열 사이에서 자신의 자리를 찾아가며 정렬합니다.

 

 

구현 과정 

import java.util.*;
public class Main {
	
	public static void main(String[] args) {
		int[] A= {70, 20, 10, 80, 60, 90, 30, 40, 100, 50};
		
		for(int i=0; i<A.length; i++) {            //정렬 전 배열 출력 
			System.out.print(A[i]+" ");
		}
		System.out.println();
		
		for(int i=1; i<A.length; i++) {
			int j=i;                                //배열은 i번째부터 시작. 
			
			while(j>0 && A[j-1]>A[j]) {     //j는 0보다 크고(어차피 j가 1일 때 자동으로 비교되니까) j-1이 j보다 클 경우.
				int temp=A[j];                        //스왑한다. 
				A[j]=A[j-1];
				A[j-1]=temp;
				j--;
			}
		}
		
		for(int i=0; i<A.length; i++) {
			System.out.print(A[i]+" ");
		}
}
}

 

 

시간 복잡도 

• Worst : O(n^2)
• Average : O(n^2)
• Best : O(n^2)