선택 정렬 (Selection Sort)

선택 정렬 알고리즘의 기본 개념

• 데이터 중 가장 최솟값을 찾아서 앞으로 보내는 알고리즘
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
  • 첫 번째 순서에는 첫 번째 위치에 최솟값을 넣는다.
  • 두 번째 순서에는 두 번째 위치에 남은 원소중 최솟값을 넣는다.
  • 정렬이 끝날 때까지 반복
• 알고리즘의 과정
  • 주어진 배열 중에서 최솟값을 찾는다.
  • 그 값을 맨 앞에 위치한 값과 교체한다.
  • 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
  • 하나의 원소만 남을 때 까지 계속 반복.

파이썬으로 코드 구현

 

코드 구현

def selectionsort(list):
    for i in range(len(list)):
        min_index = i  # 배열의 최솟값과 첫 번째 자리를 바꿔주기 위해 미리 첫 번째 위치 고정

        for j in range(i+1, len(list)):   # 첫 번째 자리의 다음 자리부터 끝까지 탐색
            if list[min_index] > list[j]: # 배열을 돌며 최솟값을 찾는다
                min_index = j
    
        list[i], list[min_index] = list[min_index], list[i] # 처음 고정해둔 앞자리와 최솟값의 자리를 교체 후 다음 회차 진행

 

알고리즘 테스트

test = [2, 1, 9, 5, 3, 6, 1, 8, 4, 7]
selectionsort(test)
print(test)

 

결과

[1, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

알고리즘 테스트 2

 

아래의 네가지 데이터를 넣고 테스트도 진행해 보았다.

1. 정렬이 끝난 배열
2. 역순으로 정렬된 배열
3. 원소가 전부 같은 배열
4. 랜덤으로 구성된 배열

import time

def selectionsort(list):
    for i in range(len(list)):
        min_index = i

        for j in range(i+1, len(list)):
            if list[min_index] > list[j]:
                min_index = j
    
        list[i], list[min_index] = list[min_index], list[i]

test1 = [1, 2, 3, 4, 5, 6, 7]
test2 = [7, 6, 5, 4, 3, 2, 1]
test3 = [1, 1, 1, 1, 1, 1, 1, 1]
test4 = [23, 15, 38, 94, 62, 123, 243, 234, 112]

start_time1 = time.time()
selectionsort(test1)
end_time1 = time.time()
total_time1 = (end_time1 - start_time1) * 1000

start_time2 = time.time()
selectionsort(test2)
end_time2 = time.time()
total_time2 = (end_time2 - start_time2) * 1000

start_time3 = time.time()
selectionsort(test3)
end_time3 = time.time()
total_time3 = (end_time3 - start_time3) * 1000

start_time4 = time.time()
selectionsort(test4)
end_time4 = time.time()
total_time4 = (end_time4 - start_time4) * 1000

print(f'{total_time1:.4f}ms')
print(f'{total_time2:.4f}ms')
print(f'{total_time3:.4f}ms')
print(f'{total_time4:.4f}ms')

 

결과

0.0644ms
0.1113ms
0.0377ms
0.0963ms

 

random 데이터로 성능 테스트

import random
import time

def selectionsort(list):
    for i in range(len(list)):
        min_index = i

        for j in range(i+1, len(list)):
            if list[min_index] > list[j]:
                min_index = j
    
        list[i], list[min_index] = list[min_index], list[i]

data = [random.randint(1, 1000000) for _ in range(1000)]
start_time = time.time()
selectionsort(data)
print(data)
end_time = time.time()
total_time = end_time - start_time
print(f'{total_time:.4f}초')

• 데이터가 1000개 일 때 : 0.0240초
• 데이터가 2000개 일 때 : 0.1096초
• 데이터가 4000개 일 때 : 0.3155초
• 데이터가 5000개 일 때 : 0.5005초
• 데이터가 10000개 일 때 : 1.9639초