삽입 정렬
-
삽입 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 5. 11:31
삽입 정렬 선택 정렬과 버블 정렬과 달리 1개짜리 배열로 시작하여 크기를 하나씩 늘려나가는 방식으로 정렬을 진행한다. 삽입 정렬 알고리즘 배열 A[1...n]에 대해 A[n] < A[i] 인 i를 찾아 A[n]과 A[i]의 자리를 바꾼다. 이 과정을 [1...n]에 대하여 반복한다. 이를 수도 코드로 나타내면 다음과 같다. 삽입 정렬 알고리즘 InsertionSort(A[], n) { for i ← 2 to n { A[1...i]의 적당한 자리에 A[n]을 삽입한다 } } ※ 삽입 정렬 알고리즘의 비교 회수는 n ~ n² 사이가 되며 시간 복잡도는 최선의 경우 Ο(n), 최악의 경우 Ο(n²)이 된다. 삽입 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. InsertionSor..