220920 링크드리스트 & 탐색 & 정렬

Linked List 링크드리스트

Node 노드 = Data 데이터 + Pointer 포인터

Pointer = 노드에서 다음 데이터를 가르킴

Head = 맨 앞 데이터

Tail = 맨 뒤 데이터

Next = None 은 다음 데이터가 없다는 뜻

---

Binary Search 이진탐색

#정렬 되어있을 때만 사용가능

시작점과 끝점의 중간점을 이용해서 타겟을 찾음

이상적으로는 데이터를 확인하는 연산 횟수를 매번 절반 줄어듬 -> 시간복잡도 O(logN)

def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2

    while current_min <= current_max:
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target: #up
            current_min = current_guess + 1
            print("up")
        else:
            current_max = current_guess - 1
            print("down")
        current_guess = (current_max + current_min) // 2

    return False

---

Sequential Search 순차탐색

하나씩 차례대로 확인하는 방법

시간복잡도  O(N)

def is_existing_target_number_sequential(target, array):
    for number in array:
        if target == number:
            return True
        
    return False

---

Bubble sort 버블정렬

인접한 두 원소를 검사

시간복잡도 O(N^2)

def bubble_sort(array):
    n = len(array)
    for i in range(n-1):
        for j in range(n-1-i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j+1] , array[j]
    return

---

Selection sort 선택정렬

최소값을 선택하는 과정을 반복

시간복잡도 O(N^2)

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

    return

---

Insertion sort 삽입정렬

작은 원소를 골라 앞쪽부터 정렬

자료배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하여 완성

한바퀴 돌때마다 완성된 배열 -> 새로운 요소가 들어오면 다시 배열 -> 완성

시간복잡도 O(N^2)

break가 있어서 시간복잡도가 최선의 경우에는 O(N)일 수도 있음

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j- 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1 ]
            else:
                break

    return