처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
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]
# nums[j] = nums[j + 1]
# nums[j + 1] = temp
nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(f'sorted nums : {nums}')
not sorted nums : [10, 2, 7, 21, 0]
sorted nums : [0, 2, 7, 10, 21]
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]
# nums[j] = nums[j + 1]
# nums[j + 1] = temp
nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(f'sorted nums : {nums}')
not sorted nums : [10, 2, 7, 21, 0]
sorted nums : [0, 2, 7, 10, 21]
정렬되어 있는 자료배열과 비교해서, 정렬 위치를 찾는다
# 삽입 정렬
nums = [5, 10, 2, 1, 0, 7, 8]
# ASCENDING
for i1 in range(1, len(nums)):
i2 = i1 - 1
cNum = nums[i1]
print(f'ASC {i1} nums : {nums}')
while nums[i2] > cNum and i2 >= 0:
nums[i2 + 1] = nums[i2]
i2 -= 1
nums[i2 + 1] = cNum
# print(f'nums : {nums}')
# 삽입 정렬
# DESCENDING
nums = [5, 10, 2, 1, 0, 7, 8]
length = len(nums)
for i1 in range(1, length):
i2 = i1 - 1
num = nums[i1]
print(f'DES {i1} nums : {nums}')
while i2 >= 0 and nums[i2] < num:
nums[i2 + 1] = nums[i2]
i2 -= 1
nums[i2 + 1] = num
ASC 1 nums : [5, 10, 2, 1, 0, 7, 8]
ASC 2 nums : [5, 10, 2, 1, 0, 7, 8]
ASC 3 nums : [2, 5, 10, 1, 0, 7, 8]
ASC 4 nums : [1, 2, 5, 10, 0, 7, 8]
ASC 5 nums : [0, 1, 2, 5, 10, 7, 8]
ASC 6 nums : [0, 1, 2, 5, 7, 10, 8]
DES 1 nums : [5, 10, 2, 1, 0, 7, 8]
DES 2 nums : [10, 5, 2, 1, 0, 7, 8]
DES 3 nums : [10, 5, 2, 1, 0, 7, 8]
DES 4 nums : [10, 5, 2, 1, 0, 7, 8]
DES 5 nums : [10, 5, 2, 1, 0, 7, 8]
DES 6 nums : [10, 7, 5, 2, 1, 0, 8]
- 생성된 난수들은 오름차순 또는 내림차순으로 정렬하는 알고리즘 구현
- 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현
#class SortNumbers
class SortNumbers:
def __init__(self, nums, asc=True, isCopy=True):
if isCopy:
self.nums = copy.copy(nums)
else:
self.nums = nums
self.isAsc = asc
def isAscending(self, flag):
self.isAsc = flag
# 삽입 졍렬 사용
def setSort(self):
length = len(self.nums)
for i1 in range(1, length):
i2 = i1 - 1
value = self.nums[i1]
# Ascending
if self.isAsc:
while i2 >= 0 and value < self.nums[i2]:
self.nums[i2 + 1] = self.nums[i2]
i2 -= 1
self.nums[i2 + 1] = value
# Descending
else:
while i2 >= 0 and value > self.nums[i2]:
self.nums[i2 + 1] = self.nums[i2]
i2 -= 1
self.nums[i2 + 1] = value
def getSortNumber(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 not self.isAsc:
return self.nums[0]
else:
return self.nums[len(self.nums) - 1]
# 1부터 1000까지의 난수 100개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자
# 1. 생성된 난수들은 오름차순 또는 내림차순으로 정렬하는 알고리즘 구현
# 2. 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현
import random
from module import sortMod
nums = random.sample(range(1, 1001), 100)
sortNum = sortMod.SortNumbers(nums)
print(f'정렬 전 \t\t : {nums}')
sortNum.setSort()
print(f'정렬 후 \t\t : {sortNum.getSortNumber()}')
print(f'가장 큰 수 \t : {sortNum.getMaxNumber()}')
print(f'가장 작은 수 \t : {sortNum.getMinNumber()}')
print(f'원본 \t\t : {nums}')
정렬 전 : [744, 360, 610, 528, 586, 193, 350, 976, 706, 966, 845, 618, 915, 333, 993, 775, 644, 221, 964, 973, 857, 420, 944, 189, 653, 224, 743, 271, 756, 12, 93, 43, 986, 284, 541, 689, 599, 642, 361, 711, 52, 593, 537, 45, 236, 903, 843, 524, 72, 159, 370, 55, 935, 504, 764, 375, 635, 409, 321, 708, 844, 829, 446, 842, 244, 503, 754, 100, 848, 395, 228, 548, 103, 33, 112, 194, 981, 606, 154, 822, 8, 423, 274, 95, 611, 555, 270, 921, 336, 959, 647, 725, 117, 253, 17, 184, 726, 913, 471, 691]
정렬 후 : [8, 12, 17, 33, 43, 45, 52, 55, 72, 93, 95, 100, 103, 112, 117, 154, 159, 184, 189, 193, 194, 221, 224, 228, 236, 244, 253, 270, 271, 274, 284, 321, 333, 336, 350, 360, 361, 370, 375, 395, 409, 420, 423, 446, 471, 503, 504, 524, 528, 537, 541, 548, 555, 586, 593, 599, 606, 610, 611, 618, 635, 642, 644, 647, 653, 689, 691, 706, 708, 711, 725, 726, 743, 744, 754, 756, 764, 775, 822, 829, 842, 843, 844, 845, 848, 857, 903, 913, 915, 921, 935, 944, 959, 964, 966, 973, 976, 981, 986, 993]
가장 큰 수 : 993
가장 작은 수 : 8
원본 : [744, 360, 610, 528, 586, 193, 350, 976, 706, 966, 845, 618, 915, 333, 993, 775, 644, 221, 964, 973, 857, 420, 944, 189, 653, 224, 743, 271, 756, 12, 93, 43, 986, 284, 541, 689, 599, 642, 361, 711, 52, 593, 537, 45, 236, 903, 843, 524, 72, 159, 370, 55, 935, 504, 764, 375, 635, 409, 321, 708, 844, 829, 446, 842, 244, 503, 754, 100, 848, 395, 228, 548, 103, 33, 112, 194, 981, 606, 154, 822, 8, 423, 274, 95, 611, 555, 270, 921, 336, 959, 647, 725, 117, 253, 17, 184, 726, 913, 471, 691]
주어진 리스트 중에 최솟값을 찾아, 그 값을 맨앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘
nums = [4, 2, 5, 1, 3]
print(nums)
for i in range(len(nums) - 1):
temp1 = i
for j in range(i + 1, len(nums)):
if nums[temp1] > nums[j]:
temp1 = j
nums[i], nums[temp1] = nums[temp1], nums[i]
print(nums)
[4, 2, 5, 1, 3]
[1, 2, 5, 4, 3]
[1, 2, 5, 4, 3]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
# class SelectSort
class SelectSort:
def __init__(self, scores, isAsc=True):
self.scores = scores
self.isAsc = isAsc
def setSortScore(self):
for i in range(len(self.scores) - 1):
idx = i
for j in range(i + 1, len(self.scores)):
if self.isAsc:
if self.scores[idx] > self.scores[j]:
idx = j
else:
if self.scores[idx] < self.scores[j]:
idx = j
self.scores[i], self.scores[idx] = self.scores[idx], self.scores[i]
def getSortScore(self):
return self.scores
def setIsAsc(self, isAsc):
self.isAsc = isAsc
def printScore(self):
if self.isAsc:
print(f'[ASC] sorted scores \t: {self.scores}')
else:
print(f'[DES] sorted scores \t: {self.scores}')
import random
from module import sortMod
scores = random.sample(range(50, 101), 20)
print(f'not sorted scores \t\t: {scores} ')
sort = sortMod.SelectSort(scores)
sort.setSortScore()
sort.printScore()
not sorted scores : [73, 99, 87, 77, 86, 59, 70, 52, 63, 80, 78, 90, 50, 92, 62, 69, 54, 81, 51, 61]
[ASC] sorted scores : [50, 51, 52, 54, 59, 61, 62, 63, 69, 70, 73, 77, 78, 80, 81, 86, 87, 90, 92, 99]
not sorted scores : [60, 96, 83, 52, 86, 75, 51, 70, 50, 97, 84, 82, 85, 95, 67, 77, 92, 81, 62, 54]
[DES] sorted scores : [97, 96, 95, 92, 86, 85, 84, 83, 82, 81, 77, 75, 70, 67, 62, 60, 54, 52, 51, 50]
자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬
# 병합정렬
def mergeSort(nums):
if len(nums) < 2:
return nums
miIdx = len(nums) // 2
leftNums = mergeSort(nums[:miIdx])
rightNums = mergeSort(nums[miIdx:])
mergeNums = []
leftIdx = 0
rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
if leftNums[leftIdx] < rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
mergeNums += leftNums[leftIdx:]
mergeNums += rightNums[rightIdx:]
print(mergeNums)
return mergeNums
nums = [7, 3, 2, 16, 24, 4, 11, 9]
mergeSort(nums)
[3, 7]
[2, 16]
[2, 3, 7, 16]
[4, 24]
[9, 11]
[4, 9, 11, 24]
[2, 3, 4, 7, 9, 11, 16, 24]
- 병합정렬 알고리즘을 이용한 난수 모듈 구현
- 위의 모듈에 오름차순과 내림차순 선택할 수 있는 옵션 추가
# 병합 모듈
def setMergeSort(nums, isAsc=True):
if len(nums) < 2:
return nums
# 분할 단계
midIdx = len(nums) // 2
leftNums = setMergeSort(nums[:midIdx], isAsc)
rightNums = setMergeSort(nums[midIdx:], isAsc)
# 병합 단계
mergeNums = []
leftIdx = 0
rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
if isAsc:
if leftNums[leftIdx] < rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
else:
if leftNums[leftIdx] > rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
mergeNums += leftNums[leftIdx:]
mergeNums += rightNums[rightIdx:]
if isAsc:
print(f'ASC mergeNums \t: {mergeNums}')
else:
print(f'DES mergeNums \t: {mergeNums}')
return mergeNums
# 1부터 100까지의 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자
# 1. 병합정렬 알고리즘을 이용한 난수 모듈 구현
# 2. 위의 모듈에 오름차순과 내림차순 선택할 수 있는 옵션 추가
import copy
import random
from module import mergeMod
randoms = random.sample(range(1, 101), 10)
ascNums = copy.deepcopy(randoms)
desNums = copy.deepcopy(randoms)
print(f'not sored \t\t: {randoms}')
print('-'*60)
mergeMod.setMergeSort(ascNums, True)
print('-'*60)
mergeMod.setMergeSort(desNums, False)
not sored : [61, 4, 80, 30, 67, 18, 40, 56, 43, 57]
------------------------------------------------------------
ASC mergeNums : [4, 61]
ASC mergeNums : [30, 67]
ASC mergeNums : [30, 67, 80]
ASC mergeNums : [4, 30, 61, 67, 80]
ASC mergeNums : [18, 40]
ASC mergeNums : [43, 57]
ASC mergeNums : [43, 56, 57]
ASC mergeNums : [18, 40, 43, 56, 57]
ASC mergeNums : [4, 18, 30, 40, 43, 56, 57, 61, 67, 80]
------------------------------------------------------------
DES mergeNums : [61, 4]
DES mergeNums : [67, 30]
DES mergeNums : [80, 67, 30]
DES mergeNums : [80, 67, 61, 30, 4]
DES mergeNums : [40, 18]
DES mergeNums : [57, 43]
DES mergeNums : [57, 56, 43]
DES mergeNums : [57, 56, 43, 40, 18]
DES mergeNums : [80, 67, 61, 57, 56, 43, 40, 30, 18, 4]
기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
# 퀵 정렬
def qSort(nums):
if len(nums) < 2:
return nums
pivotIdx = len(nums) // 2
pivotValue = nums[pivotIdx]
smallNums, sameNums, bigNums = [], [], []
for n in nums:
if n < pivotValue:
smallNums.append(n)
elif n == pivotValue:
sameNums.append(n)
else:
bigNums.append(n)
print('-' * 40)
print(f'nums\t: {nums}')
if len(smallNums) > 0 or len(bigNums) > 0:
print('-' * 40)
print(f'small\t: {smallNums}\npivot\t: {sameNums}\nbig\t\t: {bigNums}')
return qSort(smallNums) + sameNums + qSort(bigNums)
nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(f'{qSort(nums)}')
nums : [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
----------------------------------------
small : [1, 4, 3, 2, 4]
pivot : [5]
big : [8, 10, 6, 8]
----------------------------------------
nums : [1, 4, 3, 2, 4]
----------------------------------------
small : [1, 2]
pivot : [3]
big : [4, 4]
----------------------------------------
nums : [1, 2]
----------------------------------------
small : [1]
pivot : [2]
big : []
----------------------------------------
nums : [4, 4]
----------------------------------------
nums : [8, 10, 6, 8]
----------------------------------------
small : []
pivot : [6]
big : [8, 10, 8]
----------------------------------------
nums : [8, 10, 8]
----------------------------------------
small : [8, 8]
pivot : [10]
big : []
----------------------------------------
nums : [8, 8]
[1, 2, 3, 4, 4, 5, 6, 8, 8, 10]
- 퀵 정렬 알고리즘을 이용한 난수 모듈 구현
- 위의 모듈에 오름차순과 내림차순 선택할 수 있는 옵션 추가
# 퀵 정렬
def setQuickSort(nums, isAsc=True):
if len(nums) < 2:
return nums
smallList, sameList, bigList = [], [], []
pivotIdx = len(nums) // 2
pivotVal = nums[pivotIdx]
for n in nums:
if n > pivotVal:
bigList.append(n)
elif n == pivotVal:
sameList.append(n)
else:
smallList.append(n)
if isAsc:
return setQuickSort(smallList, isAsc) + sameList + setQuickSort(bigList, isAsc)
else:
return setQuickSort(bigList, isAsc) + sameList + setQuickSort(smallList, isAsc)
# 1부터 100까지의 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자
# 1. 병합정렬 알고리즘을 이용한 난수 모듈 구현
# 2. 위의 모듈에 오름차순과 내림차순 선택할 수 있는 옵션 추가
import copy
import random
from module import mergeMod
randoms = random.sample(range(1, 101), 10)
ascNums = copy.deepcopy(randoms)
desNums = copy.deepcopy(randoms)
print(f'not sored \t\t: {randoms}')
print('-'*60)
mergeMod.setMergeSort(ascNums, True)
print('-'*60)
mergeMod.setMergeSort(desNums, False)
randoms : [66, 91, 89, 99, 22, 37, 93, 8, 51, 6]
ASC : [6, 8, 22, 37, 51, 66, 89, 91, 93, 99]
DES : [99, 93, 91, 89, 66, 51, 37, 22, 8, 6]