1. 순위
순위
수의 크고 작음을 이용해서 수의 순서를 정하는 것을 순위라고 한다.
실습
학급 학생(20명)들의 중간고사와 기말고사 성적을 이용해서 각각의순위를 구하고, 중간고사 대비 기말고사 순위 변화(편차)를 출력하는 프로그램을 만들어 보자.(시험 성적은 난수를 이용한다.)
import random
midStuScos=[]
endStuScos=[]
for i in range(20):
score_ran1 = random.randint(1,100)
score_ran2 = random.randint(1,100)
midStuScos.append(score_ran1)
endStuScos.append(score_ran2)
ranks_mid = [0 for i in range(20)]
for idx, num1 in enumerate(midStuScos):
for num2 in (midStuScos):
if num1 < num2:
ranks_mid[idx] += 1
ranks_end = [0 for i in range(20)]
for idx, num1 in enumerate(endStuScos):
for num2 in (endStuScos):
if num1 < num2:
ranks_end[idx] += 1
devi = [0 for i in range(20)]
for i in range (20):
devi[i] = ranks_mid[i] - ranks_end[i]
def arrow(num):
if num > 0 :
return f'⬆️{num}'
if num < 0 :
return f'⬇️{num}'
if num == 0 :
return f'=0'
for i in range (20):
print(f'mid_rank: {ranks_mid[i]} \t end_rank: {ranks_end[i]} \t Deviation: {arrow(devi[i])}')mid_rank: 5 end_rank: 6 Deviation: ⬇️-1 mid_rank: 5 end_rank: 1 Deviation: ⬆️4 mid_rank: 16 end_rank: 18 Deviation: ⬇️-2 mid_rank: 7 end_rank: 8 Deviation: ⬇️-1 mid_rank: 8 end_rank: 16 Deviation: ⬇️-8 mid_rank: 18 end_rank: 14 Deviation: ⬆️4 mid_rank: 11 end_rank: 4 Deviation: ⬆️7 mid_rank: 4 end_rank: 2 Deviation: ⬆️2 mid_rank: 10 end_rank: 19 Deviation: ⬇️-9 mid_rank: 2 end_rank: 12 Deviation: ⬇️-10 mid_rank: 17 end_rank: 3 Deviation: ⬆️14 mid_rank: 19 end_rank: 17 Deviation: ⬆️2 mid_rank: 14 end_rank: 15 Deviation: ⬇️-1 mid_rank: 9 end_rank: 10 Deviation: ⬇️-1 mid_rank: 11 end_rank: 7 Deviation: ⬆️4 mid_rank: 11 end_rank: 5 Deviation: ⬆️6 mid_rank: 15 end_rank: 13 Deviation: ⬆️2 mid_rank: 3 end_rank: 11 Deviation: ⬇️-8 mid_rank: 0 end_rank: 9 Deviation: ⬇️-9 mid_rank: 0 end_rank: 0 Deviation: =0
2. 버블 정렬
버블 정렬
처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘이다.
실습
새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워 보자. 학생들의 키는
random모듈을 이용해서 170~185 사이로 생성한다.
import random
height = []
for i in range(20):
height_ran = random.randint(170, 185)
height.append(height_ran)
print(f'기존 height: {height}')
for i in range(len(height)):
for j in range(len(height)-1):
if height[j] > height[j+1]:
height[j], height[j+1] = height[j+1], height[j]
print(f'정렬 후 height: {height}')기존 height: [176, 171, 184, 182, 172, 185, 178, 171, 177, 173, 170, 177, 181, 176, 172, 185, 173, 174, 173, 171] 정렬 후 height: [170, 171, 171, 171, 172, 172, 173, 173, 173, 174, 176, 176, 177, 177, 178, 181, 182, 184, 185, 185]
3. 삽입 정렬
삽입 정렬
정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.
실습
1부터 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.
- 생성된 난수들을 오름 차순 또는 내림 차순으로 정렬하는 알고리즘 구현
- 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현
import random
nums = []
for i in range(100):
rand_num = random.randint(1,1000)
nums.append(rand_num)
print(f'not sortedNumber: {nums}')
for i1 in range (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'sortedNumber by ASC: {nums}')
nums.reverse()
print(f'sortedNumber by DESC: {nums}')
print(f'MinNumber: {nums[99]}')
print(f'MinNumber: {nums[0]}')not sortedNumber: [246, 213, 594, 709, 537, 619, 93, 962, 164, 170, 694, 362, 341, 222, 570, 166, 690, 638, 394, 63, 728, 869, 72, 793, 961, 420, 63, 50, 948, 585, 898, 265, 146, 965, 597, 943, 686, 235, 923, 784, 363, 78, 95, 98, 114, 886, 207, 626, 42, 603, 630, 460, 847, 172, 981, 901, 633, 397, 157, 188, 365, 789, 424, 226, 383, 243, 736, 889, 493, 865, 631, 760, 97, 771, 346, 163, 452, 413, 349, 511, 629, 820, 66, 590, 277, 708, 720, 95, 684, 379, 505, 564, 289, 120, 407, 643, 587, 112, 824, 227] sortedNumber by ASC: [42, 50, 63, 63, 66, 72, 78, 93, 95, 95, 97, 98, 112, 114, 120, 146, 157, 163, 164, 166, 170, 172, 188, 207, 213, 222, 226, 227, 235, 243, 246, 265, 277, 289, 341, 346, 349, 362, 363, 365, 379, 383, 394, 397, 407, 413, 420, 424, 452, 460, 493, 505, 511, 537, 564, 570, 585, 587, 590, 594, 597, 603, 619, 626, 629, 630, 631, 633, 638, 643, 684, 686, 690, 694, 708, 709, 720, 728, 736, 760, 771, 784, 789, 793, 820, 824, 847, 865, 869, 886, 889, 898, 901, 923, 943, 948, 961, 962, 965, 981] sortedNumber by DESC: [981, 965, 962, 961, 948, 943, 923, 901, 898, 889, 886, 869, 865, 847, 824, 820, 793, 789, 784, 771, 760, 736, 728, 720, 709, 708, 694, 690, 686, 684, 643, 638, 633, 631, 630, 629, 626, 619, 603, 597, 594, 590, 587, 585, 570, 564, 537, 511, 505, 493, 460, 452, 424, 420, 413, 407, 397, 394, 383, 379, 365, 363, 362, 349, 346, 341, 289, 277, 265, 246, 243, 235, 227, 226, 222, 213, 207, 188, 172, 170, 166, 164, 163, 157, 146, 120, 114, 112, 98, 97, 95, 95, 93, 78, 72, 66, 63, 63, 50, 42] MinNumber: 42 MinNumber: 981
4. 선택 정렬
선택 정렬
주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘이다.
실습
선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자. 시험 점수는 50부터 100까지로 한다.
import random
scores = []
for i in range(20):
sc_rand = random.randint(50, 100)
scores.append(sc_rand)
print(f'scores: {scores}')
for i in range(len(scores)-1): # 오름차순
minIdx = i
for j in range(i+1, len(scores)):
if scores[minIdx] > scores[j]:
minIdx = j
scores[minIdx], scores[i] = scores[i], scores[minIdx]
print(f'result(ASC): {scores}')
for i in range(len(scores)-1): # 내림차순
maxIdx = i
for j in range(i+1, len(scores)):
if scores[maxIdx] < scores[j]:
maxIdx = j
scores[maxIdx], scores[i] = scores[i], scores[maxIdx]
print(f'result(DESC): {scores}')scores: [51, 64, 77, 71, 84, 69, 81, 61, 56, 91, 100, 66, 94, 59, 56, 80, 84, 77, 96, 60] result(ASC): [51, 56, 56, 59, 60, 61, 64, 66, 69, 71, 77, 77, 80, 81, 84, 84, 91, 94, 96, 100] result(DESC): [100, 96, 94, 91, 84, 84, 81, 80, 77, 77, 71, 69, 66, 64, 61, 60, 59, 56, 56, 51]
5. 병합 정렬
병합정렬
자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.
def mSort(ns):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
leftNums = mSort(ns[0:midIdx])
rightNums = mSort(ns[midIdx:len(ns)])
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 = mergeNums + leftNums[leftIdx:]
mergeNums = mergeNums + rightNums[rightIdx:]
return mergeNums
nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(mSort(nums))실습
1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.
- 병합정렬 알고리즘을 이용한 난수 정렬 모듈 구현
- 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가
def mSort(ns):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
leftNums = mSort(ns[0:midIdx])
rightNums = mSort(ns[midIdx:len(ns)])
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 = mergeNums + leftNums[leftIdx:]
mergeNums = mergeNums + rightNums[rightIdx:]
return mergeNums
import random
nums = []
for i in range (10):
num = random.randint(1,100)
nums.append(num)
new_sort = mSort(nums)
print(f'not sorted rNums: {nums}')
print(f'merge sorted rNums by ASC: {new_sort}')
new_sort.reverse()
print(f'merge sorted rNums by DESC: {new_sort}')6. 퀵 정렬
퀵정렬
기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
def qSort(ns):
if len(ns) < 2:
return ns
midIdx = len(ns)//2
midVal = ns[midIdx]
smallNums = []; sameNums = []; bigNums = []
for n in ns:
if n < midVal:
smallNums.append(n)
elif n == midVal:
sameNums.append(n)
else:
bigNums.append(n)
return qSort(smallNums) + sameNums + qSort(bigNums)
nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(qSort(nums))실습
1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자.
- 퀵정렬 알고리즘을 이용한 난수 정렬 모듈 구현
- 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가
def qSort(ns):
if len(ns) < 2:
return ns
midIdx = len(ns)//2
midVal = ns[midIdx]
smallNums = []; sameNums = []; bigNums = []
for n in ns:
if n < midVal:
smallNums.append(n)
elif n == midVal:
sameNums.append(n)
else:
bigNums.append(n)
return qSort(smallNums) + sameNums + qSort(bigNums)
import random
nums = []
for i in range (10):
num = random.randint(1,100)
nums.append(num)
new_sort = qSort(nums)
print(f'not sorted rNums: {nums}')
print(f'merge sorted rNums by ASC: {new_sort}')
new_sort.reverse()
print(f'merge sorted rNums by DESC: {new_sort}')
낭만젊음사랑