[자료구조와 알고리즘] Algorithm Fundamental

선형 및 이진검색

▶ Linear Search ( 선형 검색 )

- 선형 검색은 기본적인 검색 알고리즘으로 한 번에 하나씩 모두 검색하는 것

▶ Binary Search ( 이진 검색 )

- 반복을 통해 숫자를 반으로 줄이면서 검색을 진행하기 때문에 속도가 더 빠름

-  이진 검색 방법은 데이터가 이미 정렬된 경우에만 작동

반복 정렬 ( Iteratibe Sorting )

▶ 선택 정렬 ( Selection Sort )

- 최소노드 선택 -> 왼쪽부터 비교 -> 교환

- 선택정렬은 가장 작은 노드 ( 최소값 ) 를 선택하고 왼쪽부터 정렬을 하기 위해 알맞은 위치와 교환하는 작업을 반복하는 것

- 시간 복잡도 : O(n^2)

def selection_sort(li):
    for i in range(len(li) - 1):
        min_idx = i
        for j in range(i + 1, len(li)):
            if li[j] < li[min_idx]:
                min_idx = j
        li[i], li[min_idx] = li[min_idx], li[i]

▶ 삽입 정렬 ( Insertion Sort )

- 삽입정렬은 아직 정렬되지 않은 특정 노드와 정렬된 노드들의 값을 비교하고 값이 더 큰 것의 인덱스보다 작은 인덱스에 삽입하며 정렬하는 알고리즘

- 최선의 시간복잡도 : O(n)

- 최악의 시간복잡도 : O(n^2)

def insertion_sort(li):
    for i in range(1, len(li)):
        while i > 0 and li[i -1] > li[i]:
            li[i - 1], li[i] = li[i], li[i - 1]
            i -= 1

▶ 버블 정렬 ( Bubble Sort )

- 서로 이웃한 두 원소의 크기를 비교한 결과에 따라 교환을 반복하는 알고리즘

- 시간복잡도 : O(n^2)

def bubble_sort(li):
    for i in range(len(li) - 1, 0, -1):
        swapped = False
        for j in range(i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                swapped = True
        if not swapped:
            break