04강 - 삽입 정렬 (Insertion Sort)

삽입정렬이다!

영상은 이해가 갔지만 블로그에 추가 참고 자료가 있어서 그거까지 이해하고 정리해보겠다

 

---

[ 삽입 정렬 ]

각 숫자를 적절한 위치에 삽입하여 정렬한다

 

이 또한 정렬 알고리즘 중에서는 비효율적인 알고리즘이다

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법이다

하지만 무조건 위치를 바꾸는 다른 정렬 방식과는 달리 삽입 정렬은 필요할 때만 위치를 바꾼다

 

예전부터 사실 삽입정렬이 잘 이해가 안가서 외우기만 했지 제대로 이해한건 이번이 처음이다

직접 한 싸이클씩 해보면서 이해했다..

얘의 장점은 정렬할 순서인 숫자의 앞에 숫자들은 이미 정렬이 되었기때문에, 정렬할 숫자가 자기자리 찾아서 들어가면 더이상 그 싸이클에서는 자리를 바꿀 필요가 없다는것이다!!

그래서 얘는 거의 정렬이 끝난 알고리즘에서는 최고의 효율을 보여준다!

하지만 시간복잡도는 worst case 기준으로 하기 떄문에 최악에서는 매번 자리를 바꾸는 케이스라 O(N^2)이다

그래도 그 3개의 정렬 중에서는 그나마 효율적이다 그나마,,ㅋㅋㅋ

 

 

[ 코드 ]

#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    int arr[10] = {1,10,5,8,7,6,4,3,2,9};
    int j, temp;
    for(int i=0;i<9;i++)
    {
        j=i; //정렬할 원소 선택
        while(j>=0 && arr[j]>arr[j+1])
        {
            temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;
            j--;
        }
    }

    for(int i=0;i<10;i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

안에 while문 보면 정렬할 원소가 자리를 바꾸면 그 싸이클은 정렬이 끝나기때문에

break 포인를 알 수 있다는게 최고 장점이다

뭔말인지 알지??

 

[ 시간 복잡도 ]

이 알고리즘은 worst case에서는 매번 자리를 바꿔야 되니까 O(N^2)이다.

하지만 거의 정렬이 된 수열일 경우에는 가장 효율적인 알고리즘이다.

 

삽입 정렬의 시간 복잡도는 O(N^2)이다

---

이건 보충자료!

얘가 거즘 정렬된 수열을 만났을떄는 최고의 효율을 보여준다는걸 증명하는거임!!

암튼 끝!