[알고리즘] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

특징

1. 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다.
2. 제자리 정렬(In-place Sort): 입력 배열 이외에 추가적인 메모리를 사용하지 않습니다. 입력 배열 내에서 정렬이 수행됩니다.
3. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다.

알고리즘 동작 방식

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 처리합니다. 정렬되지 않은 부분의 첫 번째 원소를 정렬된 부분에 삽입하는 과정을 반복하여 전체 배열이 정렬될 때까지 진행합니다.

1. 정렬되지 않은 부분에서 첫 번째 원소를 선택합니다.
2. 이 원소를 정렬된 부분의 올바른 위치에 삽입합니다.
3. 나머지 정렬되지 않은 부분의 원소들을 한 칸씩 뒤로 이동시킵니다.
4. 정렬되지 않은 부분의 다음 원소를 선택하고, 이를 정렬된 부분에 삽입합니다.
5. 위의 과정을 정렬되지 않은 부분이 없어질 때까지 반복합니다.

장점

1. 구현이 간단하고 이해하기 쉽습니다.
2. 작은 규모의 입력에 대해서는 효율적입니다.
3. 제자리 정렬이므로 메모리 사용량이 작습니다.

단점

1. 평균 및 최악의 경우에 대해 O(n^2)의 시간 복잡도를 가집니다. 입력 배열이 이미 거의 정렬되어 있는 경우라도 모든 원소를 비교하고 이동해야 하기 때문에 비효율적입니다.
2. 대량의 데이터를 정렬할 때는 다른 알고리즘들보다 성능이 떨어질 수 있습니다.

요약하면, 삽입 정렬은 구현이 간단하고 작은 입력에 대해서는 효율적인 정렬 알고리즘입니다. 하지만 대량의 데이터에 대해서는 다른 알고리즘들보다 성능이 떨어질 수 있으며, 최악의 경우에는 시간 복잡도가 O(n^2)이기 때문에 효율적인 알고리즘이라고는 할 수 없습니다.

https://www.pinterest.co.kr/pin/420734790180626311/

void DoInsertionSort()
{
	vector<int> arr;
	arr.assign(rand() % 30, int());

	for (auto& num : arr)
		num = rand() % 100;

	cout << "Before Sort" << endl;
	
	for (auto num : arr)
		cout << num << " ";

	cout << endll << "After Sort" << endl;

	InsertionSort(arr);
	for (auto num : arr)
		cout << num << " ";

	cout << endll;

	Pause;
	return;
}

void InsertionSort(vector<int>& arr)
{
	for (int i = 1; i < arr.size(); i++)
	{
		int key = arr[i];
		int j;

		for (j = i - 1; j >= 0; j--)
		{
			if (arr[j] < key)
				arr[j + 1] = arr[j];
			else
				break;
		}
		arr[j + 1] = key;
	}
}

기본코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <unordered_map>
#include <fstream>
#include <ostream>
#include <sstream>
#include <cctype>
#include <cmath>

#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0);
using namespace std;

int main() 
{
    fastio;
    
    int array[10] = { 1,10,5,8,7,6,4,3,2,9 };
    int i, j, temp;

    for (i = 0; i < 9; i++)
    {
        j = i;
        while (array[j] > array[j + 1])
        {
            swap(array[j], array[j + 1]);
            j--;
        }
    }
    for (i = 0; i < 10; i++)
    {
        printf("%d ", array[i]);
    }

    return 0;
}