8 лучших алгоритмов, которые должен знать каждый программист - UPROGER

В программировании алгоритм — это набор инструкций для решения конкретной проблемы или достижения конкретной задачи. Алгоритмы могут быть написаны на любом языке программирования и могут быть как простыми (последовательность основных операций), так и сложными (многоэтапный процесс, включающий различные структуры данных и логику). Основная цель алгоритма — принять входные данные, обработать их и предоставить ожидаемый результат. Алгоритмы можно классифицировать на основе временной и пространственной сложности, метода, используемого для решения проблемы, и типа решаемой проблемы. Примерами алгоритмов являются сортировка, поиск, обход графа, манипуляции со строками, математические операции и многое другое.

Алгоритмы, о которых мы будем говорить:

Алгоритмы сортировки. Сортировка является фундаментальной операцией в компьютерных науках, и для неё существует несколько эффективных алгоритмов, таких как быстрая сортировка, сортировка слиянием и пирамидальная сортировка.
Алгоритмы поиска. Поиск элемента в большом наборе данных — распространенная задача, и для неё существует несколько эффективных алгоритмов, таких как бинарный поиск и хеш-таблицы.
Алгоритмы графов. Алгоритмы графов используются для решения задач, связанных с графами, таких как поиск кратчайшего пути между двумя узлами или определение связности графа.
Динамическое программирование. Динамическое программирование — это метод решения проблем путем их разбиения на более мелкие подзадачи и сохранения решений этих подзадач во избежание избыточных вычислений.
Жадные алгоритмы. Жадные алгоритмы используются для решения задач оптимизации, делая локально оптимальный выбор на каждом шаге.
Разделяй и властвуй. Разделяй и властвуй — это парадигма разработки алгоритма, основанная на многоветвящейся рекурсии. Алгоритм «разделяй и властвуй» разбивает проблему на подзадачи того же или родственного типа, пока они не станут достаточно простыми, чтобы их можно было решить напрямую.
Поиск с возвратом. Это общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М.
Рандомизированный алгоритм: Рандомизированные алгоритмы используют случайность для решения проблемы. Это может быть полезно для решения проблем, которые не могут быть решены детерминистически, или для повышения средней сложности задачи.

Эти алгоритмы широко используются в различных приложениях, и программисту важно хорошо их понимать. Поэтому я постараюсь объяснить их.

1. Алгоритмы сортировки

Быстрая сортировка: Быстрая сортировка — это алгоритм «разделяй и властвуй», который выбирает «основной» элемент из массива и разбивает остальные элементы на два подмассива. Затем подмассивы сортируются рекурсивно.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

print(quicksort([3,6,8,10,1,2,1]))

Сортировка слиянием: Алгоритм сортировки слиянием — это алгоритм «разделяй и властвуй», который делит массив на две части, сортирует две половины, а затем снова объединяет их.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result
print(merge_sort([3,6,8,10,1,2,1]))

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

def heap_sort(arr):
    n = len(arr)
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
print(heap_sort([3,6,8,10,1,2,1]))

2. Алгоритмы поиска

Бинарный поиск: Бинарный поиск — это эффективный алгоритм поиска элемента в отсортированном списке. Он работает путем многократного деления пополам искомой части массива, пока не будет найдено искомое значение.

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
    while low <= high:
        mid = (high + low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1
print(binary_search([1,2,3,4,5,6,7], 4))

Хеш-таблицы: Хэш-таблица — это структура данных, которая сопоставляет ключи со значениями, используя хеш-функцию для вычисления индекса в массиве сегментов или слотов, из которых можно найти желаемое значение.

class HashTable:
    def __init__(self):
        self.size = 10
        self.keys = [None] * self.size
        self.values = [None] * self.size

  def put(self, key, data):
        index = self.hash_function(key)
        while self.keys[index] is not None:
            if self.keys[index] == key:
                self.values[index] = data  # update
                return
            index = (index + 1) % self.size
        self.keys[index] = key
        self.values[index] = data

    def get(self, key):
        index = self.hash_function(key)
        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.size
        return None

    def hash_function(self, key):
        sum = 0
        for pos in range(len(key)):
            sum = sum + ord(key[pos])
        return sum % self.size

t = HashTable()
t.put("apple", 10)
t.put("orange", 20)
t.put("banana", 30)
print(t.get("orange"))

3. Графический алгоритм

Алгоритм Дейкстры: Алгоритм Дейкстры — это алгоритм поиска кратчайшего пути между узлами в графе.

import heapq

def dijkstra(graph, start):
    heap = [(0, start)]
    visited = set()
    while heap:
        (cost, v) = heapq.heappop(heap)
        if v not in visited:
            visited.add(v)
            for u, c in graph[v].items():
                if u not in visited:
                    heapq.heappush(heap, (cost + c, u))
    return visited

graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'D': 4, 'E': 5},
    'C': {'F': 6},
    'D': {'G': 7},
    'E': {'G': 8, 'H': 9},
    'F': {'H': 10},
    'G': {},
    'H': {}
}
print(dijkstra(graph, 'A'))

4. Динамическое программирование

Последовательность Фибоначчи: Классическим примером проблемы, которую можно решить с помощью динамического программирования, является последовательность Фибоначчи.

def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
    
    
print(fibonacci(10))

5. Жадне алгоритмы

Кодирование Хаффмана: Кодирование Хаффмана — это алгоритм сжатия данных, который формулирует основную идею сжатия файлов.

from collections import Counter, namedtuple

def huffman_encoding(data):
    """
    Generates a Huffman encoded string of the input data
    """
    # Create a frequency counter for the data
    freq_counter = Counter(data)
    # Create a namedtuple for the Huffman tree nodes
    HuffmanNode = namedtuple("HuffmanNode", ["char", "freq"])
    # Create a priority queue for the Huffman tree
    priority_queue = PriorityQueue()
    # Add all characters to the priority queue
    for char, freq in freq_counter.items():
        priority_queue.put(HuffmanNode(char, freq))
    # Combine nodes until only the root node remains
    while priority_queue.qsize() > 1:
        left_node = priority_queue.get()
        right_node = priority_queue.get()
        combined_freq = left_node.freq + right_node.freq
        combined_node = HuffmanNode(None, combined_freq)
        priority_queue.put(combined_node)
    # Generate the Huffman code for each character
    huffman_code = {}
    generate_code(priority_queue.get(), "", huffman_code)
    # Encode the input data
    encoded_data = ""
    for char in data:
        encoded_data += huffman_code[char]
    return encoded_data, huffman_code
print(huffman_encoding("aaaaabbbcccc"))

6. Разделяй и властвуй

Сортировка слиянием: уже была объяснена выше…

7. Поиск с возвратом

Проблема N-ферзей. Проблема N-ферзей — это классическая проблема, которую можно решить с помощью поиска с возвратом. Цель состоит в том, чтобы разместить N-ферзей на шахматной доске NxN таким образом, чтобы ни один ферзь не мог атаковать другого ферзя.

def solveNQueens(n):
    def could_place(row, col):
        # check if a queen can be placed on board[row][col]
        # check if this row is not under attack from any previous queen in that column
        for i in range(row):
            if board[i] == col or abs(board[i] - col) == abs(i - row):
                return False
        return True

def backtrack(row=0, count=0):
        for col in range(n):
            if could_place(row, col):
                board[row] = col
                if row + 1 == n:
                    count += 1
                else:
                    count = backtrack(row + 1, count)
        return count
    board = [-1 for x in range(n)]
    return backtrack()
print(solveNQueens(4))

Этот алгоритм начинает размещать фигуры в первом ряду и для каждого размещённого ферзя проверяет, не атакован ли он каким-либо предыдущим ферзём. Если нет, он переходит к следующей строке и повторяет процесс. Если ферзь находится в позиции, где он подвергается атаке, алгоритм отступает и пробует другую позицию. Это продолжается до тех пор, пока все ферзи не будут размещены на доске, не атакуя друг друга.

8. Рандомизированный алгоритм

Рандомизированная быстрая сортировка: вариант алгоритма быстрой сортировки, в котором точка опоры выбирается случайным образом.

import random

def randomized_quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return randomized_quicksort(left) + middle + randomized_quicksort(right)

print(randomized_quicksort([3,6,8,10,1,2,1]))

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