삽입 정렬(Insert Sort)

삽입 정렬은 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 삽입 정렬에서는 정렬할 자룍 두 개의 부분집합 S와 U로 나뉘어 있다고 가정한다 앞부분 원소부터 정렬을 수행하는데 정렬된 앞부분의 원소들은 부분집합 S가 되고, 아직 정렬되지 않은 나머지 원소들은 부분집합 U가 된다. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하여 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 줄인다. U의 원소를 모두 삽입하여 공집합이 되면 삽입 정렬이 완성된다.

시간복잡도 : 최소 - O(n), 최대 - O(n^2)

public class insertSort {

public static void main(String[] args) {

int a[]={69,10,30,2,16,8,31,22};

int temp,j;

for(int i=0  ; i<a.length ; i++){

System.out.print(a[i]+" ");

}

System.out.println("\n");

for(int i=1 ; i<a.length ; i++){

temp=a[i];

j=i;

while((j>0)&&(a[j-1]>temp)){

a[j]=a[j-1];

j=j-1;

}

a[j]=temp;

}

for(int i=0  ; i<a.length ; i++){

System.out.print(a[i]+" ");

}

System.out.println("\n");

}

}