- 전체
- 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)의 성능을 가진다.
본 웹사이트는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
댓글 0
| 번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
|---|---|---|---|---|
| 5 |
파이선 애드온을 이용한 블랜더 2.6 : Creating a Blender 2.6 Python add-on
 | 졸리운_곰 | 2017.08.15 | 483 |
| 4 | blender import/export script | 졸리운_곰 | 2017.08.13 | 1594 |
| 3 | blender python 퀵스타드 매뉴얼 : blender python quick start | 졸리운_곰 | 2017.08.13 | 1394 |
| 2 |
블랜더 파이썬 애드온 개발 : blender python addon dev
| 졸리운_곰 | 2017.08.13 | 3386 |
| 1 |
Python Scripting for the Blender Game Engine
| 졸리운_곰 | 2017.08.13 | 736 |