개발/👾 PS
[ 선택 정렬 ] 알고리즘
정소은
2023. 3. 18. 16:18
1. 개념
선택 정렬 : 나열된 데이터에서 최솟값 혹은 최댓값을 찾아 루프 범위 가장 앞에 있는 데이터와 swap 하는 정렬
* 시간 복잡도 : O(n²)
선택 정렬 방법(오름차순 기준)
1) 루프 범위에서 최솟값을 찾는다
2) 루프 범위에서 가장 앞에 있는 데이터와 최솟값 데이터를 swap해준다 - 최솟값이 제자리를 찾음
3) 제자리를 찾은 데이터를 제외하여 루프 범위를 재정비한다
4) 반복
2. 문제 풀이
# 1 내림차순으로 자릿수 정렬하기 - 백준 1427번
https://www.acmicpc.net/problem/1427
1427번: 소트인사이드
첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
# 입력 string으로 받아서 숫자 한개씩 리스트에 넣기
n = list(input())
big = 0
bigIndex = 0
# 리스트 요소들 int로 바꿔주기
for i in range(len(n)):
n[i] = int(n[i])
for i in range(len(n)):
for j in range(i,len(n)): # 루프 범위 재정비 -> 내림차순이므로 정렬 끝난 숫자는 맨 앞으로 감
if n[j] >= big: # 범위 내에서 최댓값 구하기
big = n[j]
bigIndex = j
n[bigIndex],n[i] = n[i],n[bigIndex] # 최댓값과 맨 앞 데이터 위치 바꾸기
bigIndex = 0
big = 0
for i in n:
print(i,end='')