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
- GIS
- GNN
- GCN
- 도커 레이어
- graph
- 파이썬
- osmnx
- 좌표거리
- MESH
- 지하철역좌표
- 동명이인찾기
- Python
- geopandas
- 그리드분할
- pyvista
- python최단거리
- 알고리즘
- 이미지빌드
- 3d데이터
- 패치분할
- 도커
- 데이터입수
- 컨테이너
- Set
- 폴더조사
- docker
- geojson
- STL
- 귀여운고래
- 3d
Archives
- Today
- Total
이것저것 기록
[알고리즘] 선택 정렬 본문
* <모두의 알고리즘 with 파이썬>의 문제 08를 정리한 내용입니다.
1. 선택 정렬이란?
- 정렬 알고리즘 중 가장 직관적인 알고리즘이라고 한다. 초딩 때 운동장에서 키 순서대로 줄을 설 때를 생각해보자.
- 160cm, 150cm, 170cm, 180cm 가 있다고 했을 때, 우선 여기서 가장 키가 작은 150cm를 가장 앞에 세운다.
- 그리고 남은 세 명의 키를 비교하여 가장 키가 작은 160cm를 150cm 뒤에 세운다.
- 그리고 남은 두 명의 키를 비교하여 가장 키가 작은 170cm를 160cm 뒤에 세운다.
- 남은 180은 자동적으로 가장 뒤에 서게 된다.
- 위에서 설명한 정렬 방식을 일반하면 다음과 같다.
- 0 인덱스 부터 하나씩 보면서 제일 작은 값을 찾고 0번 인덱스와 교체한다.
- 그 후 1인덱스 부터 하나씩 보면서 작은 값 찾고 1번 인덱스와 교체한다.
- 전체 길이 - 1의 숫자까지 정렬하면 종료한다.
def select_sort_asc(a):
n = len(a)
for i in range(0, n-1):
min_idx = i
for j in range(i+1, n):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
return a
2. 문제 풀이
- 프로그램 8-1과 8-2의 정렬 알고리즘은 숫자를 작은 수에서 큰 수 순서로 나열하는 오름차순 정렬이었습니다. 이 알고리즘을 내림차순 정렬로 바꾸려면 어느 부분을 바꿔야 할까요?
def select_sort_desc(a):
n = len(a)
for i in range(0, n-1):
max_idx = i
for j in range(i+1, n):
print(j, a)
if a[j] > a[max_idx]:
max_idx = j
a[i], a[max_idx] = a[max_idx], a[i]
return a
- 파이썬에서 두 자료 값을 서로 바꾸기 위해 다음 문장을 사용한다.
- a[i], a[max_idx] = a[max_idx], a[i]
'코린이 > 코딩 기초 & 알고리즘 공부' 카테고리의 다른 글
[알고리즘] 병합 정렬 (0) | 2021.08.22 |
---|---|
[알고리즘] 삽입 정렬 (0) | 2021.08.15 |
[알고리즘] 순차 탐색 (0) | 2021.08.01 |
[알고리즘] 재귀함수 - 최대공약수, 피보나치 수열 (0) | 2021.07.17 |
[알고리즘] 재귀함수 - 팩토리얼 구하기 (0) | 2021.06.20 |
Comments