7. 삽입 정렬
알고리즘 공부
2019. 9. 25.
삽입 정렬 (Insertion Sort) 선택 정렬과 함께 인간에게 뭔가를 정렬하라고 하면 무의식으로 사용하는 대표적인 알고리즘이다. k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식으로, 평균적으론 중 빠른 편이나 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크며, 앞의 예시처럼 작은 값이 뒤쪽에 몰려있으면 (내림차순의 경우 큰 값이 뒤쪽에 몰려있으면) 최악이다. 다만 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입, 제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다. 그밖에도 배열이 작을 경우에 역시 상당히 효율적이다. 일반적으로 빠르다고 알려진 알고리즘들도 배열이 작을 경우에는 대..
