대표적인 알고리즘(feat. 파이썬)

young.h·2022년 5월 5일
0

CS

목록 보기
2/6

알고리즘

빅오
안정/불안정 정렬

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)

0개의 댓글