삽입 정렬(Insertion Sort)는
자기자신을 기준으로 앞에서 있는 애들과 비교하여 자신이 들어갈 자리에 들어가는 정렬입니다.
삽입 정렬이란?
내가 들어갈 자리에 쏙 들어가겠다
※소스코드
#include <iostream>
using namespace std;
int main()
{
int dataArray[6] = { 5, 3, 2, 8, 4, 6 };
for (int i = 0; i < 5; i++)
{
int temp = i;
while (dataArray[temp] > dataArray[temp + 1])
{
int data = dataArray[temp];
dataArray[temp] = dataArray[temp+1];
dataArray[temp + 1] = data;
if (--temp < 0)
break;
}
}
for (int i = 0; i < 6; i++)
{
cout << dataArray[i] << " ";
}
return 0;
}
※출력결과
먼저 시간복잡도는 반복문이 두번 들어가 있기 때문에 O(N^2)를 가집니다.
하지만 삽입 정렬은 자신을 기준으로 앞에 있는 애들은 정렬이 되어있기 때문에
선택정렬,버블정렬에 비해 효율이 높고 데이터가 만약 거의 정렬되어 있다면 다른 어떤 알고리즘에 비해 굉장히 빠른 속도를 자랑합니다.
삽입정렬 시간복잡도 : O(N^2)
