07-4 삽입 정렬

※ 삽입정렬(Insert Sort)

 - 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법.

 - 앞부분은 Sorted/ 뒷부분은 Unsorted로 되어있다.

 - 즉 맨앞의 원소로 부터 시작하여 오른쪽원소와 비교하여 알맞은 위치에 정렬시켜 넣어주는것 이다. 

※구현

Main

public class Main {

       public static void main(String args[]){

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

              int size = a.length;

              InsertSort is = new InsertSort();

              System.out.println("정렬할 원소 : ");

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

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

              }

              System.out.println();

              is.insertionSort(a, size);

       }

}

InsertSort

public class InsertSort {

       int a[];

       

       public InsertSort(){

              this.a=null;

       }

       

       public void insertionSort(int a[], int size){

              if(this.a==null){

                     this.a =a;

              }

              int temp;

              

              for(int i=1; i<size; i++){

                     

                     if(this.a[i-1] > this.a[i]){

                           for(int j=i; j>0; j--){

                                  if(this.a[j-1] > this.a[j]){

                                         temp = a[j];

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

                                         a[j-1] = temp;

                                  }

                           }

                     }

              }

              

              printA();

              

       }

       

       public void printA(){

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

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

              }

              System.out.println();

       }

}