Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 3d
- GIS
- osmnx
- 3d데이터
- 패치분할
- STL
- 좌표거리
- 귀여운고래
- pyvista
- graph
- 폴더조사
- 동명이인찾기
- GNN
- 파이썬
- geojson
- python최단거리
- 지하철역좌표
- GCN
- 도커 레이어
- 알고리즘
- 데이터입수
- 이미지빌드
- Python
- Set
- geopandas
- 도커
- 그리드분할
- 컨테이너
- docker
- MESH
Archives
- Today
- Total
이것저것 기록
[알고리즘] 삽입 정렬 본문
* <모두의 알고리즘 with 파이썬>의 문제 09를 정리한 내용입니다.
1. 삽입 정렬이란?
- 자신보다 앞의 원소가 큰지 작은지 확인하여 자신의 위치를 찾아 '삽입'하는 알고리즘이다.
- 정렬되어 있는 경우는 비교를 하지 않기 때문에 버블 정렬과 달리 불필요한 비교가 줄어들었다.
2. 일반적인 삽입 정렬 알고리즘
def ins_sort(a):
n = len(a)
for i in range(1, n): # 앞 원소와 비교해야하기 때문에 가장 앞 원소는 무시한다
key = a[i] # 기준 원소
j = i - 1 # 바로 하나 앞 원소
while j >=0 and a[j] > key: # 앞 원소가 나보다 클 경우만 위치 변경
a[j+1] = a[j] # a[j+1]는 기준 원소
j -= 1 # 한 칸씩 앞으로 전진하며 비교
a[j+1] = key # 삽입할 위치
return a
d = [2, 4, 5, 1, 3]
print(ins_sort(d))
3. 위의 알고리즘은 오름차순 정렬이었습니다. 이를 큰 수에서 작은 수 순서로 나열하는 내림차순 정렬로 바꾸려면 프로그램의 어느 부분을 바꿔야 할까요?
def ins_sort(a):
n = len(a)
for i in range(1, n): # 앞 원소와 비교해야하기 때문에 가장 앞 원소는 무시한다
key = a[i] # 기준 원소
j = i - 1 # 바로 하나 앞 원소
while j >=0 and a[j] < key: # 앞 원소가 나보다 작을 경우만 위치 변경
a[j+1] = a[j] # a[j+1]는 기준 원소
j -= 1 # 한 칸씩 앞으로 전진하며 비교
a[j+1] = key # 삽입할 위치
return a
d = [2, 4, 5, 1, 3]
print(ins_sort(d))
- while문의 조건을 수정해주었다. 기존 while문은 앞 원소가 나보다 클 경우에만 앞으로 옮겼다. 알고리즘 정의를 내림차순으로 바꾼다면, 앞 원소가 나보다 작을 경우에만 기준 원소를 앞으로 옮기면 된다.
'코린이 > 코딩 기초 & 알고리즘 공부' 카테고리의 다른 글
[알고리즘] 병합 정렬 (0) | 2021.08.22 |
---|---|
[알고리즘] 선택 정렬 (0) | 2021.08.01 |
[알고리즘] 순차 탐색 (0) | 2021.08.01 |
[알고리즘] 재귀함수 - 최대공약수, 피보나치 수열 (0) | 2021.07.17 |
[알고리즘] 재귀함수 - 팩토리얼 구하기 (0) | 2021.06.20 |
Comments