Insertion sort_오름차순으로 정렬하기

🔵 ThingsILearned

✔️ 삽입정렬이란

“정렬되지 않은 데이터”를 정렬된 데이터 사이에 끼워 넣는 방식

✔️ Insertion sort: complexity of O(n) or O(n^2)

이미 데이터가 정렬이 되어 있다면 시간 복잡도는 O(n)이겠지만,
만약 데이터가 역순으로 되어 있다면 가장 작은 값을 찾기 위해서는 매번 맨 앞까지 가야하니까 시간 복잡도가 O(n^2)이다.

✅ Insertion sort

package com.example.ct_inflean_2024.String;

import java.util.*;

class Main {

    public int[] solution(int n, int[] input){
        for(int i=1; i<n; i++){
            int tmp= input[i];
            int j;
            for(j=i-1; j>=0; j--){
                if(input[j] >tmp){
                     input[j+1] = input[j]; //3번 단계
                }else {
                    break; //⭐️ 시간복잡도
                }
            }
            input[j+1] = tmp; //j가 멈춘 곳을 tmp로 설정
        }

        return input;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc= new Scanner(System.in);
        int n= sc.nextInt();
        int[] input= new int[n];
        for(int i=0; i<n; i++){
            input[i]= sc.nextInt();
        }
       for(int i: T.solution(n, input)) {
           System.out.print(i+ " ");
       }
    }
}
//⭐️input:
6
11 7 5 6 10 9
//⭐️output:
5 6 7 9 10 11

1. i는 1부터, j는 i앞에서부터 감소하면서 0전까지 for문을 돈다.
   
2. 변수 tmp에 i값을 저장해 놓는다.
   
3. j값이 tmp보다 크다면, j값을 하나 뒤로 밀어버린다.
   
4. 그리고 또 앞에 값들과 비교하고, j값이 tmp보다 크다면 또 j값을 뒤로 민다.
   
5. 그러다가 j값이 tmp보다 작지 않은 경우가 오면, for문을 멈춰버린다. break
   ⭐️ 그래서 정렬된 데이터의 경우 시간복잡도가 O(n)인 것이다.
   
6. 그리고 for문이 멈춘 곳 뒤에다가 tmp값을 삽입한다.
   
7. 그러면 0부터 i까지의 값까지는 정렬이 제대로 되었을 것이다.
   
8. 이렇게 정렬된 데이터 사이에서 내 자리를 찾아서 삽입하는 알고리즘이므로 이름이 삽입정렬이다.
   

💡 Reference

https://jinhyy.tistory.com/9