Programming 기초/Python
[Python 자료구조 #정렬과 탐색1] 선택정렬, 삽입정렬, 버블정렬, 정렬 응용한 집합
코딩상륙작전
2023. 5. 23. 21:32
* 정렬(sorting)
- 오름차순( ascending order)
- 내림차순(descending order)
- 레코드(record) : 정렬시켜야 될 대상
- 필드(field) 레코드는 여러 개의 필드로 이루어지고, 필드는 속성들이다.
- 키(key) 또는 정렬 키(sort key) : 정렬의 기준이 되는 필드
- 정렬 : 레코드들을 키(key)의 순서로 재배열하는 것
* 정렬 장소에 따른 분류
- 내부(internal)정렬 : 모든 데이터가 메인 메모리에 올라와 있는 정렬
- 외부(external)정렬 : 외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려 정렬하는 방법으로 대용량 자료를 정렬하기 위해 사용한다.
* 구현 복잡도와 알고리즘 효율성에 따른 분류
- 단순하지만 비효율적인 방법 : 삽입정렬, 선택정렬, 버블 정렬 등
- 복잡하지만 효율적인 방법 : 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬 등
* 안정성에 따른 분류
- 안정성(stability)이란 입력 데이터에 동일한 킷값을 갖는 레코드가 여러 개 존재할 경우, 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것. 안정성을 충족하는 정렬에는 삽입정렬, 버블정렬, 병합정렬 등이 있다.
* 선택 정렬(selection sort)
- 리스트에서 가장 작은 숫자를 선택해서 앞쪽으로 옮기는 방법. 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트의 맨 뒤로 이동하는 작업
- 오른쪽 리스트 : 아직 정렬되지 않은 리스트
- 왼쪽 리스트 : 정렬 완료된 리스트
- 실제로 두 개의 배열을 사용하진 않는다. 정렬이 안 된 리스트에서 최솟값이 선택되면 이 값을 배열의 첫 번째 요소와 교환하면 되기 때문이다.
- 선택 정렬은 입력 배열 이외에 추가적인 배열을 사용하지 않는다. 이러한 정렬 방법을 제자리 정렬(in-place sorting)라고 한다.
- 시간 복잡도 O(n^2)이고 알고리즘이 간단하고, 입력 자료의 구성과 상관없이 자료 이동 횟수가 결정된다는 장점있음.
def selection_sort(A):
n = len(A) # 리스트 n의 길이
for i in range(n - 1): # i = 0 ~ n-2
least = i # 최솟값의 인덱스
for j in range(i + 1, n): # j = i+1 ~ n-1
if A[j] < A[least]:
least = j #최솟값의 인덱스를 찾음
A[i], A[least] = A[least], A[i]
printStep(A, i + 1)
def printStep(arr, val):
print(" Step %2d = " % val, end="")
print(arr)data = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original :", data)
selection_sort(data)
print("Selection :", data)
-----------------------------------------------
Original : [5, 3, 8, 4, 9, 1, 6, 2, 7]
Step 1 = [1, 3, 8, 4, 9, 5, 6, 2, 7]
Step 2 = [1, 2, 8, 4, 9, 5, 6, 3, 7]
Step 3 = [1, 2, 3, 4, 9, 5, 6, 8, 7]
Step 4 = [1, 2, 3, 4, 9, 5, 6, 8, 7]
Step 5 = [1, 2, 3, 4, 5, 9, 6, 8, 7]
Step 6 = [1, 2, 3, 4, 5, 6, 9, 8, 7]
Step 7 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Step 8 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Selection : [1, 2, 3, 4, 5, 6, 7, 8, 9]
* 삽입 정렬(insertion sort)
- 삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 이미 정렬되어 있는 경우는 가장 빠르다 O(n)
- 최악의 경우는 입력 자료가 역으로 정렬된 경우이다.O(n^2)
- 대부분의 레코드가 이미 정렬되어 있는 경우 효율적으로 사용될 수 있다.
- 삽입된 카드로 인해 항목들이 뒤로 이동됨.
def insertion_sort(A):
n = len(A)
for i in range(1, n): # 위부 루프 i = 1 ~ n-1
key = A[i] # key는 삽입 대상
j = i - 1
while j >= 0 and A[j] > key: # 내부 루프
A[j + 1] = A[j] # 항목들을 뒤로 한 칸씩 이동
j -= 1
A[j + 1] = key # 항목 삽입
printStep(A, i)
def printStep(arr, val):
print(" Step %2d = " % val, end="")
print(arr)data = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original :", data)
insertion_sort(data)
print("insertion :", data)
---------------------------------------
Original : [5, 3, 8, 4, 9, 1, 6, 2, 7]
Step 1 = [3, 5, 8, 4, 9, 1, 6, 2, 7]
Step 2 = [3, 5, 8, 4, 9, 1, 6, 2, 7]
Step 3 = [3, 4, 5, 8, 9, 1, 6, 2, 7]
Step 4 = [3, 4, 5, 8, 9, 1, 6, 2, 7]
Step 5 = [1, 3, 4, 5, 8, 9, 6, 2, 7]
Step 6 = [1, 3, 4, 5, 6, 8, 9, 2, 7]
Step 7 = [1, 2, 3, 4, 5, 6, 8, 9, 7]
Step 8 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
insertion : [1, 2, 3, 4, 5, 6, 7, 8, 9]
* 버블정렬(bubble sort)
- 인접한 2개의 레코드를 비교하여 크기가 순서대로가 아니면 서로 교환하는 방법. 비교-교환 과정이 한번 완료되면( 한 번의 스캔) 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다.
def bubble_sort(A):
n = len(A)
for i in range(n - 1, 0, -1): # 외부 루프 : n-1 ~ 1
bChanged = False
for j in range(i): # 내부 루프 : 0 ~ i-1
if A[j] > A[j + 1]: # 순서가 맞지 않으면
A[j], A[j + 1] = A[j + 1], A[j] # 교환
bChanged = True # 교환이 발생했음
if not bChanged: # 교환이 없으면 종료
break
printStep(A, n - i) # 중간 과정 출력용 문장
def printStep(arr, val):
print(" Scan %2d 완료 = " % val, end="")
print(arr)data = [5, 3, 8, 4, 9, 1, 6, 2, 7]
print("Original :", data)
bubble_sort(data)
print("insertion :", data)
--------------------------------------------
Original : [5, 3, 8, 4, 9, 1, 6, 2, 7]
Scan 1 완료 = [3, 5, 4, 8, 1, 6, 2, 7, 9]
Scan 2 완료 = [3, 4, 5, 1, 6, 2, 7, 8, 9]
Scan 3 완료 = [3, 4, 1, 5, 2, 6, 7, 8, 9]
Scan 4 완료 = [3, 1, 4, 2, 5, 6, 7, 8, 9]
Scan 5 완료 = [1, 3, 2, 4, 5, 6, 7, 8, 9]
Scan 6 완료 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
insertion : [1, 2, 3, 4, 5, 6, 7, 8, 9]
* 정렬 응용 : 집합 다시보기
- 집합의 원소들이 정렬되어 있으면 집합의 비교나 합집합, 차집합, 교집합 등을 훨씬 효율적으로 구현할 수 있다. 그래서 정렬을 이용해서 집합의 원소들을 항상 정렬된 순으로 저장하려고 한다.
- 집합의 삽입연산 등의 ADT(추상 데이터 타입)을 변경해야한다.
더보기
class Set:
def __init__( self ):
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 contains(self, item) :
for i in range(len(self.items)):
if self.items[i] == item :
return True
return False
def insert(self, elem) :
if elem not in self.items :
self.items.append(elem)
def delete(self, elem) :
if elem in self.items :
self.items.remove(elem)
def union( self, setB ):
setC = Set()
setC.items = list(self.items)
for elem in setB.items :
if elem not in self.items :
setC.items.append(elem)
return setC
def intersect( self, setB ):
setC = Set()
for elem in setB.items :
if elem in self.items :
setC.items.append(elem)
return setC
def difference( self, setB ):
setC = Set()
for elem in self.items:
if elem not in setB.items:
setC.items.append(elem)
return setC
* Set_insert : 삽입 연산
def insert(self, elem) : # 삽입연산
if elem in self.items : return # 이미 있는 경우
for idx in range(len(self.items)) :
if elem < self.items[idx] : # 삽입할 위치 idx를 찾음
self.items.insert(idx, elem)
return
self.items.append(elem)
* Set_ _eq_ _() : 비교 연산
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정렬되지 않은 상태에서 두 집합이 같은지 비교하려면 O(n^2) 알고리즘이 된다. 배열이 정렬되었다면 원소의 개수를 확인하고 순서대로 원소를 비교하면 된다. 정렬되어 있으면 시간 복잡도는 O(n)이 된다.
_ _eq_ _() 파이썬에서 미리 정의된 특별한 메소드로 ==연산자에 대한 연산자 중복 함수이다. Set 클래스에서 이 메소드를 구현하면 두 Set 객체 A와 B를 A==B와 같이 ==연산자를 이용해 비교할 수 있다. 산술 연산자(+,-,/,*)나 비교 연산자 등을 포함한 다양한 연산자 중복 메소드가 정의되어 있는데, 이들은 모두 _ _로 시작하여 _ _로 끝나는 이름을 갖는다.
* Set_insert : 삽입 연산
- 두 집합의 원소들이 크기순으로 정렬되어 있으므로, 가장 작은 원소들부터 비교하여 더 작은 원소를 새로운 집합에 넣고 그 집합의 인덱스를 증가시킨다.
- 만약 두 집합의 현재 원소가 같으면 하나만을 새 집합에 넣으면 된다. 인덱스는 모두 증가시킨다.
- 한쪽 집합이 모두 처리되면 나머지 집합의 남은 모든 원소를 순서대로 새 집합에 넣는다.
def union( self, setB ):
newSet = Set() # 반환할 합집합
a = 0 # 집합 self의 원소에 대한 인덱스
b = 0 # 집합 setB의 원소에 대한 인덱스
while a < len( self.items ) and b < len( setB.items ) :
valueA = self.items[a] # 집합 self의 현재 원소
valueB = setB.items[b] # 집합 setB의 현재 원소
if valueA < valueB :
newSet.items.append( valueA )
a += 1
elif valueA > valueB :
newSet.items.append( valueB )
b += 1
else :
newSet.items.append( valueA )
a += 1
b += 1
while a < len( self.items ):
newSet.items.append( self.items[a] )
a += 1
while b < len( setB.items) :
newSet.items.append( setB.items[b] )
b += 1
return newSet