728x90
반응형
📍 선택 정렬: 앞에서 부터 정렬하는, 일상적인 방법의 알고리즘
- 전체 값 중 가장 작은 값을 찾고, 해당 값을 맨 첫 번째에 배치함
- 첫 번째 값을 제외하고 가장 작은 값을 찾아 두 번째에 배치함
- 두 번째, 세 번째, ... , n-1 번째 값을 제외하고 가장 작은 값을 찾아 정해진 위치에 배치함
- 시간 복잡도: O(N^2)
- n-1, n-2, ..., 2, 1번의 비교 연산을 수행해야 하기 때문에, n(n-1)/2번의 연산 필요함
💬 python 코드
- n 개의 원소가 주어졌을 때, 선택 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬
n = int(input())
arr = list(map(int, input().split()))
for i in range(n-1):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]: # 더 작은 값이 있는지 탐색
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(*arr)
- 입력
6
5 2 6 1 3 8
- 출력
1 2 3 5 6 8
728x90
'자료구조 및 알고리즘 > 자료구조 및 알고리즘' 카테고리의 다른 글
정렬 - 4) 기수 정렬 (radix sort) (0) | 2024.04.08 |
---|---|
정렬 - 3) 삽입 정렬 (insertion sort) (0) | 2024.04.08 |
정렬 - 1) 버블 정렬 (bubble sort) (0) | 2024.04.08 |
Brute Force(완전 탐색) (0) | 2023.07.24 |
DFS와 BFS (0) | 2023.04.07 |