[알고리즘] 삽입 정렬(Insertion sort) 의 개념 with c++

삽입 정렬이란 자료 배열의 모든 요소를 앞에서 부터 비교하고자 하는 타겟값(tmp)과 정렬된 값을 비교하여 자신의 위치를 찾아 삽입하면서 정렬해나가는 알고리즘이다. 매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교하여 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣는다. 📌정렬 과정(오름차순) 1. 2번째 원소부터 비교 시작한다 2. 이전 위치에 있는 원소들과 타겟이 되는 원소들을 비교한다(타켓 원소는 임시변수에 넣는다) 3. 타겟 원소가 이전 위치에 있던 원소보다 작다면 위치를 바꾼다 4. 이전 데이터도 차례대로 비교하며 정렬해나간다 5. 이 방법을 반복해서 정렬한다 📌특징 구현이 간단하다 배열이 길어질수록 효율이 떨어진다 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 ..