단순 삽입 정렬(straight insertion sort)

단순 삽입 정렬(straight insertion sort)

단순 삽입 정렬은 0 ~ n-1까지 n개의 배열이 있다고 가정했을 때, 1번 위치 요소부터 선택을 시작하여 현재 정렬되지 않은 부분의 첫 번째 요소를 선택하여 선택한 위치 앞 부분 요소들과 비교를 하여 정렬기준에 따라 해당 되는 위치에 삽입을 수행해나가는 정렬 알고리즘이다. 

단순 삽입정렬은 셔틀 정렬(shuttle sort)라고도 부른다.

---

Do it 자료구조와 함께 배우는 알고리즘 입문 참조

---

   // 선택 정렬 부분
    static void insertionSort(int[] a, int n){
            for(int i = 1; i < n ; i++){
                int j; // 변경할 위치를 찾기위한 변수
                int tmp = a[i]; // 삽입할 요소 값
                for(j = i ; j > 0 && a[j-1] > tmp ; j--)
                    a[j] = a[j-1];
                a[j] = tmp;
            }
	}
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("단순 삽입 정렬");
        System.out.print("요솟수 : ");
        int nx = sc.nextInt();
        int[] x = new int[nx];

        for(int i = 0 ; i < nx ; i++){
            System.out.print("x[" + i + "] : ");
            x[i] = sc.nextInt();
        }

        insertionSort(x,nx);

        System.out.println("\n오름차순으로 정렬합니다.");
        for(int i = 0 ; i < nx; i++){
            System.out.println("x["+i+"] = " + x[i]);
        }
    }

---

위에 코드와 같이 1번 인덱스 위치부터 값을 선택해나가며, 정렬기준에 따른 위치에 값을 삽입해나가는 방식이다.

 

이때 두 가지 조건에 따라 반복적으로 비교가 이루어진다.

 

   1.) 해당 위치에 값을 삽입하기 위해 찾아나가는 j변수 값이 0보다 크다.

   2.) 현재 삽입하고자하는 위치 j에 대해서 앞 쪽 인덱스의 요소가 정렬기준에 따라 변경되어야 할 경우

 

-> 쉽게말해 현재 위치에 값을 선택하고 앞쪽요소와 계속 비교를 해가면 자신의 위치를 찾아나가는 것이다. 즉, 현재 위치 앞쪽에 요소가 정렬기준에 따라 현재 선택된 요소보다 뒤쪽에 위치해야할 경우라면 계속 한 칸씩 이동하다가 더 이상 비교 대상이 없거나, 이미 앞쪽 요소가 기준에 따라 앞쪽에 위치해야할 경우(정렬된 경우) 현재 위치가 선택된 요소의 정렬 위치가 되는 것이다.