JAVA-삽입 정렬

 

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

 

배열에서 두번째 요소부터 타켓으로 설정 후 이전 숫자와 비교.

(a). 타겟 : 7 . 이전 숫자인 3과 비교 -> 타겟이 더 크니까 위치 안 바뀌고 패스

(b). 타겟 : 2 . 이전 숫자 7과 비교 -> 타겟이 더 작음 -> 7의 위치를 한칸 뒤로 땡김 ->

더 이전 숫자 3과 비교 -> 타겟(2)가 더 작은 -> 3의 위치도 한칸 뒤로 땡김 -> 첫번째 자리에 타겟(2) 삽입

...

같은 과정 반복

 

** 

 

import java.util.Scanner;

public class Main {
    public int[] solution(int n, int[] arr) {
    //i=1부터 시작
        for (int i = 1; i < n; i++) {
        //타겟 숫자 지정
            int target = arr[i];
            //타겟 이전의 숫자와 비교
            int j = i - 1;
            //타겟 이전의 인덱스가 0보다 크고, 타겟보다 클때만 한칸씩 뒤로 미룸
            while (j >= 0 && target < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }
            //이때 j는 -1이거나 타겟보다 작은 숫자가 있는 위치 ->  그래서 +1 위치에 삽입
            arr[j + 1] = target;
        }
        return arr;
    }