[Java+Python]삽입 정렬(Insert Sort)

<Java + Python>으로 구현한 다른 정렬:

 

[Java+Python]버블 정렬(Bubble Sort)

[Java+Python]선택 정렬(Selection Sort)

[Java+Python]병합 정렬(Merge Sort)

[Java+Python]힙 정렬(Heap Sort)

[Java+Python]퀵 정렬(Quick Sort)

[Java+Python]카운팅 정렬(Counting Sort)

 

삽입 정렬(Insert Sort)은 한 마디로 말하면 모든 요소를 정렬이 완료된 부분과 비교하여 자리를 찾아 삽입하는 알고리즘이다.

 

실생활에서 문제가 주어졌을 때 무의식적으로 가장 먼저 사용하는 알고리즘이며, 이 덕분에 가장 직관적이고 간결하다.

 

선택 정렬이나 거품 정렬 같은 알고리즘에 비해 빠른 편이며, 최선의 경우 거품 정렬과 함께 최고의 성능을 보여준다.

 

상세한 시간 복잡도는 아래와 같다.

 

특별히 배열이 작을 경우 뛰어난 효율성을 보여주며(어지간히 빠른 알고리즘도 이긴다),

 

이 때문에 고성능 알고리즘 중에는 배열의 사이즈가 클 때는 O(N Log N) 알고리즘을 쓰다가

 

정렬해야 할 부분이 줄어들면 삽입 정렬로 전환하는 경우가 있다고 한다.

 

여기서 안정적이라는 말은 쉽게 말해 중복 값의 정렬 순서가 처음과 달라지지 않는다는 뜻이다.

 

먼저 알고리즘의 작동 방식과 구현을 살펴보고 장/단점은 마무리로 보도록 하자.

 

Algotirhm

 

글로 적었던 설명을 그림으로 나타내면 위와 같이 된다.

 

N번째 원소를 그 이전까지의 정렬된 원소와 비교해서 적절한 위치에 끼워 넣는 것을 확인할 수 있다.

 

Implementation

 

직관적이고 다소 무식한 방법답게 구현은 간단한 편이다.

 

특정 배열이 주어졌을 때 해당 배열의 두 번째 원소부터 시작해서

 

(오름차순의 경우) 자기보다 작은 값을 만날 때까지 비교 교환을 반복하면 된다.

 

먼저, 자바의 경우이다.

package SortImpl;

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {

        int[] arr = {4, 2, 5, 4, 3, 1, 10, 3};

        insertSortImpl(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void insertSortImpl(int[] arr) {

        for (int i = 1; i < arr.length; i++) { // 1번 인덱스에서 시작

            int temp = arr[i];

            int j = i - 1; // 한 칸 앞 원소의 인덱스

            while (j >= 0 && temp < arr[j]) { // 배열의 맨 앞까지 가거나 시작 원소보다 작은 값을 만날 때까지

                arr[j + 1] = arr[j]; // 자리 바꾸기(뒤로 밀기)

                j--;
            }

            arr[j + 1] = temp; // 반복이 끝난 경우 j 번째 원소가 더 작다는 의미이므로 그 앞에 위치해야 한다.
        }
    }
}

[1, 2, 3, 3, 4, 4, 5, 10]

 

같은 구현을 파이썬으로 하면 아래와 같이 작성할 수 있다.

 

def insert_sort(list):
    for i in range(1, len(list)):
        tmp = list[i]  # 정렬 대상
        j = i - 1  # 바로 왼쪽부터 비교
        while j >= 0 and tmp < list[j]:  # 리스트의 0번에 닿거나 자신보다 작은 요소를 만날 때까지
            list[j + 1] = list[j]  # 비교가 끝난 요소를 오른쪽으로 밀어냄
            j -= 1  # 다음 요소와 비교
        list[j + 1] = tmp  # 자리를 찾으면 삽입


list = [1, 2, 3, 3, 4, 4, 5, 10]

insert_sort(list)

print(list)

[1, 2, 3, 3, 4, 4, 5, 10]

구현이라고 하기 민망할 정도로 별 내용이 없는 것을 확인할 수 있다.

 

끝으로 삽입 정렬의 장점과 단점을 정리하자.

 

• 장점
  
  
  • 구현이 쉽다.
  • 최악의 경우에도 공간 복잡도가 매우 낮다(O(1)). 즉, 메모리 소모가 적다.
    이는 주어진 자료에 대한 메모리 이외엔 원소 교환 시 쓰일 임시공간 정도만 필요하기 때문이다.
  • 정렬이 거의 완료된, 혹은 자료의 수가 적은 대상에 대해 효율적이다.
  • 이미 정렬이 끝난 자료구조에 원소를 삽입/삭제하는 경우 최고의 효율을 자랑한다.
  • 위에도 언급했듯이 안정 정렬이다.
  • 비슷한 복잡도를 가진 선택/거품 정렬에 비해 빠르다.
• 단점
  
  
  • 시간복잡도가 O(N2)으로 정렬 알고리즘 중 비효율적인 편에 속한다.
  • 덩치가 큰 자료형일수록 효율성이 떨어진다. 이는 버블 정렬과 선택 정렬도 공유하는 단점이다.