정렬 - 2) 선택 정렬 (selection sort)

 

📍 선택 정렬: 앞에서 부터 정렬하는, 일상적인 방법의 알고리즘

• 전체 값 중 가장 작은 값을 찾고, 해당 값을 맨 첫 번째에 배치함
• 첫 번째 값을 제외하고 가장 작은 값을 찾아 두 번째에 배치함 
• 두 번째, 세 번째, ... , 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