인하대 컴퓨터구조론 MARS sorting과제

1. Insertion assorting algorithm 사용

Insertion Sort 알고리즘은 데이터 구조와 알고리즘을 이해하는 데 중요한 정렬 기법 중 하나이다. 이 알고리즘의 기본 개념은 배열의 요소를 하나씩 정렬된 부분 배열에 삽입하는 방식으로 작동한다. 초기 상태에서 정렬된 부분 배열은 첫 번째 요소로 시작하며, 모든 요소가 정렬될 때까지 이 과정을 반복한다. 각 반복에서는 다음 요소를 정렬된 부분 배열에 적절한 위치에 삽입한다. 이러한 방식은 마치 카드 정렬을 하는 것과 비슷하다고 할 수 있다. Insertion Sort의 시간 복잡도는 최악의 경우와 평균 경우에 O(n^이다. 이는 중첩된 루프가 존재하기 때문인데, 첫 번째 루프는 n번 실행되고, 두 번째 루프는 정렬된 부분 배열에서 삽입 위치를 찾기 위해 시행되기 때문이다. 그러나 최선의 경우, 즉 배열이 이미 정렬되어 있는 경우에는 O(n)의 시간 복잡도를 가진다. 이처럼 데이터의 상태에 따라 성능이 크게 달라지기 때문에, Insertion Sort는 작은 데이터 집합에서 효율적이며, 특정 상황에서는 더 복잡한 알고리즘보다 빠를 수 있다. Insertion Sort의 주요 특징 중 하나는 안정성이다. 이는 동일한 값의 요소들이 원…