[Java] 삽입정렬

삽입정렬

1. 두 번째 인덱스부터 앞 인덱스와 값 비교.

2. 첫 번째 인덱스 값이 두 번째 인덱스보다 크면 첫 번째 인덱스를 뒤로 한 칸 밀고 두 번째 인덱스를 첫 번째 인덱스 자리로 삽입.

3. 동일하게 인덱스 자리 1씩 증가하며 같은 순서 반복

>>   n 번째 인덱스를 비교하는 경우

n-1 번째 인덱스와 값 비교, n-1번째 인덱스보다 작으면 n-1 인덱스 값 뒤로 한 칸 밀기

n-2번째 인덱스와 값 비교, n-2번째 인덱스보다 작으면 n-2 인덱스 값 뒤로 한 칸 밀기

 

 

 

코드 구현

import java.util.Scanner;

public class Main {
  public int[] solution(int n, int[] arr){
    for(int i = 1; i < n; i++){
      int tmp = arr[i];
      int j;
      for(j = i-1; j >= 0; j--){
        if(tmp < arr[j]){       //키 값이 더 작으면
          arr[j+1] = arr[j];    //뒤로 한 칸 이동
        }else{                  //키 값이 더 크면
          break;                //멈추고
        } 
      }                         //for문 탈출 후
      arr[j+1] = tmp;           //빈 인덱스에 key값 삽입
    }
    return arr;
  }

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

    int n = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++){
      arr[i] = in.nextInt();
    }
    in.close();

    for(int x : t.solution(n, arr))
      System.out.print(x+" ");
  }
}