[알고리즘] 선택 정렬

* <모두의 알고리즘 with 파이썬>의 문제 08를 정리한 내용입니다.

 

1. 선택 정렬이란?

• 정렬 알고리즘 중 가장 직관적인 알고리즘이라고 한다. 초딩 때 운동장에서 키 순서대로 줄을 설 때를 생각해보자. 
  • 160cm, 150cm, 170cm, 180cm 가 있다고 했을 때, 우선 여기서 가장 키가 작은 150cm를 가장 앞에 세운다. 
  • 그리고 남은 세 명의 키를 비교하여 가장 키가 작은 160cm를 150cm 뒤에 세운다. 
  • 그리고 남은 두 명의 키를 비교하여 가장 키가 작은 170cm를 160cm 뒤에 세운다. 
  • 남은 180은 자동적으로 가장 뒤에 서게 된다. 
• 위에서 설명한 정렬 방식을 일반하면 다음과 같다. 
  • 0 인덱스 부터 하나씩 보면서 제일 작은 값을 찾고 0번 인덱스와 교체한다.
  • 그 후 1인덱스 부터 하나씩 보면서 작은 값 찾고 1번 인덱스와 교체한다.
  • 전체 길이 - 1의 숫자까지 정렬하면 종료한다. 

def select_sort_asc(a):
    n = len(a)
    for i in range(0, n-1):
        min_idx = i
        for j in range(i+1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]
    return a

 

 

2. 문제 풀이 

• 프로그램 8-1과 8-2의 정렬 알고리즘은 숫자를 작은 수에서 큰 수 순서로 나열하는 오름차순 정렬이었습니다. 이 알고리즘을 내림차순 정렬로 바꾸려면 어느 부분을 바꿔야 할까요? 

def select_sort_desc(a):
    n = len(a)
    for i in range(0, n-1):
        max_idx = i
        for j in range(i+1, n):
            print(j, a)
            if a[j] > a[max_idx]:
                max_idx = j
        a[i], a[max_idx] = a[max_idx], a[i]
    return a

• 파이썬에서 두 자료 값을 서로 바꾸기 위해 다음 문장을 사용한다. 
  • a[i], a[max_idx] = a[max_idx], a[i]