단순 삽입정렬이란? InsertionSort

 

package Mission4;
import java.util.Scanner;
/**
 * N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
 * 정렬하는 방법은 '삽입정렬'입니다.
 */
public class InsertionSort {
    public int[] insertionSort(int num, int[] arr) {

        //아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입 : num - 1회 반복
        for (int i = 0; i < num - 1; i++) {
            //배열의 요소(인덱스가 i인 요소)를 꺼내 알맞은 위치에 삽입
            int tmp = arr[i];
            /**
             * 아래의 두 조건중 하나를 만족할 때까지 k 를 1씩 감소하면서 대입하는 작업 반복(왼쪽으로 이동한다)
             * 1. 정렬된 열의 왼쪽 끝에 도달
             * 2. tmp 보다 작거나 같은 key를 갖는 항목 a[k]를 발견
             * 드모르간의 법칙
             * 1. -> k가 0보다 큼. k > 0
             * 2. -> a[k - 1] 값이 tmp 보다 큼. arr[k - 1] > tmp
             */
            int k;
            //반복 제어용 변수 k에 i - 1을 대입
            for (k = i - 1; k >= 0; k--) {
                if (arr[k] > tmp) {
                    arr[k + 1] = arr[k]; //밀어내기
                } else {
                    break;
                }
            }
            //위 반복문에서 탈출하는 경우 arr[k]가 tmp보다 작다는 의미이므로 tmp는 arr[k]의 뒤에 와야한다.
            //그러므로 tmp는 arr[k+1]에 위치하게 된다.
            arr[k+1] = tmp;
        }
        return arr;
    }
    /**
     * 첫 번째 줄에 자연수 N(1 <= N <= 100)이 주어집니다.
     * 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
     */
    public static void main(String[] args) {

        InsertionSort sort = new InsertionSort();
        Scanner scanner = new Scanner(System.in);

        int num = scanner.nextInt();
        int[] arr = new int[num];

        for (int i = 0; i < num; i++) {
            arr[i] = scanner.nextInt();
            for (int x = sort.insertionSort(num, arr))  {
                System.out.print(x + " ");
            }
        }
    }
}