수업시간에 들은 selection sort를 파이썬으로 구현해보았다. 쉬운 문제인데 엄청 헤맸다..
def selectionSort(arr):
findMin = [0]
for i in range(len(arr)):
findMin[0] = arr[i]
print('target idx : ', i, 'arr1[i] : ', arr[i])
for j in range(i+1,len(arr)):
if findMin[0] > arr1[j]:
findMin[0] = arr1[j]
print('check this : ', arr[j],'find another Min :',findMin)
arr[arr.index(findMin[0])] = arr[i]
arr[i] = findMin[0]
print(arr)
return arr
arr1 = [9,1,12,6,8,4,3,2,0,7,11,13,15]
print(selectionSort(arr1))
- 찾은 최소값을 저장할 findMin을 정의함
- array의 첫번째 원소를 일단 findMin에 넣고,
- array의 두번째 원소부터 끝까지 findMin을 비교검사함.
- 만약에 비교하는 도중 더 작은 값을 찾으면 findMin의 값은 바뀜
- 검사가 모두 마치면 최소 값이 있던 자리에는 첫 번째 원소가 들어가고 findMin에 있던 최소 값은 첫 번째 원소 자리로 들어가게 되어 교체가 일어난다.
- 이 과정을 array의 크기만큼 반복한다.
찾아본 위키백과 내용은 다음과 같다
Selection sort는 다음과 같은 알고리즘으로 작동한다.
- 주어진 리스트 중 최솟값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
시간복잡도는 θ(n2)
def selectionSort(x):
length = len(x)
for i in range(length-1):
indexMin = i
for j in range(i+1, length):
if x[indexMin] > x[j]:
indexMin = j
x[i], x[indexMin] = x[indexMin], x[i]
return x
값의 위치를 바꾸고 싶을 땐 튜플을 이용하자
Comments