10.4 עצים ומיון פתרון

מיון - הבנת האלגוריתמים

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


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


def insertion_sort(arr: list) -> list:
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


data = [64, 34, 25, 12, 22, 11, 90]
print(selection_sort(data[:]))   # [11, 12, 22, 25, 34, 64, 90]
print(bubble_sort(data[:]))      # [11, 12, 22, 25, 34, 64, 90]
print(insertion_sort(data[:]))   # [11, 12, 22, 25, 34, 64, 90]

עץ בינארי - חיפוש

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root = None

    def insert(self, value) -> None:
        if not self.root:
            self.root = Node(value)
        else:
            self._insert(self.root, value)

    def _insert(self, node: Node, value) -> None:
        if value < node.data:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(node.right, value)

    def search(self, value) -> bool:
        return self._search(self.root, value)

    def _search(self, node: Node | None, value) -> bool:
        if node is None:
            return False
        if node.data == value:
            return True
        if value < node.data:
            return self._search(node.left, value)
        return self._search(node.right, value)

    def inorder(self) -> None:
        self._inorder(self.root)
        print()

    def _inorder(self, node: Node | None) -> None:
        if node:
            self._inorder(node.left)
            print(node.data, end=" ")
            self._inorder(node.right)


bst = BST()
for val in [5, 3, 7, 1, 4, 6, 8]:
    bst.insert(val)

bst.inorder()          # 1 3 4 5 6 7 8
print(bst.search(4))   # True
print(bst.search(9))   # False

שאלות Leetcode

אין פתרון קוד כאן - פתרו בעצמכם ב-Leetcode. אם תקועים, קראו את הפתרון הרשמי ואז כתבו אותו מחדש בלי להסתכל.