[Java] 삽입 정렬(insertion sort)

삽입정렬(insertion sort)

 

 

선택한 요소를 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘

 

1. 변수 tmp에 a[i]를 대입 (a[i]는 정렬하지 않은 부분의 첫번째 요소)

2. 변수 j에 i-1대입 후 2개의 조건 중 하나를 만족할 때까지 j를 감소

- 정렬된 열의 왼쪽 끝에 도달

- tmp보다 작은 key를 같는 a[j]를 발견

 

import java.util.Scanner;

class InsertionSort {
    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 scan = new Scanner(System.in);
        
        print("n의 개수: ")
        int num = scan.nextInt();
        int[] x = new int[num];
        
        for(int i=0; i<num; i++){
            print("x["+i+"] :");
            x[i] = scan.nextInt();
        }
        
        insertionSort(x, num)
        
        for(int i=0; i<num; i++){
            print("x["+i+"] = "+ x[i]);
        }
        
    }
}