파이썬으로 정리하는 선택정렬

개념

• 가장 작은 값을 찾아 맨 왼쪽(앞) index로 위치 변경
  • 0번 index, 1번 index 반복
• 매번 가장 작은 데이터를 선택하여 정렬
• 각 위치에 어떤 값이 들어갈지 찾는 정렬
• 비교와 교환으로 이루어진 알고리즘

순서(오름차순 기준)

1. 주어진 데이터의 →(왼쪽에서 오른쪽) 방향으로 확인한다.
2. 임시로 0번 인덱스를 최소값으로 지정한다.
3. 한칸씩 오른쪽으로 이동하며 비교한다.
4. 길이의 끝까지 돌면서 임시로 지정한 값보다 값이 더 작으면 해당 데이터의 index를 최소 index로 변경한다.
5. 반복이 끝난 후 구해진 최소값 index를 가지고 임시로 지정한 변수와 swap 처리를 해준다.
6. 배열의 길이가 끝날때까지 반복한다.

특징

장점

• 알고리즘 코드가 간단해 레코드의 수가 적을때 사용
• 레코드가 거의 정렬되어 있을때 효율적

단점

• 많은 데이터의 이동 발생
• 데이터가 많고 크기가 클수록 효율성 떨어짐

예제 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def selection_sort(input_list):
    for i in range(len(input_list)):
    
    		# 임시 0번 index를 최소값
        min_index = i
        
        # 가장 작은 index 찾기
        for j in range(i + 1, len(input_list) - 1):
            if input_list[j] < input_list[min_index]:
                min_index = j
                
        temp = input_list[i]
        input_list[i] = input_list[min_index]
        input_list[min_index] = temp
        
    return input_list

시간복잡도

주어진 데이터의 원소 길이가 5일때 두수의 비교를 순차적으로 끝까지 하게 되면 총 4번의 횟수가 발생한다.

이때 끝까지 비교를 하면 4+3+2+1 = 10번이 발생한다. (n-1) + (n-2) ... + 1

하지만 교환은 최종적으로 index를 구한 후 딱 1번 발생하게 된다.

버블정렬과 비교했을때 최대 단계수가 약 2배정도 차이나지만 빅오표기법, 즉 시간복잡도를 이야기할 때

데이터의 계수와 상수는 무시하기 때문에 버블정렬과 시간복잡도는 동일하다고 볼 수 있다.

N의 값이 증가함에 따라 처리속도 및 공간의 증가율을 계산하는 것이기에 계수와 상수를 무시