1. 정렬 개요
정렬 : 데이터를 순서대로 재배열하는 것. 가장 기본적이고 중요한 알고리즘임. 비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있음. 오름차순과 내림차순이 있음
레코드 : 정렬시켜야 할 대상. 여러개의 필드로 이루어짐. 정렬의 기준이 되는 필드를 정렬 키라고 부름.
즉, 정렬이란 레코드들을 키(key)의 순서로 재배열하는 것.
정렬 장소에 따른 분류
- 내부 정렬 : 모든 데이터가 메인 메모리
- 외부 정렬 : 외부 기억 장치에 대부분의 레코드
단순하지만 효율성 낮음 : 삽입, 선택, 버블정렬
복잡하지만 효율성 높음 : 퀵, 힙, 병합, 기수정렬
2. 선택 정렬
선택 정렬 : 주어진 오른쪽 리스트에서 가장 작은 키(혹은 가장 큰 키)를 선택해 왼쪽으로 순서대로 옮겨 정렬해 나가는 방법.
def sort(self):
n = self.size
for i in range(n-1):
smallest = i
for j in range(i+1, n):
if num[j] < num[samllest]:
smallest = j
self.swap(i, smallest)
print(self.num)
아래는 선택 정렬을 구현한 코드
class SelectionSort:
def __init__(self, num):
self.num = num
self.size = len(num)
def __str__(self):
return "Selection Sort"
def swap(self, a, b):
self.num[a], self.num[b] = self.num[b], self.num[a]
def sort(self):
n = self.size # 전체 리스트 크기 저장
for i in range(n-1):
smallest = i # 현재 위치 i를 시작
for j in range(i+1, n): # i다음위치부터 끝까지 순회하며 최소값 찾기
if num[j] < num[smallest]:
smallest = j # 현재 찾은 값이 더 작으면 인덱스 갱신
self.swap(i, smallest) # 가장 작은 값과 현재 위치를 교환
print(self.num)
num = [31, 10, 9, 23, 49, 15, 11, 7]
s = SelectionSort(num)
print(s)
print(num)
print()
s.sort()
num = [9, 5, 2, 7, 4, 6, 3]
s = SelectionSort(num)
print(s)
print(num)
print()
s.sort()
위 코드 예제로 선택 정렬 이해하기
초기 [31, 10, 9, 23, 49, 15, 11, 7]
31부터 시작하면 됨. --> 왼쪽부터 오른쪽으로 쭉 비교하고 --> 7이랑 자리 교환
1회전 7, 10, 9, 23, 49, 15, 11, 31
이제 10에서부터 시작
2회전 7, 9, 10, 23, 49, 15, 11, 31
3회전 7, 9, 10, 11, 49, 15, 23, 31
4회전 7, 9, 10, 11, 15, 49, 23, 31
5회전 7, 9, 10, 11, 15, 23, 49, 31
6회전 7, 9, 10, 11, 15, 23, 31, 49
초기 [9, 5, 2, 7, 4, 6, 3]
1회전 2, 5, 9, 7, 4, 6, 3
2회전 2, 3, 9, 7, 4, 6, 5
3회전 2, 3, 4, 7, 9, 6, 5
4회전 2, 3, 4, 5, 9, 6, 7
5회전 2, 3, 4, 5, 6, 9, 7
6회전 2, 3, 4, 5, 6, 7, 9
3. 버블 정렬
- 인접한 2개의 키를 비교하여 순서대로 서로 교환함.
- 비교와 교환 과정을 반복해가며 리스트의 전체에 수행함(스캔).
- 한번의 스캔이 완료되면 리스트의 오른쪽 끝에 가장 큰 레코드로 정렬함.
- 끝으로 이동한 레코드를 제외하고 다시 스캔 반복
class BubbleSort:
def __init__(self, num):
self.num = num
self.size = len(num) # 리스트 길이 저장(정렬 횟수 계산용)
def __str__(self):
return "Bubble Sort"
def swap(self, a, b):
self.num[a], self.num[b] = self.num[b], self.num[a]
def sort(self):
n = self.size # 리스트 크기 가져옴
for i in range(n-1):
flag = 0 # 정렬이 이미 끝났는지 확인 위한 장치
for j in range(n-1-i):
if num[j] > num[j+1]: # 왼쪽 값이 크면 스왑해서 큰 값을 오른쪽으로 보냄
self.swap(j, j+1)
flag = 1
if flag == 0: break
print(self.num)
버블 정렬 이해하기 - 옆에 있는 두 값 비교해서 큰 값을 오른쪽으로 보내면 됨.
초기 [5, 1, 4, 2, 8]
5랑 1 -> 1이 작으니까 교환함 [1, 5, 4, 2, 8] 이런식으로 반복하면 5랑 8이 만남. 8이 더 크니까 교환없음.
그래서 [1, 4, 2, 5, 8]임. 따라서
1회전 1, 4, 2, 5, 8
2회전 1, 2, 4, 5, 8
초기 [31, 10, 9, 23, 49, 15, 11, 7]
1회전 10, 9, 23, 31, 15, 11, 7, 49]
2회전 9, 10, 23, 15, 11, 7, 31, 49
3회전 9, 10, 15, 11, 7, 23, 31, 49
4회전 9, 10, 11, 7, 15, 23, 31, 49
5회전 9, 10, 7, 11, 15, 23, 31, 49
6회전 9, 7, 10, 11, 15, 23, 31 49
7회전 7, 9, 10, 11, 15, 23, 31, 49
초기 [9, 5, 2, 7, 4, 6, 3]
1회전 5, 2, 7, 4, 6, 3, 9
2회전 2, 5, 4, 6, 3, 7, 9
(2회전에서 2, 5, 7, 4, 6, 3, 9 인걸로 착각했는데 7 앞에서 멈추지 말고 9 직전까지 비교해야함.
오른쪽에 냅둔거 빼고 끝까지 비교하는게 버블정렬 핵심)
3회전 2, 4, 5, 3, 6, 7, 9
4회전 2, 4, 3, 5, 6, 7, 9
5회전 2, 3, 4, 5, 6, 7, 9
4. 삽입 정렬
정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복함.
즉 자기 위치를 찾아 '삽입'하면서 정렬하는 방식.
카드놀이할 때 손에 들고 있는 카드를 하나씩 정렬된 위치에 끼워넣는 것처럼 이해하면 됨.
배열을 왼->오 순서로 보면서 현재 원소를 그 앞쪽 정렬된 부분에 삽입. 왼쪽은 항상 정렬된 상태로 유지됨.
class InsertionSort:
def __init__(self, num):
self.num = num
self.size = len(num)
def __str__(self):
return "Insertion Sort"
def swap(self, a, b):
self.num[a], self.num[b] = self.num[b], self.num[a]
def sort(self):
n = self.size
for i in range(1, n): # 리스트의 두번째 원소부터 끝까지 반복.
# (예제 리스트에서 31은 정렬되어 있다고 간주하고 10이 들어갈 자리를 찾기 위해 31과 비교)
temp = self.num[i] # 현재 정렬하려는 값을 temp에 저장. (i=1 일때 temp=10)
j = i - 1 # 현재 temp를 비교할 대상의 인덱스. 바로 왼쪽 왼소부터 비교 시작.
while j >= 0 and self.num[j] > temp: # j가 리스트 범위 내 and 현재 비교 대상 값이 temp보다 크면
self.num[j+1] = self.num[j] # 오른쪽으로 복사해서 자리를 비움
j = j - 1 # 왼쪽으로 이동하면서 계속 비교
self.num[j+1] = temp # temp값을 알맞은 자리에 끼워 넣음.
print(self.num)
num = [31, 10, 9, 23, 49, 15, 11, 7]
s = InsertionSort(num)
print(s)
print(num)
print()
s.sort()
print()
초기 [31, 10, 9, 23, 49, 15, 11, 7]
1회전 10, 31, 9, 23, 49, 15, 11, 7
2회전 9, 10, 31, 23, 49, 15, 11, 7
3회전 9, 10, 23, 31, 49, 15, 11, 7
4회전 9, 10, 23, 31, 49, 15, 11, 7
5회전 9, 10, 15, 23, 31, 49, 11, 7
6회전 9, 10, 11, 15, 23, 31, 49, 7
7회전 7, 9, 10, 11, 15, 23, 31, 49
초기 [9, 5, 2, 7, 4, 6, 3]
1회전 5, 9, 2, 7, 4, 6, 3
2회전 2, 5, 9, 7, 4, 6, 3
3회전 2, 5, 7, 9, 4, 6, 3
4회전 2, 4, 5, 7, 9, 6, 3
5회전 2, 4, 5, 6, 7, 9, 3
6회전 2, 3, 4, 5, 6, 7, 9
5. 퀵 정렬
- 기준(피봇)을 정함.
- 기준이 되는 레코드의 키와 나머지 레코드들의 키를 비교
- 기준보다 작으면 피봇의 왼쪽에, 크면 오른쪽에 위치시킴. partition()
- 피봇의 왼쪽 부분에는 피봇 보다 작은 키들로, 오른쪽 부분은 피봇보다 큰 키들로 재배치됨. (피봇은 정렬 완료 -> 위치 고정)
- 앞부분, 뒷부분에서 동일 작업을 반복. -> 피봇을 정함 -> 반복
class QuickSort:
def __init__(self, num):
self.num = num
self.size = len(num)
def __str__(self):
return "Quick Sort"
def swap(self, a, b):
self.num[a], self.num[b] = self.num[b], self.num[a]
def sort(self, left, right):
if left < right: # 정렬조건(개수비교)
i = left # 왼쪽부터 탐색할 인덱스 초기화
j = right + 1 # 오른쪽부터 탐색할 인덱스 초기화
pivot = num[left] # 피봇 값을 배열의 첫 번째 값으로 정함
while True:
while True:
i += 1 # i를 오른쪽으로 한칸씩 이동하면서
if i > right or num[i] >= pivot: break # 피봇보다 큰 값을 찾을 때까지 이동
while True:
j -= 1 # j를 왼쪽으로 한칸씩 이동하면서
if j < left or num[j] <= pivot: break # 피봇보다 작은 값을 찾을 때까지 이동
if i < j: # i가 j보다 왼쪽에 있으면
self.swap(i, j) # 두 값을 서로 교환
print(self.num)
else: break # i >=j 가 되면 교차한거니까 더이상 스왑할게 없음
self.swap(left, j) # 피봇을 제자리로 옮겨주는 작업
if left != j: print(self.num) # 실제로 자리 바뀌었을 때만 배열 상태 출력
self.sort(left, j-1) # 피봇 기준 왼쪽 구간을 다시 퀵 정렬, 재귀.
self.sort(j+1, right) # 피봇 기준 오른쪽 구간을 다시 퀵 정렬, 재귀.
퀵 정렬 연습 예제
초기 [26, 5, 37, 1, 61, 11, 59, 15, 48, 19] (left=0, right=9)
--> 26, 5, 19, 1, 61, 11, 59, 15, 48, 37
--> 26, 5, 19, 1, 15, 11, 59, 61, 48, 37
--> 11, 5, 19, 1, 15, 26, 59, 61, 48, 37 --> 왼쪽구간 정렬 : [11, 5, 19, 1, 15] (left=0, right=4, 피봇=11)
--> 11, 5, 1, 19, 15, 26, 59, 61, 48, 37
--> 1, 5, 11, 19, 15, 26, 59, 61, 48, 37 --> 왼쪽 재귀 : 오른쪽 [19, 15] 정렬 (left=3, right=4, 피봇=19)
--> 1, 5, 11, 15, 19, 26, 59, 61, 48, 37 --> 오른쪽구간 정렬 : [59, 61, 48, 37] (left=6, right=9, 피봇=59)
--> 1, 5, 11, 15, 19, 26, 59, 37, 48, 61
--> 1, 5, 11, 15, 19, 26, 48, 37, 59, 61
--> 1, 5, 11, 15, 19, 26, 37, 48, 59, 61
초기 [31, 10, 9, 23, 49, 15, 11, 7] (left=0, right=7)
--> 31, 10, 9, 23, 7, 15, 11, 49
--> 11, 10, 9, 23, 7, 15, 31, 49
--> 11, 10, 9, 7, 23, 15, 31, 49
--> 7, 10, 9, 11, 23, 15, 31, 49 --> 11 고정
--> 재귀들어감. 왼쪽 구간 : left=0, right=2, [7, 10, 9] --> 정렬 할 게 없음.
--> 오른쪽 구간 [10, 9] 정렬
--> 7, 9, 10, 11, 23, 15, 31, 49
--> 재귀들어감. 오른쪽 구간 : left=4, right=5, [23, 15]
--> 7, 9, 10, 11, 15, 23, 31, 49
초기 [43, 12, 56, 8, 39, 27, 61, 19, 33, 2, 48, 25, 7, 36, 15] (left=0, right=14)
--> 43, 12, 15, 8, 39, 27, 61, 19, 33, 2, 48, 25, 7, 36, 56
--> 43, 12, 15, 8, 39, 27, 36, 19, 33, 2, 48, 25, 7, 61, 56
--> 43, 12, 15, 8, 39, 27, 36, 19, 33, 2, 7, 25, 48, 61, 56
--> 25, 12, 15, 8, 39, 27, 36, 19, 33, 2, 7, 43, 48, 61, 56
--> 25, 12, 15, 8, 7, 27, 36, 19, 33, 2, 39, 43, 48, 61, 56
--> 25, 12, 15, 8, 7, 2, 36, 19, 33, 27, 39, 43, 48, 61, 56
--> 25, 12, 15, 8, 7, 2, 19, 36, 33, 27, 39, 43, 48, 61, 56
--> 19, 12, 15, 8, 7, 2, 25, 36, 33, 27, 39, 43, 48, 61, 56
--> 2, 12, 15, 8, 7, 19, 25, 36, 33, 27, 39, 43, 48, 61, 56 --> left=j 같음. 2 고정.
--> 2, 12, 7, 8, 15, 19, 25, 36, 33, 27, 39, 43, 48, 61, 56
--> 2, 8, 7, 12, 15, 19, 25, 36, 33, 27, 39, 43, 48, 61, 56
--> 2, 7, 8, 12, 15, 19, 25, 36, 33, 27, 39, 43, 48, 61, 56
--> 2, 7, 8, 12, 15, 19, 25, 27, 33, 36, 39, 43, 48, 61, 56
--> 2, 7, 8, 12, 15, 19, 25, 27, 33, 36, 39, 43, 48, 56, 61
6. 합병 정렬
- 정렬할 리스트를 두 부분으로 나눔 (n>1 일때)
- 한 부분은 ceil(n/2) 의 개수
- 나머지 부분은 floor(n/2) 의 개수의 리스트가 됨.
- 나누어진 두 부분에 대해 각각 정렬을 반복적으로 수행
- 정렬된 두 부분은 합병해 하나의 정렬된 리스트로 만듦.
- 정렬된 두 부분 A, B 리스트
- 가장 작은 항목들을 서로 비교해 가며, 더 작은 것을 우선적으로 C로 옮김
A = (2, 5, 6)
B = (1, 3, 8, 9, 10)
C = (1) -> (1, 2) -> (1, 2, 3) -> (1, 2, 3, 5) -> (1, 2, 3, 5, 6), 여기서 A가 빈 리스트됨.
두 리스트 중 어느 하나라도 빈 리스트가 되면 아직 남은 항목들은 그대로 C에 덧붙임.
- 합병에 걸리는 시간은 O(n), n=len(A)+len(B)
print("\n#\n5. 합병 정렬 구현과 실행 예")
class MergeSort:
def __init__(self, num):
self.num = num
self.size = len(num)
def __str__(self):
return "Merge Sort"
def swap(self, a, b):
self.num[a], self.num[b] = self.num[b], self.num[a]
def sort(self, left, right): # 재귀로 분할
if left < right: # 리스트가 최소 2개 이상일 때만 정렬 수행
mid = (left+right) // 2 # 리스트를 반으로 나눔
self.sort(left, mid) # 왼쪽 부분 재귀 호출
self.sort(mid+1, right) # 오른쪽 부분 재귀 호출
self.merge(left, mid, right) # 왼쪽과 오른쪽을 병합
print(self.num) # 병합 완료된 상태 출력
def merge(self, left, mid, right): # 병합 구현
pos = left # temp에 값을 넣기 시작할 위치
left_end = mid # 왼쪽 구간의 마지막 인덱스
right_start = mid + 1 # 오른쪽 구간의 시작 인덱스
n = right - left + 1 # 병합할 요소의 전체 개수
temp = [None]*self.size # 병합 결과를 담을 임시 리스트
# 두 리스트를 동시에 보면서 작은 값을 temp에 넣고 인덱스 이동
while left <= left_end and right_start <= right:
if self.num[left] <= self.num[right_start]:
temp[pos] = num[left]
pos = pos + 1
left = left + 1
else:
temp[pos] = num[right_start]
pos = pos + 1
right_start = right_start + 1
# 위에서 한쪽 리스트가 먼저 다 소진되면 남은 쪽을 그대로 이어 붙임.
while left <= left_end:
temp[pos] = num[left]
pos = pos + 1
left = left + 1
while right_start <= right:
temp[pos] = num[right_start]
pos = pos+1
right_start = right_start + 1
# 병합된 결과를 원래 배열에 덮어쓰기. 오른쪽에서 왼쪽으로 거꾸로 복사함.
for i in range(n):
self.num[right] = temp[right]
right = right - 1
초기 [31, 10, 9, 23, 49, 15, 11, 7]
--> 10, 31, 9, 23, 49, 15, 11, 7
--> 10, 31, 9, 23, 49, 15, 11, 7
--> 9, 10, 23, 31, 49, 15, 11, 7
--> 9, 10, 23, 31, 15, 49, 11, 7
--> 9, 10, 23, 31, 15, 49, 7, 11
--> 9, 10, 23, 31, 7, 11, 15, 49
--> 7, 9, 10, 11, 15, 23, 31, 49
초기 [9, 5, 2, 7, 4, 6, 3]
--> 5, 9, 2, 7, 4, 6, 3
--> 5, 9, 2, 7, 4, 6, 3
--> 2, 5, 7, 9, 4, 6, 3
--> 2, 5, 7, 9, 4, 6, 3
--> 2, 5, 7, 9, 3, 4, 6
--> 2, 3, 4, 5, 6, 7, 9
7. 정리
선택정렬 - 가장 작은 값과 위치 교환
버블정렬 - 인접한 값과 끝까지 비교하고 큰 값을 오른쪽 끝으로
삽입정렬 - 오른쪽 값과 비교하며 자리를 하나씩 바꿈. 카드놀이.
퀵 정렬 - 첫번째가 피봇. 왼쪽인덱스가 피봇보다 클 때까지, 오른쪽인덱스가 피봇보다 작을 때까지 반복 후 서로 교환. 인덱스 교차되면 오른쪽인덱스와 피봇을 교환하고 피봇은 고정. 피봇의 왼오 구간 재귀 반복.
합병정렬 - 다 나누고 왼쪽부터 합치고 오른쪽 합치고 왼오 합치기. 홀수일때 왼쪽이 더 많음.