삽입 정렬(Insertion Sort)

삽입 정렬은 간단하면서도 직관적인 정렬 알고리즘입니다. 이 알고리즘은 배열의 모든 요소를 차례대로 이미 정렬된 배열 부분과 비교하여, 각 요소를 적절한 위치에 삽입하는 방식으로 동작합니다. 이 과정을 통해 배열이 점차적으로 정렬됩니다.

삽입 정렬의 작동 과정은 다음과 같습니다:

1. 배열의 두 번째 요소부터 시작하여, 해당 요소가 이전에 정렬된 배열 부분에 삽입될 올바른 위치를 찾습니다.
2. 이 요소를 그 위치에 삽입하고, 필요한 경우 나머지 요소들을 오른쪽으로 이동시켜 자리를 마련합니다.
3. 배열의 모든 요소에 대해 이 과정을 반복합니다.

   

728x90

삽입정렬의 장점:

• 간단하고 이해하기 쉽습니다: 코드 구현이 간단하여 초보자도 쉽게 이해하고 구현할 수 있습니다.
• 안정적인 정렬 방법입니다: 같은 값의 요소가 입력에 주어진 순서를 유지합니다.
• 제자리 정렬(in-place sorting)입니다: 추가적인 메모리를 거의 사용하지 않습니다.
• 부분적으로 정렬된 배열에 대해 효율적입니다: 이미 정렬된 데이터에 대해서는 매우 빠르게 동작합니다.

반응형

삽입 정렬의 단점:

• 비효율적인 정렬 방법일 수 있습니다: 배열의 크기가 크거나 요소들이 무작위로 배치되어 있을 경우, 다른 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)에 비해 성능이 떨어집니다.
• O(n^2)의 시간 복잡도를 가집니다: 각 요소를 삽입할 때마다 앞쪽의 배열을 다시 검사해야 하므로, 최악의 경우 모든 요소에 대해 이전의 모든 요소와 비교해야 합니다.

삽입 정렬의 시간 복잡도:

• 최선의 경우: O(n) - 배열이 이미 정렬되어 있는 경우
• 평균 및 최악의 경우: O(n^2) - 평균적으로 혹은 완전히 무작위로 배치된 배열을 정렬할 때

삽입 정렬의 공간 복잡도는 O(1)입니다. 추가적인 저장 공간을 거의 사용하지 않으며, 제자리에서 정렬을 수행합니다.

삽입 정렬은 작은 데이터 세트를 정렬하거나 거의 정렬된 데이터에 대해 빠른 정렬이 필요할 때 유용합니다. 그러나 크기가 큰 데이터 세트에 대해서는 다른 더 효율적인 정렬 알고리즘을 고려하는 것이 좋습니다.

 

<파이썬 코드>

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example usage
unsorted_array = [64, 25, 12, 22, 11]
sorted_array = insertion_sort(unsorted_array)
print("Sorted array:", sorted_array)

 

<C++ 코드>

#include <iostream>
using namespace std;

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int unsorted_array[] = {64, 25, 12, 22, 11};
    int n = sizeof(unsorted_array) / sizeof(unsorted_array[0]);

    insertion_sort(unsorted_array, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << unsorted_array[i] << " ";
    }
    cout << endl;

    return 0;
}

<버블 정렬, Bubble Sort>

https://tonnykang.tistory.com/179

Bubble Sort 버블 정렬