버블 정렬
- 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그 다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복한다.
- 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간이 필요하지 않고 (제자리 정렬), 중복된 값을 입력 순서와 동일하게 정렬한다. (안정 정렬)
- 시간 복잡도는 최악, 최선, 평균 모두 O(n^2)으로 비효율적이며, 정렬되지 않은 원소가 정렬됐을 때의 자리로 가기 위해서 스왑 연산이 많이 일어난다.
알고리즘
def bubble_sort(arr):
for i in range(len(arr) - 1, 0, -1):
for j in range(i):
if arr[j] > arr[j - 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
조금 더 개선된 방법
def improved_bubble_sort(arr):
end = len(arr) - 1
while end > 0:
last_swap = 0
for i in range(end):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
last_swap = i
end = last_swap
선택 정렬
- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
- 시간 복잡도는 O(n^2)으로 정렬을 위한 비교 횟수는 많지만, 버블 정렬에 비해 실제로 교환하는 횟수가 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적이다.
- 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간이 필요하지 않고 (제자리 정렬), 중복된 값의 입력 순서가 정렬 후에 유지되지 않는다. (불안정 정렬)
알고리즘
def selection_sort(arr):
for i in range(len(arr) - 1):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[min_idx], arr[i] = arr[i], arr[min_idx]
삽입 정렬
- 두 번째 원소부터 시작해서 앞에 있는 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘
- 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적이다.
- 이미 정렬되어 있을 때는 O(n)의 시간 복잡도를 갖지만, 역순으로 정렬된 경우(최악의 경우) 시간 복잡도는 O(n^2)
- 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간이 필요하지 않고 (제자리 정렬), 중복된 값을 입력 순서와 동일하게 정렬한다. (안정 정렬)
- 버블 정렬이나 선택 정렬에 비해 상대적으로 빠르지만, 배열의 길이가 길어질수록 비효율적이다.
알고리즘
def insertion_sort(arr):
for end in range(1, len(arr)):
for i in range(end, 0, -1):
if arr[i - 1] > arr[i]:
arr[i - 1], arr[i] = arr[i], arr[i - 1]
조금 더 개선된 방법
def improved_insertion_sort(arr):
for end in range(1, len(arr)):
to_insert = arr[end]
i = end
while i > 0 and arr[i - 1] > to_insert:
arr[i] = arr[i - 1]
i -= 1
arr[i] = to_insert
'Python > Algorithm' 카테고리의 다른 글
투 포인터와 슬라이딩 윈도우 (0) | 2022.03.04 |
---|---|
그래프 관련 알고리즘 (0) | 2022.03.01 |
트라이 (0) | 2022.02.27 |
힙과 우선순위 큐 (0) | 2022.02.27 |
트리의 종류와 트리 순회 (0) | 2022.02.26 |