[TIL_알고리즘] 정렬 알고리즘 Selection Sort

최대값, 최소값은 인덱스의 위치를 이용해서 구하기

인덱스번호와 값을 함께 변경하기

 

최대값 구하기

max=data[0]

if max<data[i]:

  max=data[i]

 wheremax = i

 

정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식

 

[5,1,7,10,2] 에서 

1회전시 가장 작은 수를 찾음 인덱스 [1]인 1이 가장 작은 숫자 - > 인덱스[0]과 교환 [5,1,7,10,2]->[1,5,7,10,2]

2회전시 가장 작은 수를 찾음 인덱스 [4]인 2가 가장 작은 숫자 -> 인덱스[1]과 교환 [1,5,7,10,2]->[1,2,7,10,5]

3회전시 가장 작은 수를 찾음 인덱스 [4]인 5가 가장 작은 숫자 -> 인덱스 [2]와 교환 [1,2,7,10,5] ->[1,2,5,10,7]

4회전시 가장 작은 수를 찾음 인덱스[4]인 7과 가장 작은 숫자->인덱스 [3]과 교환 [1,2,5,10,7]->[1,2,5,7,10]

 

best case: O(n2)

worst case: O(n2)

평균적인 시간 복잡도: O(n2)

 

data=[3,2,5,4,1]

for pivot in range(len(data)-1):

  min = pivot #pivot은 방주인을 찾음

  for where in range(pivot+1,len(data)): #min이 가장 작은 수

    if data[where]<data[min]:

      min=where 

    data[pivot],data[min]=data[min],data[pivot] #교환

    print(data)

print(" ")   

print(data)

 

[2, 3, 5, 4, 1]

[3, 2, 5, 4, 1]

[2, 3, 5, 4, 1]

[1, 3, 5, 4, 2]

[1, 3, 5, 4, 2]

[1, 3, 5, 4, 2]

[1, 2, 5, 4, 3]

[1, 2, 4, 5, 3]

[1, 2, 3, 5, 4]

[1, 2, 3, 4, 5]

 

[1, 2, 3, 4, 5]