Day41. 알고리즘 (2)

순위 - 실습

• 순위(실습)

• 학급 학생(20명)들의 중간고사와 기말고사 성적을 이용해서 각각의 순위를 구하고,
  중간고사 대비 기말고사 순위 변화(편차)를 출력하는 프로그램을 만들어보자!
  (시험 성적은 난수를 이용한다!)

모듈 코드 부분

class RankDeviation:

    def __init__(self, mss, ess):   # mss 중간고사, ess 기말고사
        self.midStuScos = mss
        self.endStuScos = ess
        self.midRanks = [0 for i in range(len(mss))]
        self.endRanks = [0 for i in range(len(mss))]
        self.rankDeviation = [0 for i in range(len(mss))]

    def setRank(self, ss, rs):  # ss 점수, rs 순위
            for idx, score1 in enumerate(ss):
                for score2 in ss:
                    if score1 < score2:
                        rs[idx] += 1

    def setMidRank(self):
        self.setRank(self.midStuScos, self.midRanks)

    def getMidRank(self):
        return self.midRanks

    def setEndRank(self):
        self.setRank(self.endStuScos, self.endRanks)

    def getEndRank(self):
        return self.endRanks

    def printRankDeviation(self):

        for idx , mRank in enumerate(self.midRanks):
            deviation = mRank - self.endRanks[idx]

            if deviation > 0:
                deviation = '↑' + str(abs(deviation))

            elif deviation < 0:
                deviation = '↓' + str(abs(deviation))

            else:
                deviation = '=' + str(abs(deviation))

            print(f'mid_rank : {mRank} \t end_rank : {self.endRanks[idx]} \t Deviation : {deviation}')

실행 코드 부분

import rank_module as rm
import random

midStuScos = random.sample(range(50,101), 20)
endStuScos = random.sample(range(50,101), 20)

rd = rm.RankDeviation(midStuScos, endStuScos)

rd.setMidRank()
print(f'midStuScores : {midStuScos}')
print(f'mid_rank : {rd.getMidRank()}')

rd.setEndRank()
print(f'endStuScores : {endStuScos}')
print(f'end_rank : {rd.getEndRank()}')

rd.printRankDeviation()

복습 꼭 꼭 꼭!

버블 정렬 - 이론

• 버블정렬

• 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘이다!
  
  
  10 2 7 21 0
  
  
  [2, 10, 7, 21, 0] 7과 10 비교
  [2, 7, 10, 21, 0] 10과 21 비교
  [2, 7, 10, 21, 0] 21과 0 비교
  [2, 7, 10, 0, 21] 21이 가장 뒤로 왔다!
  
  
  [2, 7, 10, 0, 21] 7과 10 비교
  [2, 7, 10, 0, 21] 10과 0 비교
  [2, 7, 0, 10, 21] 10과 0 비교
  
  
  [2, 7, 0, 10, 21] 7과 0 비교
  [2, 0, 7, 10, 21] 7과 0 비교
  
  
  [2, 0, 7, 10, 21] 2와 0 비교
  [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):  # 끝까지 비교할 필요가 없으므로 -i! ★★★★★★★
        if nums[j] > nums[j+1]: # 10과 2랑 비교했을때 자리를 바꿔야 하는 경우!
            # temp = nums[j]  # 순서바꾸기 1
            # nums[j] = nums[j+1] # 순서바꾸기 2
            # nums[j+1] = temp    # 순서바꾸기 완료!

            nums[j], nums[j+1] = nums[j+1], nums[j] # 순서바꾸기 1,2,3을 한줄로!

        print(nums) # 자리 바뀌는 과정
    print()

print(f'sorted nums : {nums}')

버블 정렬 - 실습

• 버블정렬

• 새 학년이 되어 학급에 20명의 새로운 학생들이 모였다.
  학생들을 키 순서로 줄 세워 보자.
  학샐들의 키는 random 모듈을 이용해서 170~185사이로 생성한다!

모듈 코드 부분

• 얕은 복사 버전

### 얕은 복사 버전 ###
def bubbleSort(ns): # ns : nums

    length = len(ns) - 1 # 가장 끝에서 바로 앞까지만 비교하면 되므로!
    for i in range(length):
        for j in range(length - i):
            if ns[j] > ns[j + 1]:
                ns[j], ns[j + 1] = ns[j + 1], ns[j]

    return ns

• 깊은 복사 버전

### 깊은 복사 버전 ###

import copy
def bubbleSort(ns, deepCopy = True): # ns : nums

    if deepCopy:
        cns = copy.copy(ns) # 원본 데이터를 복사해서 새로운 데이터를 만든다!
    else:   # deepCopy = False인 경우!
        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 module_bubbleSort as mbs

students = []

for i in range(20): # 학생 20명 키 랜덤으로 생성!
    students.append(rd.randint(170, 185))

print(f'students : {students}')

sortedStudents = mbs.bubbleSort(students, deepCopy = True) # deepCopy로 원본을 깊은 복사할지 얕은 복사할지 선택 가능!

print(f'students : {students}') # students도 정렬된 후의 모습으로 출력된다!
print(f'sortedStudents : {sortedStudents}')

##### 깊은 복사와 얕은 복사 생각해보기! #####
# 변수명만 달르지 데이터가 똑같다 -> 얕은 복사

삽입 정렬 - 이론

• 삽입정렬

• 정렬 위치를 찾아 들어가자!
  
  
  정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다!
  [5 10] 2 1 0 --> 2 5 10
  [2 5 10] 1 0 --> 1 2 5 10
  [1 2 5 10] 0 --> 0 1 2 5 10
  0 1 2 5 10

• 오름차순

## 오름차순
nums = [5, 10, 2, 1, 0]

for i1 in range(1, len(nums)):  # 리스트의 두번째 자리부터 시작해서 첫번째와 비교하기 시작!
    i2 = i1 - 1
    cNum = nums[i1]

    ### while 문의 > 방향을 바꿔줌에 따라서 오름차순, 내림차순으로 정렬을 바꿀 수 있다!
    while nums[i2] > cNum and i2 >= 0:  # 인덱스i2의 앞자리와 계속 비교하고, 0번째보다는 클때! 계속 비교
        nums[i2 + 1] = nums[i2]
        i2 -= 1

    nums[i2 +1] = cNum

    print(f'nums : {nums}')
print(f'ascending nums : {nums}')

• 내림차순

## 내림차순

nums = [5, 0, 2, 10, 1]

for i1 in range(1, len(nums)):  # 리스트의 두번째 자리부터 시작해서 첫번째와 비교하기 시작!
    i2 = i1 - 1
    cNum = nums[i1]

    ### while 문의 > 방향을 바꿔줌에 따라서 오름차순, 내림차순으로 정렬을 바꿀 수 있다!
    while nums[i2] < cNum and i2 >= 0:  # 인덱스i2의 앞자리와 계속 비교하고, 0번째보다는 클때! 계속 비교
        nums[i2 + 1] = nums[i2]
        i2 -= 1

    nums[i2 +1] = cNum

    print(f'nums : {nums}')
print(f'descending nums : {nums}')