Insertion Sort

로직

1. 두번째 인텍스부터 시작
2. temp에 현재 인덱스(i)의 변수 저장(정렬하려고하는 대상)
3. temp의 값(i인덱스 값)과 i-1인덱스 값을 비교한다.
4. 비교해서 i-1번째 값이 더 크다면 i-1번 값을 i번째로 복사
5. 다음 i-2번째 값과 temp값을 비교한다.
6. 만약 temp값이 비교 인덱스(j라고 하자)의 값보다 크다면 j+1번째에 temp값을 넣어 준다.

import java.io.*;
import java.util.*;

public class Solution {

    public static void insertionSortPart2(int[] ar)
    {       
        int temp;
           for(int i=1;i<ar.length;i++){
               temp=ar[i];
               for(int j=i;j>0;j--){
                  if(ar[j-1]>temp){
                       ar[j]=ar[j-1];
                       if(j-1==0){
                           ar[j-1]=temp;
                       }
                  }else{ //temp 가 더 크다면
                       ar[j]=temp;
                       break;
                  }
               }
                    printArray(ar);
           }
    }  

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
       int s = in.nextInt();
       int[] ar = new int[s];
       for(int i=0;i<s;i++){
            ar[i]=in.nextInt(); 
       }
       insertionSortPart2(ar);    

    }    
    private static void printArray(int[] ar) {
      for(int n: ar){
         System.out.print(n+" ");
      }
        System.out.println("");
   }
}

시간 복잡도와 공간 복잡도

최악의 경우 (역순으로 정렬되어 있을 경우) : O(n^2)

이미 정렬되어 있는 경우 : O(n)

시간 복잡도 : O(n^2) (최악의 경우 기준)

공간 복잡도 : O(n) (배열 하나에서 진행됨)

  public static void insertionSortPart2(int[] ar)
    {       
        int temp;
           for(int i=1;i<ar.length;i++){
               temp=ar[i];
               for(int j=i-1;j>=0;j--){
                  if(ar[j]>temp){
                       ar[j+1]=ar[j];
                       if(j==0){
                           ar[j]=temp;
                       }
                  }else{ //temp 가 더 크다면
                       ar[j+1]=temp;
                       break;
                  }
               }
                    printArray(ar);
           }
    }