- 전체
- 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
| 번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
|---|---|---|---|---|
| 8 |
[python, 그래픽] [파이썬 활용] 마우스 자동화 (pyautogui)
 | 졸리운_곰 | 2022.11.26 | 437 |
| 7 |
[python, 그래픽] 파이썬 자동화 툴 - pyautogui 사용하기
| 졸리운_곰 | 2022.11.26 | 568 |
| 6 |
[python][image processing][파이썬][이미지프로세싱] 파이썬 영상 처리 (OpenCV)
| 졸리운_곰 | 2021.11.12 | 629 |
| 5 |
[Python, GUI tool] GUI drag & drop style GUI Builder for Python Tkinter
| 졸리운_곰 | 2021.05.17 | 613 |
| 4 |
[python 파이썬 2d 그래픽스] The Interesting Python Graphics Libraries for Python Programmers
| 졸리운_곰 | 2021.04.27 | 1227 |
| 3 | 파이선 텍스트 게임 샘플 Code for my First Text-Based Game | 졸리운_곰 | 2018.09.01 | 745 |
| 2 |
python Collada dae file Reading : 파이썬으로 콜라다 dae 파일 분석
| 졸리운_곰 | 2017.08.01 | 1064 |
| 1 |
matplotlib으로 하트 그리기
| 졸리운_곰 | 2017.03.04 | 2278 |