[java] Insertion Sort 삽입정렬

 
import java.util.Arrays;
import java.util.LinkedList;
 
public class Z21_InsertionSort {
//    public static void main(String[] args) {
//        int[] arr= {6,4,8,5,7,2,9,3,0,1};
//        
//        for(int i=1;i<arr.length;i++) {
//            //삽입할 위치를 찾아 넣기
//            for(int j=i-1;j>=0;j--) {
//                if(arr[j]>arr[j+1]) { //뒤쪽에서 앞으로
//                    int temp = arr[j+1];
//                    arr[j+1]= arr[j];
//                    arr[j]=temp;
//                }
//            }
//        }
//        
//        for(int i=1;i<arr.length;i++) {
//            //삽입할 위치를 찾아 넣기
//            int num=arr[i];
//            int j;
//            for(j=i-1;j>=0;j--) {
//                if(arr[j]>num) { //뒤쪽에서 앞으로
//
//                    arr[j+1]= arr[j];
//
//                } else {
//                    break; //성능을 높일 수 있다.
//                }
//            }
//            arr[j+1] = num;
//        }
//        System.out.println(Arrays.toString(arr));
//    }
    
    public static void main(String[] args) {
        //Linked List 사용하기
        //Swap(쉬프트)작업을 안하는 것으로 성능을 개선
        
        int[] arr= {6,4,8,5,7,2,9,3,0,1};
        LinkedList<Integer> ll = new LinkedList<Integer>();
        
        for(int i=0;i<arr.length;i++) {
            int idx=0;
            for(idx = 0; idx<ll.size();idx++) { //정렬된 데이터에 삽입할 위치 찾기.
                if(arr[i]<ll.get(idx)) {
                    break; //삽입은 밖에서.
                    //0번째에서는 데이터가 없으니 해당 포문을 돌지않아 데이터가 들어가지 않는다.
                }
            }
            ll.add(idx,arr[i]); //ll의 idx번째 자리에 arr[i]를 삽입
        }
        System.out.println(ll);
    }
}