자료구조를 놓은 지 너무 오래되어서 가장 기본인 정렬 문제도 정리할 겸 이 문제를 풀었다. 문제에 대한 설명에서 시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있고, 그 예로 삽입 정렬, 거품 정렬 등이 있다고 한다. 그래서 그냥 삽입 정렬로 풀어보기로 했다.(거품 정렬은 다음 포스팅에서 해보도록 하겠다) 그럼 우선 삽입 정렬에 대해 정리해보자. 삽입 정렬(insertion sort) 삽입 정렬이란 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입해 정렬을 완성하는 알고리즘이다. 구체적인 과정을 살펴보겠다. 삽입 정렬은 2번째 자료부터 시작하여 그 요소의 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자..
