insertion sort(삽입 정렬)

>>>>>>> 소스코드.git

삽입정렬이란?

- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

동작 방식

3	5	1	4	2	처음 상태.
3	[5]	1	4	2	두 번째 원소(5)를 부분 리스트에서 적절한 위치에 삽입한다.
3	<5>	[1]	4	2	세 번째 원소(1)를 부분 리스트에서 적절한 위치에 삽입한다.
<1>	3	5	[4]	2	네 번째 원소(4)를 부분 리스트에서 적절한 위치에 삽입한다.
1	3	<4>	5	[2]	마지막 원소(2)를 부분 리스트에서 적절한 위치에 삽입한다.
1	<2>	3	4	5	종료.

 

소스코드(java)

- SortClass 클래스는 정렬 알고리즘을 담는 컨테이너이다. (앞으로 정렬은 이 클래스 내에 작성할 예정)

- 타입 파라미터 T를 사용하여 객체 타입을 포함하는 리스트를 정렬하는 메서드를 작성할 수 있다. (SortClass.java)

import java.util.*;

public class SortClass<T> {
    public void insertionSort(List<T> list, Comparator<T> comparator) {

        for (int i = 1; i < list.size(); i++) {
            T elt_i = list.get(i);
            int j = i;
            while (j > 0) {
                T elt_j = list.get(j - 1);
                if (comparator.compare(elt_i, elt_j) >= 0) {
                    break;
                }
                list.set(j, elt_j);
                j--;
            }
            list.set(j, elt_i);
        }
    }
}

 

insertionSort 메서드는 두 개의 인자를 받는데, 객체를 요소로 갖는 List 객체와 타입 T 객체를 비교하는 방법을 담은 Comparator 객체이다. 이 메서드는 그 자리(in place)에서 리스트를 정렬하는데, 이는 새로운 공간을 할당하지 않고 현재 리스트를 고친다는 의미이다.

 

두 개의 중첩된 반복문이 있어서 실행시간은 이차로 추측할 수 있다. 이 경우에는 추측이 맞지만, 바로 결론으로 가기전에 각 반복문의 실행 횟수가 배열의 크기 n에 비례하는지 살펴봐야한다.

 

외부 반복문은 1에서 list.size()까지 반복한다. 따라서 리스트 크기인 n에 선형적이다. 내부 반복문은 j에서 0까지 반복하므로 이것도 n에 선형적이다. 따라서 총 실행 횟수는 이차이다.

 

다시 살펴보면,

• 첫 번째, i = 1이고 내부 반복문은 한 번만 실행
• 두 번째, i = 2이고 내부 반복문은 최대 2번 실행
• 마지막으로, i = n - 1이고 내부 반복문은 최대 n - 1번 실행

따라서 내부 반복문의 총 실행 횟수는 1, 2, …, n-1 수열의 합인 n(n-1)/2가 되고 이 식의 최대 차수는 n²이 된다. 

 

최악일 때 삽입 정렬은 이차지만, 다음과 같은 특징이 있다.

1. 요소가 이미 정렬되어 있거나 거의 정렬되어 있으면 삽입 정렬은 선형이다. 특히 각 요소가 있어야 하는 자리 기준 k 이하의 위치에 있다면 내부 반복문은 k번 이하로 동작하게 되고 전체 실행시간은 O(kn)이 된다.
2. 구현이 단순하므로 오버헤드가 작다. 즉, 실행시간은 an²이지만 최대 차수의 계수인 a는 아마 작을 것이다.

따라서, 배열이 거의 정렬되어 있거나 별로 크지 않다면 삽입 정렬은 좋은 선택이다.

 

실행 코드

List<Integer> list = new ArrayList<Integer>(Arrays.asList(3, 5, 1, 4, 2));

Comparator<Integer> comparator = new Comparator<Integer>() {
    @Override
    public int compare(Integer elt1, Integer elt2) {
        return elt1.compareTo(elt2);
    }
};

SortClass<Integer> is = new SortClass<Integer>();
is.insertionSort(list, comparator);
System.out.println(list);

Integer 객체의 List로 insertionSort 메서드를 호출하는 소스코드이다.

결과
[1,2,3,4,5]

 

 

 

List<String> list = new ArrayList<String>(Arrays.asList("apple", "banana", "Air", "bbq", "aaa"));

Comparator<String> comparator = new Comparator<String>() {
    @Override
    public int compare(String elt1, String elt2) {
        return elt1.compareTo(elt2);
    }
};

SortClass<String> is = new SortClass<String>();
is.insertionSort(list, comparator);
System.out.println(list);

String 객체의 List로 insertionSort 메서드를 호출하는 소스코드이다.

결과
[Air, aaa, apple, banana, bbq]

 

Tip.

대소문자 구분없이 String 비교하려면 compareTo 대신 compareToIgnoreCase를 사용하면된다.

결과 (대소문자 구분 X)
[aaa, Air, apple, banana, bbq]