[자료구조] 삽입 정렬 (Insertion Sort)

삽입 정렬(Insertion Sort)

• 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복.
• 앞에서부터 정렬된다.

출처: C언어로 쉽게 풀어쓴 자료구조

 

코드

import java.util.Scanner;

// 삽입 정렬
public class InsertionSort {
    public void sort(int[] array) {
        for (int i=1; i < array.length; i++) {
            int key = array[i];
            for (int j=i-1; j >= 0; j--) {
                if (key < array[j]) {
                    array[j+1] = array[j];
                }
                else {
                    array[j+1] = key;
                    break;
                }
            }
        }
        for(int n : array) {
            System.out.print(n + " ");
        }
    }
}

// 테스트
class Test {
    public static void main(String[] args) {
        System.out.print("정렬할 수를 입력하세요 ex) 1,4,5,3 >> ");
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] s = input.split(",");
        int[] array = new int[s.length];
        for(int i=0; i<s.length; i++) {
            array[i] = Integer.parseInt(s[i]);
        }
        InsertionSort insertion = new InsertionSort();
        insertion.sort(array);
    }
}

 

실행 결과

정렬할 수를 입력하세요 ex) 1,4,5,3 >> 1,8,4,6,7,2,4,3,5,10,12
1 2 3 4 4 5 6 7 8 10 12