선택정렬
선택정렬이란?
주어진 리스트 중에서 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘이다.
nums = [4, 2, 5, 1, 3]
print(f'nums: {nums}')
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
nums[i], nums[minIdx] = nums[minIdx], nums[i] # 위에 자리바꿈 간단하게 쓴 것
print(f'nums: {nums}')
print(f'final nums: {nums}')# 결괏값:
nums: [4, 2, 5, 1, 3]
nums: [1, 2, 5, 4, 3]
nums: [1, 2, 5, 4, 3]
nums: [1, 2, 3, 4, 5]
nums: [1, 2, 3, 4, 5]
final nums: [1, 2, 3, 4, 5]선택정렬(실습)
실습
선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자. 시험 점수는 50부터 100까지로 한다.
- 모듈
def sortNumber(ns, asc=True):
if asc: # 오름차순 정렬일 때
for i in range(len(ns) - 1):
minIdx = i
for j in range(i+1, len(ns)):
if ns[minIdx] > ns[j]:
minIdx = j
ns[i], ns[minIdx] = ns[minIdx], ns[i]
else: # 내림차순 정렬일 때
for i in range(len(ns) - 1):
minIdx = i
for j in range(i + 1, len(ns)):
if ns[minIdx] < ns[j]:
minIdx = j
ns[i], ns[minIdx] = ns[minIdx], ns[i]
return ns
- 실행파일
import copy
import random
import sortMod as sm
scores = random.sample(range(50, 101),20)
# 오름차순 정렬일 때
print(f'scores: {scores}') # 정렬되기 전
result = sm.sortNumber(copy.deepcopy(scores)) # 원본이 훼손되지 않고 완벽한 복사본으로 전달됨
print(f'result: {result}') # 정렬된 후
# 내림차순 정렬일 때
print(f'scores: {scores}') # 정렬되기 전
result = sm.sortNumber(copy.deepcopy(scores), asc=False) # 원본이 훼손되지 않고 완벽한 복사본으로 전달됨
print(f'result: {result}') # 정렬된 후# 결괏값:
scores: [92, 58, 72, 73, 76, 61, 80, 57, 99, 93, 83, 90, 68, 98, 81, 51, 95, 87, 69, 96]
result: [51, 57, 58, 61, 68, 69, 72, 73, 76, 80, 81, 83, 87, 90, 92, 93, 95, 96, 98, 99]
scores: [92, 58, 72, 73, 76, 61, 80, 57, 99, 93, 83, 90, 68, 98, 81, 51, 95, 87, 69, 96]
result: [99, 98, 96, 95, 93, 92, 90, 87, 83, 81, 80, 76, 73, 72, 69, 68, 61, 58, 57, 51]최댓값
최댓값
자료구조에서 가장 큰 값을 찾는다.
class MaxAlgorithm:
def __init__(self, ns):
self.nums = ns
self.maxNum = 0
def getMaxNum(self):
self.maxNum = self.nums[0]
for n in self.nums:
if self.maxNum < n:
self.maxNum = n
return self.maxNum
ma = MaxAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])
maxNum = ma.getMaxNum()
print(f'maxNum: {maxNum}')# 결괏값:
maxNum: 20최댓값(실습)
실습
리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘을 만들어보자.
class MaxAlgorithm:
def __init__(self, cs):
self.chars = cs
self.maxChar = 0
def getMaxChar(self):
self.maxChar = self.chars[0]
for c in self.chars:
if ord(self.maxChar) < ord(c):
self.maxChar = c
return self.maxChar
chars = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
mc = MaxAlgorithm(chars)
maxChar = mc.getMaxChar()
print(f'maxChar: {maxChar}')# 결괏값:
maxChar: x