1. 버블정렬
2. 삽입정렬
3. 병합정렬
4. 퀵정렬
5. 이진 검색
6. 해시
입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법으로
어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 표기하는 대표적인 방법입니다.
안정 정렬
중복된 값을 입력 순서와 동일하게 정렬
불안정 정렬
버블정렬, 안정
O(n^2)
배열 전체를 쭉 살펴보는 것을 n번 하며 순서가 잘못되어 있는 것을 발견하면 맞바꾼다.
def bubblesort(A):
for i in range(1, len(A)):
for j in range(0, len(A) - 1):
if A[j] > A[j+1]:
A[j], A[j+1] = A[j+1], A[j]
# 삽입 정렬
병합 정렬(분할 정복), 안정
O(n log n)
더 이상 쪼갤 수 없을 때 까지 분할한 후 분할이 끝나면 정렬
퀵 정렬, 불안정
최악의 경우: O(n^)
기준이 되는 피벗을 설정한 후 피벗보다 작으면 왼쪽, 크면 오른쪽으로 정렬
def quicksort(A, lo, hi):
def partition(lo, hi):
pivot = A[hi]
left = lo
for right in range(lo, hi):
if A[right] < pivot:
A[left], A[right] = A[right], A[left]
left += 1
A[left], A[hi] = A[hi], A[left]
return left
if lo < hi:
pivot = partition(lo, hi)
quicksort(A, lo, pivot - 1)
quicksort(A, pivot + 1, hi)