Сортировка бинарным деревом python

Sort Binary Tree by Levels using Python

Your task is to return the list with elements from tree sorted by levels, which means the root element goes first, then root children (from left to right) are second and third, and so on.

Return empty list if root is None .

Example 1 – following tree:

Should return following list:

Example 2 – following tree:

Should return following list:

Test cases#

Test.assert_equals(tree_by_levels(None), []) Test.assert_equals(tree_by_levels(Node(Node(None, Node(None, None, 4), 2), Node(Node(None, None, 5), Node(None, None, 6), 3), 1)), [1, 2, 3, 4, 5, 6]) 

The solution in Python#

# Our helper function # ..takes in `node` def tree_iterator(node: Node): # create a list to loop through nodes = [node] # loop while nodes: # yield from the list yield from nodes # internal loop for n in nodes[:]: # add to list if exists if n.left: nodes.append(n.left) if n.right: nodes.append(n.right) # remove from teh main list loop nodes.remove(n) # The primary function being called # ..passes in `node` def tree_by_levels(node): # return a list of values from our helper function # otherwise return `[]` if node is empty return [n.value for n in tree_iterator(node)] if node else [] 

def tree_by_levels(node): # create a return list, and a queue to loop p, q = [], [node] # loop while q: # take the first item from the queue v = q.pop(0) # if it is not empty if v is not None: # add it's value to the return list p.append(v.value) # add the left and right nodes to the queue q += [v.left,v.right] # return the final list, otherwise return [] is empty return p if not node is None else [] 

Top Related Articles

1. How to Split a String with Python
2. Converting to PigLatin with Python
3. Multiples of 3 and 5 with Python
4. Solving the “Catching Car Mileage Numbers” Challenge using Python
5. Counting smiley faces with Python
6. How to Convert Numeric Words into Numbers using Python
7. Solve The Triangle of Odd Numbers using Python
8. “Who likes it” code Challenge in Python
9. Python 4 New Features Planned
10. Custom RGB To Hex Conversion with Python

Источник

Binary Tree Sort Algorithm (Python)

A Binary Tree Sort is an algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order. Average Case Time Complexity : O(N log N) adding one element to a Binary Search Tree on average takes O(log N) time (height of a tree). Therefore, adding n elements will take O(N log N) time. Worst Case Time Complexity : O(N^2). The worst case can be improved by using a self-balancing binary search tree, which will take O(N log N) time to sort the array in worst case. Just for practicing, I’ve implemented the Binary Tree Sort algorithm, and if you’d like to review the code and provide any change/improvement recommendations, please do so, and I appreciate that.

Code

""" This module creates a Binary Sort Tree ascendingly using In Order Tree Traverse; Stable Sort; Worst Case Time Complexity (For if the tree would be a chain Tree): O(N^2) Average Case Time Complexity: O(N^Log N) Memory Complexity: Not in place O(N) """ import random from typing import List, TypeVar T = TypeVar('T') # Not sure how to design and handle the exceptions here yet class ExceptionHandling(Exception): pass class Node(object): def __init__(self, node_value: int) -> None: """ Initializes a node with three attributes; `node_value` (Node Value): Must be an integer/float; `right_child` (Right Child): Initializes to `None`; Its value must be larger than the Root Node; `left_child` (Left Child): Initializes to `None`; Its value must be smaller than the Root Node; """ self.node_value = node_value self.right_child = None self.left_child = None class BinarySearchTree(object): def __init__(self) -> None: """ Initializes the Root Node of the Binary Tree to None; """ self.root = None def is_empty(self) -> bool: """ Returns True if the tree doesn't have a node; """ return self.root == None def insert(self, new_node: int) -> None: """ Inserts an integer-value Node in the Tree; """ self.root = self._insert(self.root, new_node) def _insert(self, parent: int, new_node: int) -> int: """ Inserts an integer value in the left or right Node; Returns the parent Node; """ # If tree is empty if parent is None: parent = Node(new_node) # If the new Node value is smaller than its parent Node value elif new_node < parent.node_value: parent.left_child = self._insert(parent.left_child, new_node) # If the new Node value is bigger than its parent Node value else: parent.right_child = self._insert(parent.right_child, new_node) return parent def inorder(self) ->None: """ Calls the _inorder traversing method; """ self._inorder(self.root) def _inorder(self, parent: int) -> None: """ Traverses the tree inorder (Left Node, Root Node, Right Node) """ if parent is None: return self._inorder(parent.left_child) print(f'') self._inorder(parent.right_child) if __name__ == '__main__': tree = BinarySearchTree() for i in range(random.randint(20, 30)): tree.insert(random.uniform(-10, 10)) tree.inorder() 

Sources

Источник

Виды алгоритмов сортировки в Python

В одной из прошлых статей я рассматривал списки в Python, а также затронул их сортировку. Теперь давайте разберем эту тему более подробно: изучим виды алгоритмов сортировки и сравним их скорость на примере сортировки чисел в порядке возрастания.

Встроенные методы сортировки в Python

Стандартный метод сортировки списка по возрастанию – sort(). Пример использования:

nums = [54, 43, 3, 11, 0] nums.sort() print(nums) # Выведет [0, 3, 11, 43, 54]

Метод sorted() создает новый отсортированный список, не изменяя исходный. Пример использования:

nums = [54, 43, 3, 11, 0] nums2 = sorted(nums) print(nums, nums2) # Выведет [54, 43, 3, 11, 0] [0, 3, 11, 43, 54]

Если нам нужна сортировка от большего числа к меньшему, то установим флаг reverse=True. Примеры:

nums = [54, 43, 3, 11, 0] nums.sort(reverse=True) print(nums) # Выведет [54, 43, 11, 3, 0] nums = [54, 43, 3, 11, 0] nums2 = sorted(nums, reverse=True) print(nums, nums2) # Выведет [54, 43, 3, 11, 0] [54, 43, 11, 3, 0]

Но будет полезно знать и другие виды сортировки, так как не всегда встроенные методы будут подходить под все ваши задачи.

Пузырьковая сортировка

Алгоритм попарно сравнивает элементы списка, меняя их местами, если это требуется. Он не так эффективен, если нам нужно сделать только один обмен в списке, так как данный алгоритм при достижении конца списка будет повторять процесс заново. Чтобы алгоритм не выполнялся бесконечно, мы вводим переменную, которая поменяет свое значение с True на False, если после запуска алгоритма список не изменился.

Сравниваются первые два элемента. Если первый элемент больше, то они меняются местами. Далее происходит все то же самое, но со следующими элементами до последней пары элементов в списке.

Пример пузырьковой сортировки:

def bubble(list_nums): swap_bool = True while swap_bool: swap_bool = False for i in range(len(list_nums) - 1): if list_nums[i] > list_nums[i + 1]: list_nums[i], list_nums[i + 1] = list_nums[i + 1], list_nums[i] swap_bool = True nums = [54, 43, 3, 11, 0] bubble(nums) print(nums) # Выведет [0, 3, 11, 43, 54]

Сортировка вставками

Алгоритм делит список на две части, вставляя элементы на их правильные места во вторую часть списка, убирая их из первой.

Если второй элемент больше первого, то оставляем его на своем месте. Если он меньше, то вставляем его на второе место, оставив первый элемент на первом месте. Далее перемещаем большие элементы во второй части списка вверх, пока не встретим элемент меньше первого или не дойдем до конца списка.

Пример сортировки вставками:

def insertion(list_nums): for i in range(1, len(list_nums)): item = list_nums[i] i2 = i - 1 while i2 >= 0 and list_nums[i2] > item: list_nums[i2 + 1] = list_nums[i2] i2 -= 1 list_nums[i2 + 1] = item nums = [54, 43, 3, 11, 0] insertion(nums) print(nums) # Выведет [0, 3, 11, 43, 54]

Сортировка выборкой

Как и сортировка вставками, этот алгоритм в Python делит список на две части: основную и отсортированную. Наименьший элемент удаляется из основной части и переходит в отсортированную.

Саму отсортированную часть можно и не создавать, обычно используют крайнюю часть списка. И когда находится наименьший элемент списка, то переносим его на первое место, вставляя первый элемент на прошлое порядковое место наименьшего. Далее делаем все то же самое, но со следующим элементом, пока не достигнем конца списка.

Пример сортировки выборкой:

def selection(sort_nums): for i in range(len(sort_nums)): index = i for j in range(i + 1, len(sort_nums)): if sort_nums[j] < sort_nums[index]: index = j sort_nums[i], sort_nums[index] = sort_nums[index], sort_nums[i] nums = [54, 43, 3, 11, 0] selection(nums) print(nums) # Выведет [0, 3, 11, 43, 54]

Пирамидальная сортировка

Этот алгоритм, как и сортировки вставками или выборкой, делит список на две части. Алгоритм преобразует вторую часть списка в бинарное дерево для эффективного определения самого большого элемента.

Преобразуем список в бинарное дерево, где самый большой элемент является вершиной дерева, и помещаем этот элемент в конец списка. После перестраиваем дерево и помещаем новый наибольший элемент перед последним элементом в списке. Повторяем этот алгоритм, пока все вершины дерева не будут удалены.

Хоть алгоритм и кажется сложным, он значительно быстрее остальных, что особенно заметно при обработке больших списков.

Пример пирамидальной сортировки:

def heapify(sort_nums, heap_size, root): l = root left = (2 * root) + 1 right = (2 * root) + 2 if left < heap_size and sort_nums[left] >sort_nums[l]: l = left if right < heap_size and sort_nums[right] >sort_nums[l]: l = right if l != root: sort_nums[root], sort_nums[l] = sort_nums[l], sort_nums[root] heapify(sort_nums, heap_size, l) def heap(sort_nums): size = len(sort_nums) for i in range(size, -1, -1): heapify(sort_nums, size, i) for i in range(size - 1, 0, -1): sort_nums[i], sort_nums[0] = sort_nums[0], sort_nums[i] heapify(sort_nums, i, 0) nums = [54, 43, 3, 11, 0] heap(nums) print(nums) # Выведет [0, 3, 11, 43, 54]

Сортировка слиянием

Алгоритм разделяет список на две части, каждую из них он разделяет еще на две и так далее, пока не останутся отдельные единичные элементы. Далее соседние элементы сортируются парами. Затем эти пары объединяются и сортируются с другими парами, пока не обработаются все элементы в списке.

Пример сортировки слиянием:

def mergeSort(sort_nums): if len(sort_nums)>1: mid = len(sort_nums)//2 lefthalf = sort_nums[:mid] righthalf = sort_nums[mid:] mergeSort(lefthalf) mergeSort(righthalf) i=0 j=0 k=0 while i
Быстрая сортировка в Python
Один из самых популярных алгоритмов при сортировке списков. При правильном использовании он не требует много памяти и выполняется очень быстро.
Алгоритм разделяет список на две равные части, принимая псевдослучайный элемент и используя его в качестве опоры, то есть центра деления. Элементы, меньшие, чем опора, перемещаются влево от опоры, а элементы, размер которых больше опоры – вправо. Этот процесс повторяется для списка слева от опоры, а также для массива элементов справа от опоры, пока весь массив не будет отсортирован. Алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементу списка.
Пример быстрой сортировки:
def partition(sort_nums, begin, end): part = begin for i in range(begin+1, end+1): if sort_nums[i] = end: return part = partition(sort_nums, begin, end) quick(sort_nums, begin, part-1) quick(sort_nums, part+1, end) return quick(sort_nums, begin, end) nums = [54, 43, 3, 11, 0] quick_sort(nums) print(nums) # Выведет [0, 3, 11, 43, 54]
 
Скорость работы алгоритмов
 
Сортировка слиянием почти в два раза медленнее, чем быстрая сортировка. Сортировка выборкой выполняет больше сравнений, чем сортировка вставками, но выполняется немного быстрее.
 
Пузырьковая сортировка не подойдет для практического применения, так как она является самой медленной из всех. Но знать данный алгоритм будет полезно тем, кто хочет полностью изучить тему алгоритмов сортировки списков в Python.
 
Итог
 
Мы изучили виды сортировки списков в Python и сравнили их эффективность, а также рассмотрели встроенные методы. Надеюсь, данная статья была полезна для вас!
 
Источник