[ 선택 정렬 ] 알고리즘

 

 

1.  개념

 

    선택 정렬 :   나열된 데이터에서 최솟값 혹은 최댓값을 찾아 루프 범위 가장 앞에 있는 데이터와 swap 하는 정렬

   

    * 시간 복잡도 : O(n²)

 

 

    선택 정렬 방법(오름차순 기준)

 

    1) 루프 범위에서 최솟값을 찾는다

    2) 루프 범위에서 가장 앞에 있는 데이터와 최솟값 데이터를 swap해준다 - 최솟값이 제자리를 찾음

    3) 제자리를 찾은 데이터를 제외하여 루프 범위를 재정비한다

    4) 반복

 

      

 

 

 

2.  문제 풀이

 

 # 1  내림차순으로 자릿수 정렬하기 - 백준 1427번

https://www.acmicpc.net/problem/1427

1427번: 소트인사이드

 

# 입력 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='')