선택 정렬(selection sort)

📔 선택 정렬(selection sort) 이란

• 오름차순의 경우 가장 작은 원소를 맨 앞으로 보낸다.
• 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2)
• 한 세트가 끝날 때마다 가장 작은 수가 맨 앞에 온다.

 

📔 선택 정렬(selection sort) 예제

• 위의 예제는 오름차순일 경우의 예제이다.
• 5개의 원소중 가장 작은 숫자를 맨 앞의 숫자와 바꾼다.
• 1세트가 끝나면 가장 작은 수가 맨 앞으로 온다. 
• 다음 세트부터는 맨 앞의 숫자를 빼고 비교를 해준다. (이미 가장 작은 수이기 때문)

 

📔 선택 정렬(selection sort) 구현

numbers = [5, 3, 8, 1, 2]
print(f'정렬 전: {numbers}')
print()
for i in range(len(numbers)):
    print(f'{i + 1}세트')
    min_number = 99
    idx = 0
    for j in range(i, len(numbers)):
        if numbers[j] < min_number:
            min_number = numbers[j]
            idx = j
    else:
        numbers[i], numbers[idx] = numbers[idx], numbers[i]
    print(f'정렬 중: {numbers}')
print()
print(f'정렬 후: {numbers}')

 

📔 선택 정렬(selection sort) 특징

• 장점
  • 단순한 구현
• 단점
  • 정렬이 불필요한 요소에도 접근해야 한다.
  • 시간복잡도 O(n^2)
• 구현이 간단하지만 매우 비휼적이므로 거의 쓰이지 않음.

 

📔 선택 정렬(selection sort) 참교자료