[SORT] Insertion Sort (삽입 정렬)

Goal

정렬 알고리즘 중 Insertion Sort 에 대해 알기
Insertion Sort의 장· 단점
시간 복잡도 이해하기
자바로 구현할 줄 알기

Insertion Sort (삽입 정렬) 알고리즘

"순서대로 뽑고, 적당한 위치에 삽입"
배열의 모든 요소를 왼쪽의 모든 요소들과 비교하여 지정 자리에 자료를 삽입하면서 정렬하는 알고리즘.
아래 예시를 통해 이해해 보자.

기억★ 두번째 data 부터 시작할 것

PASS 1 - 왼쪽 값과 오른쪽 값을 비교한다.

• 왼쪽 데이터 값과 오른쪽 데이터 값(처음 상태: 두번 째 data 값)을 비교한다.
• 왼쪽 데이터 값이 더 크다면, 오른쪽 값과 비교한다.
• 왼쪽 데이터 값이 존재하지 않을 때까지, 비교 후 삽입 반복
• 왼쪽에 데이터가 더이상 존재하지 않는다면, 현재 상태(kEY값)를 오른쪽으로 이동시킨다.

PASS 2 현재 상태(KEY)가 배열의 끝에 도달할 때까지 PASS1를 반복한다.

---

Insertion Sort (삽입 정렬) 의 장 · 단점

장점:

• 안정적인 정렬 방법이다.
• 제자리 정렬(in-place sort) 이다.
• 주어진 자료 공간 이외의 공간을 사용하지 않고 정렬하는 것
  • 데이터 수가 적을 수록 유리하다.
  • 데이터가 정렬이 되어있을수록 더 효율적이다.
  • Selection Sort (선택 정렬) , Bubble Sort (버블 정렬) 보다 효율이 높다.

단점:

• 데이터 상태와 데이터 크기에 따라 성능의 편차가 심하다.

Insertion Sort (삽입 정렬) 의 시간복잡도

최선의 경우 (Best) - 자료가 정렬되어 있을 때

• 비교 횟수
  • 이동 없이 1번의 비교만 이루어진다. (ex 2,3,5,7 - 정렬되어 있는 상태일 때)
  • n-1 번 비교
  • O(n)

최악의 경우 (Worst) - 자료가 역순일 때

• 비교 횟수 & 교환 횟수
  • 각 반복마다 계속해서 비교하고 교환해야 한다. (ex 4,3,2,1)
  • (n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2
  • O(n^2)

Insertion Sort (삽입 정렬) JAVA 구현

  

    
    
      
     
  
public class InsertionSort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.valueOf(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(br.readLine());
        }

        for (int i = 1; i < n; i++) {
            // 현재 key 값과 key 위치 저장
            int key = arr[i];
            int keyIndex = i;
            for (int j = i - 1; j >= 0 && arr[j] > key; j--) {
                // 현재 key 값으로부터 왼쪽에 있는 모든 값들과 비교
                // 정렬이 안되어 있을 경우, arr[j]를 arr[j+1] (오른쪽)로 밀기
                arr[j + 1] = arr[j];
                keyIndex = j;

            }
            // 한 턴(pass)가 끝나면 최종 keyindex에 key값을 저장한다.
            arr[keyIndex] = key;

            sb.append("PASS " + i + " : ");
            for (int k = 0; k < n; k++) {
                sb.append(arr[k] + " ");
            }
            sb.append("\n");
        }

        for (int i = 0; i < n; i++) {
            sb.append(arr[i] + " ");
        }
        System.out.println(sb);
    }
}

윗 예시를 코드를 통해 똑같이 적용.

n = 6, array = [5, 10, 8, 6, 1, 3]