[알고리즘] 삽입 정렬

1. 삽입 정렬

정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.
index를 늘려가면서 비교를 한다.

5 10 2 1 0 -> 2 5 10
5와 10을 비교

2 5 10 1 0 -> 1 2 5 10
2, 5, 10을 비교 순서를 바꿔준다.

1 2 5 10 0 -> 0 1 2 5 10
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 # index 0의 자리를 나타낸다. 비교를 하기 위해 설정한다.
    cNum = nums[i1]

    while nums[i2] > cNum and i2 >= 0: # index값이 0미만이면 오류가 발생한다.
        nums[i2 + 1] = nums[i2] #자리를 바꾼 뒤
        i2 -= 1 # 계속해서 진행이 되기 위해 while문이 돌기 위해 하나씩 빼주면 된다.

    nums[i2 + 1] = cNum

    print(f'nums: {nums}')

처음 두개의 숫자를 비교하기 위해 i1은 index 1부터 시작을 하고,
i2는 index 0부터 시작을 한다.

cNum = nums[i1]
while nums[i2] > cNum and i2 >= 0:
현재 원소를 적절한 위치로 삽입하는 역할 nums[i2]>cNum 비교하고 있는 원소가 삽입하려는 위치보다 작은 경우에만 실행
index값이 0미만이면 오류가 발생할 경우를 대비해 작성한 코드이다.
nums[i2 + 1] = nums[i2] # 자리를 바꾼 뒤
i2 -= 1 # 계속해서 진행이 되기 위해 while문이 돌기 위해 하나씩 빼주면 된다. 왼쪽으로 이동한다.

조건을 만족하면 cNum이 된다.
nums[i2 + 1] = cNum

2. 삽입 정렬 실습

1부터 1000까지의 난수 100개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어 본다.

1) 생성된 난수들을 오름 차순 또는 내림 차순으로 정렬하는 알고리즘 구현
2) 생성된 난수 중 최솟값, 최댓값을 반환하는 함수를 구현한다.

알고리즘을 아는것도 중요하지만 클래스나 모듈이나 함수로 만들어서 재활용 하는 것도 중요하다.

• 클래스 코드

class SortNumbers:
    def __init__(self, ns, asc=True):
        self.nums = ns # ns 이건 그냥 nums가 된다는 조건이다.
        self.isAsc = asc # 무조건 asc=True가 된다는 조건이다.

    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: # descending
                while self.nums[i2] < cNum and i2 >= 0:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1

            self.nums[i2 + 1] = cNum # 현재 값에 nums[i2 + 1]
            
    def getSortedNumbers(self): # 외부에서 sort가 된 배열을 가져올 수 있도록 한다.
        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]코드를 입력하세요

self.nums[i2 + 1] = cNum
현재 값에 nums[i2 + 1]을 왜 사용해야 하는지 궁금하다.

• main 코드

import random
import sort as sm

nums = random.sample(range(1,1000),100)
print(f'not sorted numbers: {nums}')

# 객체 생성
sn = sm.SortNumbers(nums) # class를 불러온다.

# 오름 차순 (ascending)
sn.setSort() # setSort()함수를 사용한다.

sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers asc : {sortedNumbers}')

# 내림 차순 true값이 적용되어 있으니깐 isAscending이 false값으로 한다.
sn.isAscending(False)
sn.setSort()
sortedNumbers = sn.getSortedNumbers()
print(f'sortedNumbers desc : {sortedNumbers}')

# 최솟값
print(f'min: {sn.getMinNumber()}')
print(f'max: {sn.getMaxNumber()}')