[알고리즘] JAVA 삽입 정렬 (Insert Sort) 알고리즘

  

 

- 무조건 위치를 변경하는 선택 정렬, 버블 정렬과는 다르게 필요할 때에만 위치를 변경

- 시간복잡도는 선택 정렬, 버블 정렬과 같은 O(N^2)으로 비효율적

- 하지만, 데이터가 이미 정렬된 상태에 한해서는 어떤 알고리즘보다도 빠르다.

- 적절한 위치에 삽입하는 알고리즘

 

문제

- 다음 숫자들을 오름차순으로 정렬하시오.

- 1, 10, 6, 8, 4, 2, 3, 5, 9, 7

 

소스 코드

package com.company;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int arr[] = new int[10];
        for(int k=0; k<arr.length; k++) {
            arr[k] = sc.nextInt();
        }

        int i, j, temp;
        for(i=0; i<9; i++) {
            j=i;
            while(j>0 && arr[j-1] > arr[j+1]) {
                temp = arr[j-1];
                arr[j-1] = arr[j+1];
                arr[j+1] = temp;
                j--;
            }
        }

        for(i=0; i<10; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 

출력 결과