[Algoritm]초보자도 쉽게 삽입정렬 이해하기! - java언어, 백준문제풀이

삽입정렬(Insertion Sort)

 

 

삽입정렬 개념, 삽입정렬이란?

 

배열의 모든 원소를 앞에서부터 차례대로 이미 정렬된 배열 원소들과 비교하여, 자신의 위치를 찾아 삽입하는 정렬알고리즘이다.

즉 2번째 원소부터 시작하여 앞 쪽의 원소와 비교해 해당 원소가 삽입될 위치를 찾는다.

 

좀 더 쉽게 설명하면, 삽입정렬은 배열하나를 두개의 부분집합으로 나눈다. 하나는 '정렬된 앞 쪽 집합'(S), 나머지 하나는 '정렬되지 않은 뒷 쪽 집합'(U)이다. 차례가 한번씩 지날 때마다 S의 원소는 하나씩 늘어나고, U의 원소는 하나씩 줄어든다. 그러다 U가 공집합이 되면 삽입 정렬이 끝난다. 

 

Stable sorting, in-place 알고리즘이다.

 

그림으로 이해하기

자료 출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

시간 복잡도

최악

• O(n^2)
  • 입력 자료가 역순인 경우

최선

• O(n)
  • 이미 정렬된 경우, 원소의 이동없음.
  • 원소 수만큼 각 한번의 비교만 이루어짐

 

장단점 (사용하면 좋은/나쁜 상황)

장점

• Stable sorting 으로 안정된 정렬이다.
• 알고리즘 구현이 매우 간단하여 원소 수가 적을 경우, 다른 복잡한 정렬보다 유리한 방법이 될 수 있다.
• 대부분의 원소가 정렬되어있는 경우 효율적이다.
• 같은 시간 복잡도인 선택정렬, 버블정렬과 비교하면 성능적으로 우수하다.
• 별도의 추가 공간을 사용하지 않는다. 

단점

• 원소수가 많고, 데이터의 크기가 클 경우 적합하지 않다.(배열이 길어질수록 효율이 떨어짐)
• 비교적 원소들이 많이 이동한다. 

 

소스코드 예시와 설명 (백준문제_ java)

백준 11399문제 정렬로 풀기

  문제 -  https://www.acmicpc.net/problem/11399

  조건 -  

 

import java.util.*;

public class 삽입정렬_ATM인출시간계산_11399 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        for(int i=0; i<N;i++) a[i] = sc.nextInt();

        for(int i=1;i<N;i++){ //2번째 원소부터 삽입위치찾을거임
            int j = i-1; //비교해야하는 방의 인덱스
            int key = a[i]; // 위치가 계속 변하기 때문에 원소를 빼둠
            while(j>=0 && a[j]>key) {
                //1번방부터 조회, 앞의 값과 비교하여 작으면 앞으로(클때까지반복)
                a[j+1]=a[j];
                j--;
            }
            a[j+1]=key; // 앞칸 비워놓고 한칸씩 뒤로 미루다가 다 미뤄졌을때, 젤 앞칸에 key채움
        }//for
        
        int sum = 0;
        int result = 0;
        for(int i=0;i<N;i++)//합산값 출력
        {
            sum += a[i];
            result += sum;
        }
        System.out.println(result);
    }
}