이미 정렬이 된 값에서 임의적으로 어떤 값을 위치시키는 방식
→ 정렬되어 있는 자료 배열과 비교해서 정렬 위치를 찾아나간다.
nums = [5,10,2,1,0]
# 앞에서부터 비교할 필요 없고, 2번째자리부터 앞과 비교해나가면 된다.
# 오름차순 정렬
for i1 in range(1,len(nums)):
i2 = i1 - 1 # 이전의 인덱스값을 지정해준다
cNum = nums[i1] # 기준 위치의 값
while nums[i2] > cNum and i2 >= 0: # 이전 인덱스값이 더 크고, 0인덱스위치 이상일 경우에만 위치를 변경해줘야 한다
nums[i2 + 1] = nums[i2] # 비교하는 위치의 인덱스 값의 위치를 뒤로 보낸다.
i2 -= 1
nums[i2 + 1] = cNum
print(f'nums : {nums}')
Python
복사
# 내림차순 정렬
nums = [5,10,2,1,0]
# 앞에서부터 비교할 필요 없고, 2번째자리부터 앞과 비교해나가면 된다.
# 오름차순 정렬
for i1 in range(1,len(nums)):
i2 = i1 - 1 # 이전의 인덱스값을 지정해준다
cNum = nums[i1] # 기준 위치의 값
while nums[i2] < cNum and i2 >= 0: # 이전 인덱스값이 더 크고, 0인덱스위치 이상일 경우에만 위치를 변경해줘야 한다
nums[i2 + 1] = nums[i2] # 비교하는 위치의 인덱스 값의 위치를 뒤로 보낸다.
i2 -= 1
nums[i2 + 1] = cNum # 필수
print(f'nums : {nums}')
Python
복사
# 1부터 1000까지의 난수 100개를 생성하고 요구 사항을 만족하는 모듈을 만들자.
# 난수들을 오름차순, 또는 내림차순 정렬하는 알고리즘 구현
# 난수 중 최솟값, 최댓값을 반환하는 함수 구현
import random
Nums = []
for _ in range(100):
Nums.append(random.randint(1,1000))
print(Nums)
# 1. 오름차순
# 두번째 위치부터 비교하면됨. 이유: 이전값과 크기를 비교해나가기 때문
for i1 in range(1,len(Nums)): # 2번째부터 마지막 원소까지 확인
i2 = i1 - 1 # 바로 이전 인덱스 저장
cNum = Nums[i1] # 기준 위치의 값
# 이전 인덱스 값이 더 크고, 인덱스가 0보다 클 경우에만 위치 변경을 반복한다.
while Nums[i2] > cNum and i2 >= 0:
Nums[i2 + 1] = Nums[i2]
i2 -= 1 # i2 를 하나씩 줄여나가야지 아래에 있는 값들을 확인할 수 있다
Nums[i2 + 1] = cNum # 맨 마지막에 cNum의 위치를 최종적으로 결정해준다.
print(Nums)
Python
복사
# 위 결과를 사용해서 class 만들자.
class SortNumbers:
def __init__(self,ns,asc=True):
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]
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[-1]
def getMaxNumber(self):
if self.isAsc:
return self.nums[-1]
else:
return self.nums[0]
Python
복사
import random
nums = []
for _ in range(100):
nums.append(random.randint(1,1000))
print(f'not sorted Numbers : {nums}')
# 객체 생성
import insertSort as sn
Nums = sn.SortNumbers(nums)
# 오름차순
Nums.setSort()
sortedNums = Nums.getSortedNumbers()
print(f'sorted Numbers by ASC: {sortedNums}')
# 내림차순
Nums.isAscending(False)
Nums.setSort()
sortedNums = Nums.getSortedNumbers()
print(f'sorted Numbers by DESC: {sortedNums}')
# 최솟값 / 최댓값
print(f'최솟값 출력 : {Nums.getMinNumber()}')
print(f'최댓값 출력 : {Nums.getMaxNumber()}')
Python
복사
# insertSort.py
import copy
def InsertSort(ns, asc=True):
c_ns = copy.copy(ns)
# 이미 정렬되어 있는 곳에서 들어갈 자리를 찾아가는 구조
for i1 in range(1, len(c_ns)): # 두번째 인덱스부터 들어갈 위치를 구해주면 된다.
i2 = i1 - 1 # 비교할 기준값 이전의 인덱스 위치를 지정
c_Num = c_ns[i1] # 비교할 기준값(현재값) 저장
if asc: #오름차순
while c_Num < c_ns[i2] and i2 >= 0: # 현재값이 더 작고, i2 인덱스가 0이상일때
c_ns[i2 + 1] = c_ns[i2] # 비교된 이전 값을 뒤로 보낸다.
i2 -= 1 # 그리고 더 앞의 인덱스와도 비교
else: # 내림차순
while c_Num > c_ns[i2] and i2 >= 0: # 현재값이 더 크고, i2 인덱스가 0이상일때
c_ns[i2 + 1] = c_ns[i2]
i2 -= 1
c_ns[i2 + 1] = c_Num
print(f'c_ns : {c_ns}')
return c_ns
Python
복사
import random
import insertSort
nums = random.sample(range(1,21),10)
print(f'not sorted nums :{nums}')
result = insertSort.InsertSort(nums)
print(f' sorted nums by asc : {result}')
result2 = insertSort.InsertSort(nums,False)
print(f' sorted nums by desc : {result2}')
Python
복사