[버블 정렬]
- 버블 정렬: 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘.
nums = [10, 2, 7, 21, 0]
print(f'not sorted nums: {nums}')
length = len(nums) - 1
for i in range(length):
for j in range(length-i): # 처음 비교가 끝나면, 그 다음에는 앞자리까지만 비교하면 되기 때문.
if nums[j] > nums[j+1]:
# temp = nums[j] # 자리 바꾸기 방법 예시 1
# nums[j] = nums[j+1]
# nums[j+1] = temp
nums[j], nums[j+1] = nums[j+1], nums[j] # 자리 바꾸기 방법 예시 2
print(nums)
print()
print(f'sorted nums: {nums}')- 버블 정렬 실습)
-> 새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워 보자. (학생들의 키는 170~185 사이의 랜덤)
-> 모듈: sortMod
모듈: sortMod
import copy
def bubbleSort(ns, deepCopy = True): # ns 라는 자료구조를 받는다.
if deepCopy: # 깊은 복사
cns = copy.copy(ns)
else: # 얕은 복사
cns = ns
length = len(cns) - 1
for i in range(length):
for j in range(length - i):
if cns[j] > cns[j+1]:
cns[j], cns[j+1] = cns[j+1], cns[j]
return cns실행파일)
import random as rd
import sortMod as sm
students = []
for i in range(20):
students.append(rd.randint(170, 185))
print(f'students: {students}')
sortedStudents = sm.bubbleSort(students) # 지금은 깊은 복사가 되어 있는 상태, 이게 싫으면 sm.bubbleSort(stdudents, deepCopy = False)
print(f'students: {students}')
print(f'sortedStudetns: {sortedStudents}')[삽입정렬]
- 삽입정렬: 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다. (insert 알고리즘 정렬)
# 오름차순
nums = [5, 10, 2, 1, 0]
for i1 in range(1,len(nums)): # index1부터 시작해서 앞에 있는 숫자들과 비교
i2 = i1 -1
cNum = nums[i1]
while nums[i2] > cNum and i2 >= 0:
nums[i2 + 1] = nums[i2]
i2 -= 1
nums[i2 + 1] = cNum
print(f'nums: {nums}')
# 내림차순
nums = [0, 5, 2, 1, 10]
for i1 in range(1,len(nums)):
i2 = i1 -1
cNum = nums[i1]
while nums[i2] < cNum and i2 >= 0:
nums[i2 + 1] = nums[i2]
i2 -= 1
nums[i2 + 1] = cNum
print(f'nums: {nums}')- 삽입정렬 실습)
모듈: sortMod
class SortNumbers:
def __init__(self, ns, asc=True): # 오름차순이 기본적으로 True
self.nums = ns
self.isAsc = asc
def isAscending(self, flag):
self.isAsc = flag
def setSort(self):
for i1 in range(1,len(self.nums)):
i2 = i1 - 1
cNum = self.nums[i1]
if self.isAsc:
while self.nums[i2] > cNum and i2 >= 0:
self.nums[i2+1] = self.nums[i2]
i2 -= 1
else:
while self.nums[i2] < cNum and i2 >= 0:
self.nums[i2+1] = self.nums[i2]
i2 -= 1
self.nums[i2 + 1] = cNum
def getSortedNumbers(self):
return self.nums
def getMinNumber(self):
if self.isAsc:
return self.nums[0]
else:
return self.nums[len(self.nums)-1]
def getMaxNumber(self):
if self.isAsc:
return self.nums[len(self.nums) - 1]
else:
return self.nums[0]실행파일)
import random
import sortMod as sm
nums = random.sample(range(1,1000), 100)
print(f'not sorted numbers: {nums}')
sn = sm.SortNumbers(nums)
# 오름차순(ascending)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by ASC: {sortedNumbers}')
# 내림차순(descending)
sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers by DSC: {sortedNumbers}')
# min & max
print(f'min: {sn.getMinNumber()}')
print(f'max: {sn.getMaxNumber()}')[선택정렬]
- 선택정렬: 주어진 리스트 중에 최솟값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬.
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}')
- 선택정렬 실습)
-> 선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자. (시험 점수는 50~100점)
모듈: sortMod
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 random
import sortMod as sm
scores = random.sample(range(50,101),20)
# 오름차순
print(f'scores: {scores}')
result = sm.sortNumber(scores)
print(f'result: {result}')
# 내림차순
print(f'scores: {scores}') # scores가 얕은 복사 되었기 때문에, 원본이 아니라 이미 오름차순 정렬이 되어있는 리스트로 출력됨.
result = sm.sortNumber(scores, asc=False)
print(f'result: {result}')
# ----------------------------------------------------------------------
# 깊은 복사 하는 방법
import random
import sortMod as sm
import copy
scores = random.sample(range(50,101),20)
# 오름차순
print(f'scores: {scores}')
result = sm.sortNumber(copy.deepcopy(scores)) # copy.deepcopy()를 통해 복사본을 만들어 모듈에 전달
print(f'result: {result}')
# 내림차순
print(f'scores: {scores}')
result = sm.sortNumber(copy.deepcopy(scores), asc=False)
print(f'result: {result}')[최댓값]
- 최댓값: 자료구조에서 가장 큰 값을 찾는다.
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}')
- 최댓값 실습)
-> 리스트에서 아스키 코드가 가장 큰 값을 찾는 알고리즘을 만들어보자.
-> ord(): 문자열을 아스키 코드로 변환해주는 함수
class MaxAlgorithm:
def __init__(self, cs):
self.chars = cs
self.maxChar = 0
def getMaxChar(self):
self.maxChar = self.chars[0]
for i in self.chars:
if ord(self.maxChar) < ord(i):
self.maxChar = i
return self.maxChar
chars= ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
mc = MaxAlgorithm(chars)
maxChar = mc.getMaxChar()
print(f'maxChar: {maxChar}')
늘 온 마음을 다해 :)