- 전체
- 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 자료구조 [파이썬으로 구현한 알고리즘] (5) 삽입 정렬(Insertion Sort)
2018.02.27 17:47
[파이썬으로 구현한 알고리즘] (5) 삽입 정렬(Insertion Sort)
삽입 정렬은 이미 정렬 된 자료 리스트에서 새로운 자료를 적절한 위치에 삽입하는 동작을 반복하여 정렬하는 방법이다. 비교적 적은 비교와 많은 교환이 일어난다.
파이썬으로 삽입 정렬을 구현해 보자.
파이썬으로 삽입 정렬을 구현해 보자.
#!/usr/bin/python
import random
def insertion_sort(random_list):
random_list.insert(0, -1)
for start_index in range( 2, len(random_list) ):
temp = random_list[start_index]
insert_index = start_index
# insert index serch
while random_list[insert_index-1] > temp:
random_list[insert_index] = random_list[insert_index-1]
insert_index = insert_index - 1
random_list[insert_index] = temp
del random_list[0]
def Main():
list = []
for i in range(10):
list.append( random.randint(1,10) )
print "< Before Sort >"
print list
insertion_sort(list) # now sorting!
print "< After Sort >"
print list
Main()
import random
def insertion_sort(random_list):
random_list.insert(0, -1)
for start_index in range( 2, len(random_list) ):
temp = random_list[start_index]
insert_index = start_index
# insert index serch
while random_list[insert_index-1] > temp:
random_list[insert_index] = random_list[insert_index-1]
insert_index = insert_index - 1
random_list[insert_index] = temp
del random_list[0]
def Main():
list = []
for i in range(10):
list.append( random.randint(1,10) )
print "< Before Sort >"
print list
insertion_sort(list) # now sorting!
print "< After Sort >"
print list
Main()
가장 앞에 -1 이라는 원소를 추가했다가 삭제하는 이유는 while문의 조건을 하나로 하기 위함이다. 이런 루틴이 없으면 insert_index가 0보다 큰지도 판별 해야 한다. 이렇게 임시로 값을 넣어서 조건문을 하나 줄이는 기법을 보초 기법 이라고 한다.
현재 구현된 삽입 정렬은 삽입 될 위치를 찾을 때 앞에서 부터 차례대로 찾는 순차 검색을 한다. 검색법 중에 이분 검색을 이용 하면 삽입 할 위치를 빠른 속도로 찾을 수 있다. 삽입 정렬은 이중 루프문으로 구성 되어있기 때문에 O(N^2)의 성능을 가진다.
본 웹사이트는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
