[알고리즘] 삽입 정렬 - 앞에서 꺼내서 뒤부터 비교

삽입 정렬

정렬이 필요한 요소를 뽑아서 적당한 곳에 삽입

 

두 부분으로 나눈다, 정렬된 집합과 정렬되지 않은 집합으로 가정

• 부분집합 S: 정렬된 원소
• 부분집합 U: 정렬안된 원소

 

U의 원소를 하나씩 꺼내서 S의 마지막 원소부터 비교해서 위치를 찾아 삽입

S는 하나씩 늘어나고, U는 하나씩 줄어든다

 

예시

• S(정렬된 자료)= {44}
• U(정렬안된 녀석들) = {88, 62, 38, 19, 49}

먼저 U의 88을 S의 44와 비교후 88이 크니까 44뒤에 삽입

그럼 이렇게 된다

• S = {44, 88}
• U = {62, 38, 19, 49}

그다음 62를 88과 비교한다, 62가 작으니 다음으로

다음 44와 비교한다, 62가 크니 44뒤에 집어넣는다

• S = {44, 62, 88}
• U = {38, 19, 49}

이런식으로 마지막 49까지 진행한다

U집합이 공집합이 되어 종료한다.

최종값은 S로 모두 이동된다.

S = {19, 38, 44, 49, 62, 88}