정리 노트

이 포스트는 삽입 정렬에 대해 알고 있다는 가정 하에 작성되었습니다. 저번에 적은 삽입 정렬에 관한 글이 있으니 참고하실 분은 참고하시면 됩니다. 2022.09.12 - [알고리즘] - 삽입 정렬(Insertion Sort) Shell Sort 기존의 삽입 정렬은 정렬을 위해 배열 내의 원소 간 이동이 많이 발생한다는 단점이 생깁니다. 만일 정수형 배열에서 원소 '1'이 배열의 가장 끝에 있다고 해봅시다. 그럼 원소 '1'을 배열의 거의 앞에 놓기 위해 거의 모든 원소들이 한 칸씩 옆으로 이동하는 연산을 수행해야 합니다. Shell 정렬은 이러한 문제점을 개선하기 위해 생겼습니다. Shell 정렬에서는 gap만큼 떨어진 원소들끼리의 삽입 정렬을 진행해서 적은 데이터의 이동으로 작은 값을 앞으로 당겨올 수..