- 전체
- Python 일반
- Python 수학
- Python 그래픽
- Python 자료구조
- Python 인공지능
- Python 인터넷
- Python SAGE
- wxPython
- TkInter
- iPython
- wxPython
- pyQT
- Jython
- django
- flask
- blender python scripting
- python for minecraft
- Python 데이터 분석
- Python RPA
- cython
- PyCharm
- pySide
- kivy (python)
Python 자료구조 [파이썬으로 구현한 알고리즘] (6) 쉘 정렬(Shell Sort)
2018.02.27 17:48
[파이썬으로 구현한 알고리즘] (6) 쉘 정렬(Shell Sort)
쉘 정렬은 삽입 정렬의 업그레이드 판이라고 할 수 있다. 삽입 정렬은 이미 정렬된 자료 리스트에서는 매우 뛰어난 성능을 보인다. 쉘 정렬은 일정 간격 만큼 떨어진 레코드를 삽입 정렬하는 방법이다. 뛰엄 뛰엄 삽입 정렬을 하고, 간격을 줄여나가면서 삽입 정렬을 반복한다. 이런 형식으로 정렬을 반복 하게 되면, 간격이 줄어들면서 자료 리스트는 대충 정렬되어 있기 때문에 뛰어난 성능을 보이는 삽입 정렬을 할 수 있다.
< 그림 1. 쉘 정렬 과정 >
쉘 정렬이 최고의 성능을 내기 위해서는 간격을 잘 설정하는 것이다. Robert Sedgewick에 의하면 간격 h는 다음과 같은 수열에서 가장 효율적이라고 밝혀졌다.
루틴이 조금 복잡해 보인다. shell_sort()는 처음에 최적의 간격 h를 구하고, 간격을 줄이면서 삽입 정렬을 한다. 간격을 갱신하는 루프 안에 삽입 정렬 루틴이 들어있어 4중 루프문으로 되어있다.
쉘 정렬은 4중 루프로 되어있어 매우 느릴 것이라고 생각 될 것이지만, 일반적으로 O(N(logN)^2)이나 O(N^-1.25) 정도의 성능을 가진 것으로 밝혀졌다. 10,000 이하 자료 집합에서는 다른 O(NlogN) 성능을 가지는 알고리즘보다 오히려 빠를 수가 있다. 추가적인 메모리도 필요 없기 때문에, 10,000이하 자료 집합에서는 쉘 정렬을 사용하는 편이 좋다.
<그림 1>에서 보는 것처럼, 간격이 줄어들수록 삽입 정렬하는 원소들은 어느정도 정렬이 된 상태 이다. 쉘 정렬은 삽입 정렬의 장점을 이용한 것이기 때문에, 삽입 정렬에 대해 잘 숙지하고 있다면, 그리 어렵지 않다.
< 삽입 정렬 복습 >
< 삽입 정렬 복습 >
쉘 정렬이 최고의 성능을 내기 위해서는 간격을 잘 설정하는 것이다. Robert Sedgewick에 의하면 간격 h는 다음과 같은 수열에서 가장 효율적이라고 밝혀졌다.
- h = 1, 4, 13, 40, 121, 364, 1093...
- 즉, h = 3*(n-1)+1
#!/usr/bin/python
import random
def shell_sort(random_list):
h = 1
# find best 'h'
while h < len(random_list):
h = h*3+1
h = h/3
while h>0:
for i in range(h):
# setp = h, insertion sort
# ---------------------------------------------------------
start_index = i+h
while start_index<len(random_list):
temp = random_list[start_index]
insert_index = start_index
while insert_index>h-1 and random_list[insert_index-h]>temp:
random_list[insert_index] = random_list[insert_index-h]
insert_index = insert_index - h
random_list[insert_index] = temp
start_index = start_index + h
# ---------------------------------------------------------
h = h/3 # set new h
def Main():
list = []
for i in range(10):
list.append( random.randint(1,10) )
print "< Before Sort >"
print list
shell_sort(list) # now sorting!
print "< After Sort >"
print list
Main()
import random
def shell_sort(random_list):
h = 1
# find best 'h'
while h < len(random_list):
h = h*3+1
h = h/3
while h>0:
for i in range(h):
# setp = h, insertion sort
# ---------------------------------------------------------
start_index = i+h
while start_index<len(random_list):
temp = random_list[start_index]
insert_index = start_index
while insert_index>h-1 and random_list[insert_index-h]>temp:
random_list[insert_index] = random_list[insert_index-h]
insert_index = insert_index - h
random_list[insert_index] = temp
start_index = start_index + h
# ---------------------------------------------------------
h = h/3 # set new h
def Main():
list = []
for i in range(10):
list.append( random.randint(1,10) )
print "< Before Sort >"
print list
shell_sort(list) # now sorting!
print "< After Sort >"
print list
Main()
루틴이 조금 복잡해 보인다. shell_sort()는 처음에 최적의 간격 h를 구하고, 간격을 줄이면서 삽입 정렬을 한다. 간격을 갱신하는 루프 안에 삽입 정렬 루틴이 들어있어 4중 루프문으로 되어있다.
쉘 정렬은 4중 루프로 되어있어 매우 느릴 것이라고 생각 될 것이지만, 일반적으로 O(N(logN)^2)이나 O(N^-1.25) 정도의 성능을 가진 것으로 밝혀졌다. 10,000 이하 자료 집합에서는 다른 O(NlogN) 성능을 가지는 알고리즘보다 오히려 빠를 수가 있다. 추가적인 메모리도 필요 없기 때문에, 10,000이하 자료 집합에서는 쉘 정렬을 사용하는 편이 좋다.
본 웹사이트는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
