선택 정렬(Selection Sort)(파이썬)

 

 

 

선택 정렬(Selection Sort)

---

 

 

 

 

선택 정렬(Selection Sort)

주어진 데이터 중 최소값을 찾아서, 계속 맨앞으로 위치를 바꾸면서 순서를 바꾸는 방법

주어진 숫자 중 3이 가장 최소값이어서 자리를 바꾼다면 6과 자리를 바꾸게 된다. 이런식으로 하나하나 계속 비교하면서 자리를 찾아가는 방법이다.

 

1. 주어진 데이터 중, 최소값을 찾는다.

2. 최소값을 맨 앞으로 이동한다.

3. 맨 앞 데이터를 제외한 나머지 데이터들에게 동일한 반복을 시행한다. 

 

 

주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘

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

for i in range(len(nums)-1):
   minIdx = i

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

   tempNum = nums[i]
   nums[i] = nums[minIdx]
   nums[minIdx] = tempNum

print(f'nums: {nums}')

nums: [1, 2, 3, 4, 5]

 

 

 

선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자. 시험 점수는 50부터 100까지로 한다.

import random
import sortMod as sm
import copy

scores = random.sample(range(50, 101), 20)
print(f'scores: {scores}')
print(f'scores length: {len(scores)}')

result = sm.sortNumber(copy.deepcopy(scores))
print(f'result(ASC): {result}')

result = sm.sortNumber(copy.deepcopy(scores), asc=False)
print(f'result(DESC): {result}')

def sortNumber(ns, asc=True):

    cnt = 0

    for i in range(len(ns) - 1):
        targetIdx = i

        for j in range(i + 1, len(ns)):
            if asc:
                if ns[targetIdx] > ns[j]:
                    targetIdx = j
                    cnt += 1
            else:
                if ns[targetIdx] < ns[j]:
                    targetIdx = j
                    cnt += 1

        ns[i], ns[targetIdx] = ns[targetIdx], ns[i]

    return ns

scores: [70, 57, 96, 83, 68, 91, 98, 76, 56, 74, 69, 84, 53, 86, 59, 79, 94, 73, 67, 87]
scores length: 20
result(ASC): [53, 56, 57, 59, 67, 68, 69, 70, 73, 74, 76, 79, 83, 84, 86, 87, 91, 94, 96, 98]
result(DESC): [98, 96, 94, 91, 87, 86, 84, 83, 79, 76, 74, 73, 70, 69, 68, 67, 59, 57, 56, 53]