Computer Science/Algorithm :: 알고리즘
[알고리즘] 삽입 정렬 - 앞에서 꺼내서 뒤부터 비교
HJPlumtree
2021. 3. 18. 21:03
삽입 정렬
정렬이 필요한 요소를 뽑아서 적당한 곳에 삽입
두 부분으로 나눈다, 정렬된 집합과 정렬되지 않은 집합으로 가정
- 부분집합 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}