※
안정 정렬
중복된 값을 입력 순서와 동일하게 정렬
(버블, 삽입, 병합)
불안정 정렬
중복된 값이 기존 순서가 유지되지 않는 정렬
(선택, 퀵, 힙)
버블, 삽입, 선택, 퀵, 힙 정렬은 제자리 정렬
(입력 배열 이외의 다른 추가 메모리를 요구하지 않는 방법)
버블 정렬
- 정렬 방법 중 가장 단순한 방법
- 시간이 많이 걸려서 자주 사용하진 않는다.
- 이웃한 두 아이템을 비교하여 정렬하는 것을 처음부터 마지막까지 반복
- 0번 인덱스부터 시작
코드
# 버블 정렬
def bubble_sort(numbers):
for i in range(len(numbers) - 1):
for j in range(len(numbers) - i - 1):
if numbers[j] > numbers[j + 1]:
numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
print(numbers) # 정렬되는 과정
numbers = [5, 7, 3, 8, 1, 4, 6, 2]
bubble_sort(numbers)
print(numbers)
"""
[5, 3, 7, 1, 4, 6, 2, 8]
[3, 5, 1, 4, 6, 2, 7, 8]
[3, 1, 4, 5, 2, 6, 7, 8]
[1, 3, 4, 2, 5, 6, 7, 8]
[1, 3, 2, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
"""선택 정렬
- 가장 작은 값을 가지는 데이터를 리스트에 앞에 위치시키는 정렬 방법
- 자리를 선택하고 그 자리에 들어갈 값을 찾는 방법
- 0번 인덱스부터 시작
코드
# 선택 정렬
def select_sort(numbers):
for i in range(len(numbers)):
min_num = i
for j in range(i + 1, len(numbers)):
if numbers[j] < numbers[min_num]:
min_num = j
numbers[i], numbers[min_num] = numbers[min_num], numbers[i]
print(numbers)
numbers = [5, 7, 3, 8, 1, 4, 6, 2]
select_sort(numbers)
print(numbers)
"""
[1, 7, 3, 8, 5, 4, 6, 2]
[1, 2, 3, 8, 5, 4, 6, 7]
[1, 2, 3, 8, 5, 4, 6, 7]
[1, 2, 3, 4, 5, 8, 6, 7]
[1, 2, 3, 4, 5, 8, 6, 7]
[1, 2, 3, 4, 5, 6, 8, 7]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
"""삽입 정렬
- 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 방법
- 배열의 뒷 쪽부터 정렬하는 방법
- 1번 인덱스부터 시작
코드
# 삽입 정렬
def insert_sort(numbers):
for i in range(1, len(numbers)):
while i - 1 >= 0:
if numbers[i - 1] > numbers[i]:
numbers[i - 1], numbers[i] = numbers[i], numbers[i - 1]
i -= 1
print(numbers)
numbers = [5, 7, 3, 8, 1, 4, 6, 2]
insert_sort(numbers)
print(numbers)
"""
[5, 7, 3, 8, 1, 4, 6, 2]
[3, 5, 7, 8, 1, 4, 6, 2]
[3, 5, 7, 8, 1, 4, 6, 2]
[1, 3, 5, 7, 8, 4, 6, 2]
[1, 3, 4, 5, 7, 8, 6, 2]
[1, 3, 4, 5, 6, 7, 8, 2]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
"""→ 속도는 삽입, 선택, 버블 정렬 순으로 빠르지만 시간복잡도는 모두 O(n^2)
→ 삽입 정렬은 제일 빠를 최선의 경우에선 O(n)
합병 정렬
- 분할 정복과 재귀를 사용한 정렬 방법
- 배열의 원소가 하나만 남을 때까지 분할
- 분할된 배열을 다시 합칠 때 정렬을 통한 재배열
- 시간복잡도: O(nlogn)
코드
# 합병 정렬
def merge_sort(numbers):
if len(numbers) == 1:
return numbers
mid = len(numbers) // 2
left = merge_sort(numbers[:mid])
right = merge_sort(numbers[mid:])
print(left, right)
return merge(left, right)
def merge(left, right):
sort_numbers = []
l_index = r_index = 0
while l_index < len(left) and r_index < len(right):
if left[l_index] < right[r_index]:
sort_numbers.append(left[l_index])
l_index += 1
else:
sort_numbers.append(right[r_index])
r_index += 1
sort_numbers += left[l_index:] + right[r_index:]
return sort_numbers
numbers = [5, 7, 3, 8, 1, 4, 6, 2]
print(merge_sort(numbers))
"""
[5] [7]
[3] [8]
[5, 7] [3, 8]
[1] [4]
[6] [2]
[1, 4] [2, 6]
[3, 5, 7, 8] [1, 2, 4, 6]
[1, 2, 3, 4, 5, 6, 7, 8]
"""