[Algorithm] Insertion Sorting (삽입 정렬)

삽입 정렬 (Insertion Sorting)

삽입 정렬(Insertion Sorting)은 선택 정렬(Selection Sorting)과 유사하지만 좀 더 효율적인 정렬 알고리즘이다.

매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

 

장점

1. 안정적인 정렬 방법

2. 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.

3. 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

단점

1. 비교적 많은 레코드들의 이동을 포함한다.

2. 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

 

Cording

package 삽입정렬;

public class InsertionSort {
	public static void main(String[] args) {
		int array[] = {8,5,6,2,4};
		for(int i=0;i<array.length-1;i++) {
			for(int j=i;j>=0;j--) {
				int tmp = 0;
				if(array[j]>array[j+1]) {
					tmp = array[j];
					array[j]=array[j+1];
					array[j+1]=tmp;
				}
				else break;
			}
		}
		for(int i : array) System.out.print(i+" ");
	}
}