시래 블로그

정렬 알고리즘 중 하나인 삽입 정렬(Insertion sort)에 대해 알아보겠습니다. 이 글은 《Introduction to Algorithms》 3th edition을 정리한 것입니다. 기본 개념 삽입 정렬은 카드 게임을 할 때 우리가 카드를 정렬하는 방식과 같은 방식으로 작동합니다. 처음에는 손에 카드가 없는 상태로 시작합니다. 카드 더미에서 카드를 한 장씩 가져와서 왼손에 쥐는데, 새로 가져온 카드를 알맞은 위치에 넣습니다. 알맞은 위치를 찾기 위해서 새로 가져온 카드를 왼손에 쥔 카드와 비교합니다. 오른쪽부터 왼쪽으로 차례대로 비교합니다. 예시 a) 오른쪽으로 갈수록 큰 수가 오도록 정렬을 한다고 하겠습니다. 순서가 [5, 2, 4, 6, 1, 3]인 배열을 정렬하고자 합니다. 계속해서 카드에 ..