정렬
=> 키를 항목의 대소 관계에 따라 데이터 집합을 일정한 순서 늘어놓는 작업
=> 내부정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용
외부정렬 : 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용
=> 정렬 알고리즘의 핵심은 교환 , 선택 , 삽입
1. 버블 정렬
이웃한 두원소의 대소를 비교, 교환을 반복 => 단순 교환 정렬
ex) bubble_sort()
def bubble_sort(arr):
n = len(arr)
# 배열의 모든 요소에 대해 반복
for i in range(n):
# 각 반복마다 배열의 마지막 요소는 정렬이 완료되므로 제외
for j in range(n-i-1):
# 현재 요소와 그 다음 요소를 비교하고, 순서가 잘못되어 있다면 서로 교환
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# 비교, 교환하는 과정을 패스라고 한다
# 예시
arr = [5, 2, 9, 1, 5, 6]
bubble_sort(arr)
print(arr) # Output: [1, 2, 5, 5, 6, 9]
인접한 두 원소를 비교하면서 정렬 수행 <= 간단하지만 비효율적인 정렬 알고리즘2. 단순 선택 정렬
ex) selection_sort()
def selection_sort(arr):
n = len(arr)
# 배열의 모든 요소에 대해 반복
for i in range(n):
# i번째 위치부터 마지막 위치까지 중에서 가장 작은 값을 찾아서 i번째 위치와 교환
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
# 예시
arr = [5, 2, 9, 1, 5, 6]
selection_sort(arr)
print(arr) # Output: [1, 2, 5, 5, 6, 9]
주어진 배열의 최소값을 선택하여 맨 앞의 위치와 교환하고 다음으로 작은 값을 선택하여 두 번쨰 위치와 교환하는 방식의 정렬3. 단순 삽입 정렬
ex) insertion_sort()
def insertion_sort(arr):
n = len(arr)
# 배열의 모든 요소에 대해 반복
for i in range(1, n):
# i번째 위치의 요소를 적절한 위치에 삽입
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
# 예시
arr = [5, 2, 9, 1, 5, 6]
insertion_sort(arr)
print(arr) # Output: [1, 2, 5, 5, 6, 9]
각 요소를 적절한 위치에 삽입하여 정렬 하는 알고리즘3-1. 이산 삽입 정렬 <= bisect.insort()
ex) discrete_insertion_sort()
def discrete_insertion_sort(arr):
n = len(arr)
# 배열의 모든 요소에 대해 반복
for i in range(1, n):
# i번째 위치의 요소를 적절한 위치에 삽입
key = arr[i]
j = bisect_left(arr[:i], key)
arr[j+1:i+1] = arr[j:i]
arr[j] = key
# 예시
from bisect import bisect_left
arr = [5, 2, 9, 1, 5, 6]
discrete_insertion_sort(arr)
print(arr) # Output: [1, 2, 5, 5, 6, 9]
단순 삽입 정렬과 유사하지만, 이전의 삽입된 요소들과 비교하여 적절한 위치를 찾아 삽입하는 방식으로 정렬을 수행하는 알고리즘, 정렬이 완료될 떄까지 맨번 배열의 모든 요소를 비교하는 단순 삽입 정렬과 달리, 이전의 요소들만을 비교하여 적절한 위치를 찾으므로 더 효율적인 알고리즘이 될 수 있다.
bisect.insort()
=> 'bisect' 모듈에서 제공하는 함수
리스트를 이진 검색하여 새로운 요소를 정렬된 순서로 삽입하는 기능을 제공
정렬된 리스트, 삽입하려는 요소를 인수로 받아 이진 검색 알고리즘 이용하여 리스트에서 삽입 위치를 찾은 후
'list.insert()' 메서드를 이용해 해당 위치에 삽입4. 셸 정렬
ex) shell_sort()
def shell_sort(arr):
n = len(arr)
gap = n // 2
# 간격(gap)을 점점 줄여가며 삽입 정렬 수행
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
# 삽입 정렬 수행
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap //= 2
# 예시
arr = [5, 2, 9, 1, 5, 6]
shell_sort(arr)
print(arr) # Output: [1, 2, 5, 5, 6, 9]
삽입 정렬을 보완, 정렬할 배열을 일정한 간격을 나누어 각각을 삽입 정렬한 후, 간격을 줄여가며 다시 삽입정렬을 반복하는 알고리즘5. 퀵 정렬
ex) quick_sort()
def quick_sort(arr, left, right):
if left >= right:
return
pivot = arr[(left + right) // 2] # 피벗은 중간값으로 선택
i, j = left, right
while i <= j:
# 피벗보다 큰 값을 찾을 때까지 i를 증가
while arr[i] < pivot:
i += 1
# 피벗보다 작은 값을 찾을 때까지 j를 감소
while arr[j] > pivot:
j -= 1
# i와 j의 위치를 바꾸고, i와 j를 각각 한 칸씩 이동
if i <= j:
arr[i], arr[j] = arr[j], arr[i]
i += 1
j -= 1
# 재귀 호출로 퀵 정렬을 수행
quick_sort(arr, left, j)
quick_sort(arr, i, right)
# 예시
arr = [5, 2, 9, 1, 5, 6]
quick_sort(arr, 0, len(arr)-1)
print(arr) # Output: [1, 2, 5, 5, 6, 9]
분할 정복 알고리즘의 하나, 평균적으로 가장 빠른 속도를 보이는 정렬 알고리즘 6. 병합 정렬
ex) merge_sort()
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 병합 과정
i = j = 0
merged = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged += left[i:]
merged += right[j:]
return merged
# 예시
arr = [5, 2, 9, 1, 5, 6]
sorted_arr = merge_sort(arr)
print(sorted_arr) # Output: [1, 2, 5, 5, 6, 9]
분할 정복 알고리즘의 하나, 리스트를 반씩 분할한 후, 각 부분 리스트를 정렬하여, 정렬된 부분 리스트를 병합하여 최종적을 정렬된 리스트를 얻는 알고리즘 7. 힙 정렬
ex) heap_sort()
import heapq
def heap_sort(arr):
h = []
# 리스트의 요소를 힙에 추가
for i in arr:
heapq.heappush(h, i)
# 힙에서 요소를 하나씩 꺼내서 정렬된 리스트에 추가
sorted_arr = []
while h:
sorted_arr.append(heapq.heappop(h))
return sorted_arr
# 예시
arr = [5, 2, 9, 1, 5, 6]
sorted_arr = heap_sort(arr)
print(sorted_arr) # Output: [1, 2, 5, 5, 6, 9]
최대 힙(Max heap) 또는 최소 힙(Min heap) 구조를 이용하여 정렬하는 알고리즘, 힙 구조는 부모 노드가 자식 노드보다 큰 값 또는 작은 값만을 가지는 이진 트리 구조8. 도수 정렬
ex) counting_sort()
def counting_sort(arr):
# 데이터의 범위를 구함
max_val = max(arr)
min_val = min(arr)
# 데이터가 등장한 횟수를 세는 리스트 생성
count = [0] * (max_val - min_val + 1)
# 데이터가 등장한 횟수를 count 리스트에 저장
for i in arr:
count[i - min_val] += 1
# count 리스트를 누적합으로 변경
for i in range(1, len(count)):
count[i] += count[i-1]
# 정렬된 결과를 저장할 리스트 생성
sorted_arr = [0] * len(arr)
# count 리스트를 이용하여 데이터를 정렬
for i in arr:
sorted_arr[count[i - min_val] - 1] = i
count[i - min_val] -= 1
return sorted_arr
# 예시
arr = [5, 2, 9, 1, 5, 6]
sorted_arr = counting_sort(arr)
print(sorted_arr) # Output: [1, 2, 5, 5, 6, 9]
도수 정렬(Counting sort)은 정렬할 데이터의 범위를 알고 있을 때, 각 데이터가 몇 번 등장했는지 세는 작업을 통해 정렬하는 알고리즘