정렬
특징
정렬이란, 어떠한 자료를 정해진 순서대로 정리하는것을 말한다. 정렬을 왜 하는가에 대한 대답은 우리 모두가 잘 알고있다. 정렬이 잘 되어있으면, 즉 정돈이 잘 되어있는 자료에서는 데이터를 찾아내기가 쉽기 때문이다. (나는 어지러진곳에서 더 잘 찾는다는 분들은 아마 힙정렬을 이용하는게 아닌가 싶다.)
알고리즘과 자료구조의 기초가 되는것이 바로 정렬이지만, 정작 100% 이해하고 쓰는것같지는 않다.
선택 정렬
정렬들의 이름은 특이하게 한글로 보는것보다 영어로 보는게 이해가 더 빠를때가 많다. 선택정렬은 Selection 정렬이다. 말 그대로 선택해서 정렬하라는 뜻이다. 리스트에서 가장 작은 숫자를 선택해서 앞쪽으로 옮기는 방법을 사용한다.
선택정렬의 구현
def selection(n):
for i in range(len(n)):
tmp = i
for j in range(i + 1, len(n)): # i 다음원소부터 마지막까지 반복
if (n[tmp] >= n[j]):
tmp = j # 만약 tmp가 j 보다 크다면 tmp를 j로 바꾼다. 리스트를 다 돌고 나면 tmp가 가장 작은 값이 되어있음.
n[i], n[tmp] = n[tmp], n[i]
return n 삽입 정렬
삽입정렬은 카드를 정리하는 방법과 유사하다. 손 안에 정렬된 카드가 있다고 할 때, 우리는 한장을 새로 받으면 그 카드를 올바른 위치에 꼽아넣는다. 이러한 방식으로 정렬하는것이 삽입정렬이다.
삽입정렬의 구현
def insertion(n):
for i in range(1, len(n)):
j = i - 1 # j는 현재 원소보다 하나 전 원소
nxt_ele = n[i] # 현재원소는 nxt_ele에 넣음
while (n[j] > nxt_ele) and (j >= 0): # 하나 전 원소가 다음원소(i)보다 큰 동안, 즉 미정렬 상태인동안
n[j + 1] = n[j] #
j = j - 1
n[j + 1] = nxt_ele
return n버블 정렬
버블정렬은 사실 왜 이런 이름이 붙었는지 모를 정렬이다. 하지만 원리는 가장 간단하다. 인접한 두 원소를 비교-교환한다.
버블정렬의 구현
def bubble(n):
for i in range(len(n) - 1, 0, -1): # 리스트의 끝에서부터 시작
for idx in range(i): # 앞에서 부터 다시 카운팅
if n[idx] > n[idx + 1]: # 현 원소와 다음 원소 비교
n[idx], n[idx + 1] = n[idx + 1], n[idx] # 조건 성립시 교환
return n뭔가 이상하지 않은가? 그렇다. 이미 정렬되어 있더라도 계속 정렬을 해야하는 비효율적인 구조이다.
def improved_bubble(n):
for i in range(len(n) - 1, 0, -1):
sorted = True
for idx in range(i):
if n[idx] > n[idx + 1]:
n[idx], n[idx + 1] = n[idx + 1], n[idx]
sorted = False # 해당과정을 들어오지 않으면 이미 sorted되어있다는 뜻
if (sorted):
break # 정렬되어있는 경우 그만돌림
return n이런식으로 sorted를 이용하면 더 빠르게 정렬이 가능하다.
정렬 응용
정렬을 응용하면 다양한것을 할 수 있겠지만, 우리가 앞에서 미리 작성했던 class Set의 경우 뛰어난 성능향상을 보인다.
정렬된 집합
집합에서 주된 기능은 합집합, 차집합, 여집합이다. 기존의 방식에서는 이를 작성할 때 이중 for문을 활용하여 두 집합을 검사하였지만, 만약 정렬되어 있다면 이러한 과정을 줄일 수 있다. 수의 값이 점점 더 커질것을 알기에, 더 이상 정리할 필요가 없기 때문이다.
정렬된 집합의 구현
class Set:
def __init__(self):
self.items = []
def sort(self):
sorted(self.items)
def size(self):
return len(self.items)
def display(self, msg):
print(msg, self.items)
def contains(self, item):
return item in self.items
def insert(self, elem):
if elem in self.items:
return
for idx in range(len(self.items)):
if elem < self.items[idx]:
self.items.insert(idx, elem)
self.sort()
return
self.items.append(elem)
def delete(self, elem):
if elem in self.items:
self.items.remove(elem)
def __eq__(self, setB):
if self.size() != setB.size():
return False
for idx in range(len(self.items)):
if self.items[idx] != setB.items[idx]:
return False
return True
def union(self, setB):
self.sort()
setB.sort()
setC = Set()
a = b = 0
while a < len(self.items) and b < len(setB.items):
ValueA = self.items[a]
ValueB = setB.items[b]
if ValueA < ValueB:
setC.items.append(ValueA)
a += 1
elif ValueA > ValueB:
setC.items.append(ValueB)
b += 1
else:
setC.items.append(ValueA)
a += 1
b += 1
while a < len(self.items):
setC.items.append(self.items[a])
a += 1
while b < len(self.items):
setC.items.append(setB.items[b])
b += 1
return setC
def intersect(self, setB):
self.sort()
setB.sort()
setC = Set()
a = b = 0
while a < len(self.items) and b < len(setB.items):
ValueA = self.items[a]
ValueB = setB.items[b]
if ValueA == ValueB:
setC.items.append(ValueA)
a += 1
b += 1
elif ValueA < ValueB:
a += 1
else:
b += 1
return setC
def difference(self, setB):
self.sort()
setB.sort()
setC = Set()
a = b = 0
while a < len(self.items) and b < len(setB.items):
ValueA = self.items[a]
ValueB = setB.items[b]
if ValueA == ValueB:
a += 1
b += 1
elif ValueA > ValueB:
b += 1
elif ValueA < ValueB:
setC.items.append(ValueA)
a += 1
while a < len(self.items):
setC.items.append(self.items[a])
a += 1
return setC
#--------------------------------------------------------------------------
# Driver code
def main():
setA = Set()
setA.insert('휴대폰')
setA.insert('지갑')
setA.insert('손수건')
setA.display('Set A:')
setB = Set()
setB.insert('빗')
setB.insert('파이썬 자료구조')
setB.insert('야구공')
setB.insert('지갑')
setB.display('Set B:')
setB.insert('빗')
setA.delete('손수건')
setA.delete('발수건')
setA.display('Set A:')
setB.display('Set B:')
setA.union(setB).display('A U B: ')
setA.intersect(setB).display('A ^ B: ')
setA.difference(setB).display('A – B: ')
print('A == B: ', setA.__eq__(setB))
if __name__ == '__main__':
main()
기존의 기능과 크게 다를것이 없으나 교집합, 합집합, 차집합을 담당하는 부분은 많이 달라졌다.
우선 교집합 부터 살펴보겠다
intersect
def intersect(self, setB):
self.sort()
setB.sort()
setC = Set()
a = b = 0
while a < len(self.items) and b < len(setB.items):
ValueA = self.items[a]
ValueB = setB.items[b]
if ValueA == ValueB:
setC.items.append(ValueA)
a += 1
b += 1
elif ValueA < ValueB:
a += 1
else:
b += 1
return setC정렬된 두 집합 A, B가 있고, 이들의 교집합을 C에 담고자한다. 두 함수는 정렬이 되어 있기에 반복문을 통해 동시에 해당 집합들에 접근하면서, 겹치는 값을 C에 추가하고, 더 작은 쪽의 인덱스를 올려가면서 끝까지 탐색하는 방식을 취하면 기존의 이중 for문보다 훨씬 빠르게 정리가 가능하다.
Union
def union(self, setB):
self.sort()
setB.sort()
setC = Set()
a = b = 0
while a < len(self.items) and b < len(setB.items):
ValueA = self.items[a]
ValueB = setB.items[b]
if ValueA < ValueB:
setC.items.append(ValueA)
a += 1
elif ValueA > ValueB:
setC.items.append(ValueB)
b += 1
else:
setC.items.append(ValueA)
a += 1
b += 1
while a < len(self.items):
setC.items.append(self.items[a])
a += 1
while b < len(self.items):
setC.items.append(setB.items[b])
b += 1
return setC합집합의 경우 교집합과 비슷하다. 두 함수는 정렬이 되어 있기에 반복문을 통해 동시에 해당 집합들에 접근하면서, 더 작은 값들을 함수 C에 넣으면서, 동시에 작은 쪽의 index를 키운다. 만약 크기관계가 반전된다면 다시 작은쪽을 키워나간다. 만약 둘다 같다면, 원소를 넣은 후 두 집합의 인덱스를 동시에 키운다. 어느 한쪽이 끝에 달했다면, 남은 원소를 전부 C에 넣는다. 이런 방식으로 기존의 이중 for문보다 훨씬 빠르게 정리가 가능하다.
Difference
def difference(self, setB):
self.sort()
setB.sort()
setC = Set()
a = b = 0
while a < len(self.items) and b < len(setB.items):
ValueA = self.items[a]
ValueB = setB.items[b]
if ValueA == ValueB:
a += 1
b += 1
elif ValueA > ValueB:
b += 1
elif ValueA < ValueB:
setC.items.append(ValueA)
a += 1
while a < len(self.items):
setC.items.append(self.items[a])
a += 1
return setC차집합의 경우 기존의 방식과 조금 다르다. 반복문을 통해 동시에 해당 집합들에 접근하는것까진 동일하다. 하지만 이는 서로 다른 값을 넣는 과정이기에,
1) 같은 값인 경우 :
차집합의 특성상 넣을 수가 없어서 인덱스를 하나씩 올린다.
2) A가 B보다 큰 경우 :
A - B이기에 이 경우 A보다 작은 B가 존재할 수 없고 A는 아직 차집합여부가 확인되지 않았다. 따라서 b의 인덱스를 올린다.
3) B가 A보다 큰 경우 :
위의 모든 조건에 걸리지 않으면서 B가 A보다 크면 해당 A는 B에 중복되는값이 없고 더 이상 나올 가능성도 없다는 뜻이다. 따라서 C에 삽입한다
마무리
위와 같은 방식으로 정렬을 활용할 수 있고, 고급정렬에 대해서는 다른 글에서 상세하게 다뤄놨다!
정렬은 이 밖에도 무수히 많은 알고리즘이 존재한다. 이에 관해서는 방학 때 시간이 비면 그때 정리를 하도록 하겠다.
탐색의 경우 글이 너무 길어져 다음 글에서 더 다루도록 하겠다.
