shell sort

[알고리즘][파이썬/Python] 쉘 정렬 (Shell Sort)

정의 - 일정 간격(interval) 떨어져 있는 원소들끼리 부분집합을 구성한 후 각 부분집합의 원소들에 대해서 삽입 정렬을 수행하되, 간격을 줄여가며 삽입 정렬을 반복하여 전체 원소들을 정렬하는 방식의 정렬 알고리즘 * 쉘 정렬은 삽입 정렬의 문제점을 극복하기 위해 개선한 정렬 알고리즘이다. 삽입 정렬의 경우, 주어진 자료의 정렬 상태에 따라 시간 복잡도가 많이 달라졌는데, 역순으로 정렬되어 있는 형태에 가까울수록 비교횟수가 아주 많이 늘어나는 치명적인 문제점이 존재했다. 그래서 Donald L. Shell 은 '간격(interval)'이라는 개념을 도입하여 위 언급한 문제점을 극복해내는 '쉘 정렬'을 고안해냈다. 동작 방식 0. 간격(interval) h = 정렬할 배열(혹은 리스트)의 길이 % 2 ..