자료구조 및 알고리즘/자료구조 및 알고리즘

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

viamemine 2024. 4. 8. 14:03
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