Day42. 알고리즘 (3)

삽입 정렬 - 실습

• 삽입정렬(실습)

• 정렬 위치를 찾아 들어가자!
  
  
  1부터 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자
  
  
  요구사항1) 생성된 난수들을 오름 차순 또는 내림 차순으로 정렬하는 알고리즘 구현
  요구사항2) 생성된 난수 중 최소값, 최대값을 반환하는 함수 구현

모듈 파일 코드

class SortNumbers:

    def __init__(self, ns, asc=True): # ns: number, asc: 오름차순, 내림차순 결정!
        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]    # cNum: current number

            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 module_insertSort 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 DESC : {sortedNumbers}')

# min & max
print(f'min : {sn.getMinNumber()}')
print(f'max : {sn.getMaxNumber()}')

선택 정렬 - 이론

• 선택정렬 이란?

• 주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘이다.
  
  
  4 2 5 [1] 3
  ↙
  [1] 2 5 4 [3]
  ↙
  1 2 [3] 4 5

nums = [4, 2, 5, 1, 3]

for i in range(len(nums) -1):   # 첫숫자가 기준부터 맨뒤에서 하나 앞까지!
    minIdx = i

    for j in range(i + 1, len(nums)):   # i보다 하나 더 큰곳부터 끝까지 비교!
        if nums[minIdx] > nums[j]:
            minIdx = j

    print(f'sort log : {nums}')

    tempNum = nums[i]
    nums[i] = nums[minIdx]
    nums[minIdx] = tempNum

    # 1,2,3 과정을 한줄로!
    nums[i], nums[minIdx] = nums[minIdx], nums[i]
    # print(f'sort log : {nums}')

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

선택 정렬 - 실습

• 선택정렬 실습

• 선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자.
  시험 점수는 50부터 100까지로 한다!

import random
import module_selectSort as sm
import copy # 깊은 복사를 위함! (원본 데이터를 보존할 수 있다!)

scores = random.sample(range(50, 101), 20)

print(f'scores : {scores}')
print(f'scores length : {len(scores)}')

result = sm.sortNumber(copy.deepcopy(scores))
print(f'원본 확인scores : {scores}')
print(f'오름차순 result : {result}')

result = sm.sortNumber(copy.deepcopy(scores), asc = False)   # 내림차순
print(f'원본 확인scores : {scores}')
print(f'내림차순 result : {result}')

# 정렬 후에도 정렬전의 데이터가 영향 받지 않게 하려면!
# 얕은 복사, 깊은 복사 생각하기!

정렬 후에도 정렬전의 데이터가 영향 받지 않게 하려면!
얕은 복사, 깊은 복사 생각하기!

최댓값 - 이론

• 최댓값

• 가장 큰 값을 찾자!
  
  
  자료구조에서 가장 큰 값을 찾는다!
  
  
  nums = [-2, -4, 5, 7, 10, 0, 8, 20, -11]
  ↓
  maxNum = nums[0]
  ↓
  maxNum < num[1], nums[2], nums[3], ... nums[n]

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0

    def getMaxNum(self):
        self.maxNum = self.nums[0]  # maxNum을 일단 가장 첫번째수로 설정

        for n in self.nums:
            if self.maxNum < n:
                self.maxNum = n # maxNum을 비교해서 계속 큰수로 설정!

        return self.maxNum

nums = [-2, -4, 5, 7, 10, 0, 8, 20, -11]

ma = MaxAlgorithm(nums)
maxNum = ma.getMaxNum()

print(f'maxNum : {maxNum}')

최댓값 - 실습

• 최댓값 실습

• 리스트에서 아스키코드가 가장 큰 값을 찾는 알고리즘을 만들어보자!

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):  # ord() 문자를 아스키코드값으로 변환해 주는 함수!
                self.maxChar = c

        return self.maxChar

chars = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']

mc = MaxAlgorithm(chars)
maxChar = mc.getMaxChar()
print(f'maxChar : {maxChar}')


class CharToAscii():

    def __init__(self, css):

        self.chars = css
        self.ordchars = []

    def changeord(self):

        for o in self.chars:
            aaa = ord(o)
            self.ordchars.append(aaa)

        return  self.ordchars

chars = ['c', 'x', 'Q', 'A', 'e', 'P', 'p']
mc = CharToAscii(chars)
ordChar = mc.changeord()
print(f'ordChar : {ordChar}')