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

정렬 알고리즘 중에

하나인 삽입 정렬

입니다.

이번 포스팅 에서는

삽입 정렬에 대해서

최대한 알기 쉽게

써보도록 하겠습니다.

삽입 정렬은

화투나 카드패 섞을때

적용하는 방법으로써

맨 처음값을

기준으로 잡고

순차적으로 값을 비교하면서

적당한 위치에

정렬하는 알고리즘

입니다.

설명 하기에 앞서서

아래 그림처럼

색깔에 따라

보시면 됩니다.

아래 처럼 정렬이

되지 않은 배열이

있다고 하고

제일 처음 값을

이미 정렬이 되었다고

치고 고정시켜 놓습니다.

그다음 순차적으로

값을 체크하고 이미 정렬이

된 값들과 비교해서

알맞은 위치에

집어 넣는 과정을

반복 합니다.

모든 루프를 돌고나면

아래처럼 정렬이

완료 됩니다.

소스코드로 표현하면

대략 아래같이

표현 됩니다.

void InsertionSort(int A[], int N) { for(int Pick = 1; Pick < N; ++Pick) { int Current = Pick; int Temp = A[Pick]; for(; (Currnet > 0) && (A[Current-1] > A[Temp]); --Current) { A[Current] = A[Current-1]; } A[Current] = A[Temp]; } }

참조

C,C++ 로

배우는 자료구조론

삽입 정렬의

복잡도는

최적일 경우에는

이지만..

최악의 경우일때는

가 됩니다.

따라서

삽입 정렬도

엄청 효율적이지 못한

불안정한 정렬

입니다.

이상 삽입 정렬

알고리즘 이었습니다.