Java-알고리즘 ( insertion sort )

1. 삽입 정렬 (insertion sort)란?

• 삽입 정렬은 두 번쨰 인덱스부터 시작
• 해당 인덱스(key 값)앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B 값을 뒤 인덱스로 복사
• 이를 key값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key값을 이동

2. 어떻게 코드로 만들까? 

알고리즘 연습 방법에 기반해서 단계별로 생각해봅니다.

• 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 비교 로직을 이해해보자)
  • 예: dataList: [9, 3, 2, 5]
    • 처음 한번 실행하면, key값은 9, 인덱스(0) - 1 은 0보다 작으므로 끝: [9, 3, 2, 5]
    • 두 번째 실행하면, key값은 3 9보다 3이 작으므로 자리 바꾸고 끝: [3, 9, 2, 5]
    • 세 번째 실행하면, key값은 2 9보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝: [2, 3, 9, 5]
    • 네 번째 실행하면, key값은 5 9보다 5가 작으므로 자리 바꾸고 3보다는 5가 크므로 끝: [2, 3, 5, 9]  

3. 알고리즘 구현

// src/com.company/Sort/InsertionSort.java

package com.company.Sort;

import java.util.ArrayList;
import java.util.Collections;

public class InsertionSort {
    public static ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        for(int idx1 = 0; idx1 < dataList.size() - 1; idx1++) {
            for(int compareIdx = 0; compareIdx < idx1 + 1; compareIdx++) {
                if(dataList.get(idx1 - compareIdx + 1) < dataList.get(idx1 - compareIdx)) {
                    Collections.swap(dataList, idx1 - compareIdx + 1, idx1 - compareIdx);
                } else {
                    break;
                }
            }
        }
        return dataList;
    }
}

// src/Main.java

package com.company;

import com.company.Sort.InsertionSort;

import java.util.ArrayList;

public class Main {
        ArrayList<Integer> testData = new ArrayList<Integer>();

        for(int i = 0; i < 100; i++) {
            testData.add((int)(Math.random() * 100));
        }
        InsertionSort.sort(testData);

        System.out.println(testData);
    }
}

4. 알고리즘 분석

• 반복문이 두 개 O(n^2)
  • 최악의 경우, n * (n - 1) / 2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)