[알고리즘] 삽입 정렬 InsertionSort

정렬 알고리즘이란?

정렬 알고리즘은 배열의 원소들을 조건에 맞게 순서대로 정렬하는 알고리즘입니다. 원소들이 어떤 순서로 들어오는지에 따라 적절한 정렬 알고리즘을 선택할 수 있습니다.

선택 기준

1. 시간 복잡도: 알고리즘이 실행되는 데 소요되는 시간
2. 공간 복잡도: 알고리즘이 사용하는 메모리의 양
3. 안전성 (Stability): 동일한 값의 원소들의 순서가 유지되는지 여부

정렬 알고리즘 종류와 시간 복잡도

정렬 알고리즘 종류	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도
BubbleSort (버블 정렬)	O(n)	O(n^2)	O(n^2)
SelectionSort (선택 정렬)	O(n^2)	O(n^2)	O(n^2)
InsertionSort (삽입 정렬)	O(n)	O(n^2)	O(n^2)
MergeSort (병합 정렬)	O(n log n)	O(n log n)	O(n log n)
RadixSort (기수 정렬)	O(nk)	O(nk)	O(nk)
QuickSort (퀵 정렬)	O(n log n)	O(n log n)	O(n^2)

 

현재 정렬을 사용할 때는 대부분 퀵 정렬을 사용합니다. 병합 정렬이 최악의 조건에서 더 빠를 것 같다고 생각할 수 있지만, 정렬 알고리즘을 선택할 때는 시간 복잡도뿐만 아니라 공간 복잡도도 고려해야 합니다.

병합 정렬은 메모리를 많이 사용하므로, 여러 가지를 고려하여 정렬 알고리즘을 선택해야 합니다.

 

 

InsertionSort(삽입 정렬)란?

삽입 정렬(Insertion Sort)은 정렬 알고리즘 중 하나로, 현재 비교하는 요소(target)와 해당 요소의 이전 요소들을 비교하며 조건에 맞게 정렬하는 방법입니다. 삽입 정렬은 배열의 두 번째 요소부터 시작하여, 각 요소를 올바른 위치에 삽입하는 방식으로 동작합니다.

 

삽입 정렬 과정

1. 초기 설정: 두 번째 요소부터 시작하여 배열의 각 요소를 순차적으로 탐색합니다.
2. 현재 요소 선택: 현재 탐색 중인 요소를 "타겟"으로 설정합니다.
3. 비교 및 이동: 타겟 요소와 그 이전 요소들을 비교하여 타겟 요소가 삽입될 위치를 찾습니다. 이전 요소가 타겟 요소보다 크면, 이전 요소를 한 칸 뒤로 이동시킵니다.
4. 삽입: 타겟 요소를 알맞은 위치에 삽입합니다.
5. 반복: 배열의 끝까지 이 과정을 반복합니다.

 

삽입 정렬 특징

1. 비효율적인 성능: 배열이 이미 정렬되어 있는 경우 O(n)의 시간 복잡도를 가지지만, 일반적인 경우와 최악의 경우에는 O(n^2)의 시간 복잡도를 가집니다. 이는 데이터의 크기가 커질수록 비효율적입니다.
2. 메모리 사용: 삽입 정렬은 추가적인 메모리 공간을 거의 사용하지 않으므로, 공간 복잡도는 O(1)입니다.
3. 단순성: 구현이 간단하고 이해하기 쉬운 알고리즘입니다.
4. 안정성: 안정 정렬 알고리즘으로, 동일한 값의 원소들의 순서가 유지됩니다.

 

 

코드로 작성하기

직접 하시고 싶은 분들이 있을 수 있으니 코드는 숨기겠습니다.

코드를 보고 싶다면 더보기 클릭:

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 3, 6, 1, 8, 10, 2, 9, 7, 4};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));  // 정렬된 배열 출력
    }
    
    // 삽입 정렬 함수
    public static void insertionSort(int[] arr) {
        // 배열의 두 번째 요소부터 시작
        for (int i = 1; i < arr.length; i++) {
            int target = arr[i];  // 현재 요소를 타겟으로 설정
            int j = i - 1;
            
            // 타겟 요소를 알맞은 위치에 삽입하기 위해 이전 요소들과 비교 및 이동
            while (j >= 0 && arr[j] > target) {
                arr[j + 1] = arr[j];  // 이전 요소를 한 칸 뒤로 이동
                j--;
            }
            arr[j + 1] = target;  // 타겟 요소를 올바른 위치에 삽입
        }
    }
}