정렬 알고리즘은 순서가 없던 데이터를 순서대로 바꾸어 나열하는 알고리즘이다.
정렬을 하는 방법 중, 선택정렬 (Selection sort) 에 대한 문제이다.
선택정렬이란?
선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
1) 주어진 리스트 중에 최소값을 찾는다.
2) 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
def selectionSort(nums):
for j in range(len(nums)):
smallest_index = j
for i in range(j,len(nums)):
if nums[i] < nums[smallest_index]:
smallest_index = i
nums[j], nums[smallest_index] = nums[smallest_index], nums[j]
return nums
a = [2, 5, 6, 8, 10, 1, 3, 4, 7]
print(selectionSort(a)) 결과 : [1, 2, 3, 4, 5, 6, 7, 8, 10]
내가 푼 방식:
for 문을 2 번 돌린다.
외부 for문: 맨 앞에 제일 작은 수가 오고 나서, 다음 루프 때 그 다음 인덱스의 값부터 비교할 수 있게 해준다.
내부 for문: 수를 비교하여 값을 변경해준다.
