[알고리즘] 삽입 정렬(Insertion sort) 알아보기

안녕하세요 🌟🌟

오늘 포스팅할 내용은 정렬 알고리즘 중, [삽입 정렬]입니다.

이번에도 역시 [버블 정렬], [선택 정렬]과 비슷한 방식으로 진행되고, 마찬가지로 구현이 어렵지 않습니다.

이제 삽입 정렬에 대해서 자세하게 알아보도록 하겠습니다 :)

* 다양한 정렬 알고리즘

1. 버블 정렬
2. 선택 정렬
3. 삽입 정렬
4. 병합 정렬
5. 퀵 정렬
6. 힙 정렬

 

---

삽입 정렬(Insertion Sort)

---

• 이미 정렬된 상태에서 새로운 요소를 추가하여 비교한 후, 재정렬하는 방식
• 손 안의 카드를 정렬하는 방법과 유사

 

01. 그림으로 방식 이해하기

어센딩 방식을 예시로 들었습니다.

 

아래 [9, 1, 4, 2, 7]을 가진 배열이 있습니다.

1) 정렬을 하기 위해서 먼저 인덱스 1번 데이터를 인덱스 0번의 데이터와 비교합니다.

• 삽입 정렬은 다른 정렬과 다르게 인덱스 1번부터 꺼내서 앞에 있는 인덱스와 비교를 하는 방식인데요. 위 그림을 보면, 인덱스 1번의 데이터 1을 앞 인덱스인 9와 비교를 하게 됩니다. 그리고 인덱스 0번의 값이 크기 때문에 자리를 교체하게 됩니다.

사실 여기까지를 봤을 때는 다른 정렬과 차이를 느끼기 힘듭니다. 이제 다음으로 넘어가겠습니다.

 

2) 다음은 인덱스 2번의 값인 4를 꺼내어 앞 인덱스의 값들과 역순으로 비교합니다.

• 첫 번째) 인덱스 2의 값 4와 인덱스 1의 값 9를 비교합니다.
  → 9보다 4가 작기 때문에 두 인덱스의 자리를 교체합니다.
• 두 번째) 4와 인덱스 0의 값 1을 비교합니다.
  → 이번에는 1이 작기 때문에 자리를 교체하지 않습니다.

인덱스 2까지 정렬된 결과

 

 

3) 다음 인덱스 3번의 값 2를 꺼내어 앞과 동일하게 앞 인덱스의 값들과 역순으로 비교합니다.

 

4) 마지막 7도 꺼내어 동일하게 진행합니다.

• 이번 과정까지 진행해서 정렬이 완료된 것을 확인할 수 있습니다.
• 여기서 중요한 포인트가 있습니다. 마지막 과정에서 7은 두 번만 비교한 것이 보이는데요. 그 이유는 사실상 7을 제외해서는 모두 정렬된 상태였습니다. 따라서 두 번째 4와 비교한 결과 7이 더 크다는 것을 알았고, 그 이하는 당연히 작기 때문에 더 이상 비교를 할 필요가 없습니다.

---

02. 코드 구현

참고 클래스 : Collections.swap
-> Java.util의 클래스
-> Collections.swap(List<?> list, int i, int j);
-> list의 index i와 index j 의 자리를 바꿈.

참고 클래스 : Math.random
-> Java.lang 의 클래스
-> Math.random()
-> 0 이상 1 미만의 부동 소수점 값을 가져올 수 있음 => 0.12

1) 정렬 메서드 구현

public ArrayList<Integer> sort(ArrayList<Integer> dataList) {

	// i는 비교를 하기 위해 꺼내는 카드, 인덱스 1부터 시작
    for(int i = 1; i < dataList.size(); i++) { 	// outter

       // 꺼낸 카드보다 작은 인덱스들과 비교(i-1)
        for(int j = i-1; j > -1; j--) {	// inner

            // 꺼낸 카드가 비교하는 카드(인덱스)보다 작을 경우 자리 교체
            if(dataList.get(i) < dataList.get(j)) {
                Collections.swap(dataList, i , j);
                i = j; // 자리가 교체외었으므로 인덱스를 j로 대입
            } else {
                break; // 순회 도중 꺼낸 카드가 비교 카드(인덱스)보다 클 경우 inner for문 종료
            }
        }

    }
    
    return dataList; // 정렬된 배열 반환

}

• 삽입 정렬에서 index 1번부터 카드를 꺼내기 때문에 outter for문의 i를 1로 초기화합니다.
• 이후 꺼낸 카드보다 작은 인덱스의 값들과 역순으로 비교를 하기 때문에 i-1로 초기화하고, j-- 로 점차 감소하게 했습니다.
• inner for문을 반복하는 동안 꺼낸 카드가 비교 카드보다 작다면 자리를 교체합니다.
• 자리를 교체한 후 j 가 -1을 진행해서 꺼낸 카드와 이어서 비교를 해야 합니다. 하지만 꺼낸 카드의 인덱스는 자리를 교체했기 때문에 한 칸 앞으로 이동된 상태입니다. 그렇기 때문에 꺼낸 index 또한 방금 비교한 j가 되어야 하는 것입니다. 따라서 if문 안에 j = j로 처리를 해주었습니다.
• 만약 비교도중 꺼낸 카드가 비교 카드보다 작지 않다면 더 이상 비교를 할 필요가 없기 때문에 바로 inner for 문을 종료합니다.2) 실행

public static void main(String[] args) {

    ArrayList<Integer> dataList = new ArrayList<>();

    for(int i = 0; i < 50; i++ ) {
        dataList.add((int)(Math.random() * 100));
    }

    InsertionSort insSort = new InsertionSort();

    System.out.println(insSort.sort(dataList));
}

 

결과는 랜덤 수들의 배열을 정렬하여 출력한 내용입니다. 제대로 출력이 되었습니다.

 

03. 시간 복잡도

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

이번에도 역시 이중 for문이 사용되면서 O(n^2)의 시간 복잡도를 예상할 수 있습니다. 

정말 최악의 상황은 모두 비교를 진행하지만, 이전에 포스팅했던 [버블 정렬], [선택 정렬]과 동일하게 등차수열 합만큼 횟수가 나옵니다. 즉, 시간 복잡도는 역시나 O(n^2)입니다. 

그래도 차이점은 비교 도중 자리를 교체할 필요가 없을 때 break로 for문을 종료하기 때문에 효율성을 가질 수 있습니다. 만약 최선의 상태인 배열이라면 O(n)의 시간 복잡도를 갖게 됩니다.