삽입 정렬
-
[알고리즘] 삽입 정렬(Insertion Sort)알고리즘 & 자료구조/알고리즘 2021. 3. 6. 17:32
아래의 숫자들을 오름차순으로 정렬한다고 생각해보자 1 10 5 8 7 6 4 3 2 9 버블 정렬과 선택정렬을 사용 할 수도 있지만, 삽입 정렬을 사용하면 특정상황에 따라서는 보다 효율적으로 정렬할 수 있다. 다른 정렬들은 무조건 위치를 바꾸는 방식이였지만, 삽입정렬의 다른점은 '필요할 때만' 위치를 바꾼다는 것이다. 예를들어 보자, 아래와 같은 숫자들을 오름차순 정렬한다고 했을때, 삽입정렬은 1 10 5 8 7 6 4 3 2 9 바로 옆의 10과 대소를 비교한다. 10은 1의 앞 혹은 지금 현재 자리에 있을 수 있는데, 오름차순이기때문에 현재 위치를 그대로 유지하면 된다. 그다음 10 과 5를 비교해보면, 5가 더 작기때문에 10과 5의 자리를 바꿔준다. 조금 더 쉽게 생각하면 빈칸이 있다고 생각을 해..