Стандартные алгоритмы: поиск, линейный и бинарный поиск, сортировка, сортировка пузырьком, выбором и вставками

IRC-Mania Die Seite rund um Sicherheit und Programmierung

Internet, Sicherheit , Internet Relay Chat

Gesponsert

Поиск и сортировка входят в число самых фундаментальных операций при разработке ПО. В этой статье мы разберем пять ключевых алгоритмов: линейный поиск, бинарный поиск, сортировку пузырьком, сортировку выбором и сортировку вставками. Для каждого алгоритма я объясню, как он работает, его сложность в нотации Big-O и приведу примеры кода на Python.

Будь то дипломная работа, университет или любая другая IT-подготовка, вопросы о поиске и сортировке всегда где-то всплывают. Обычно это простые задачи вроде реализации сортировки пузырьком или работы с массивами.

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

Время это деньги, и здесь начинается первая дилемма программиста. Когда алгоритм хорош, а когда он совершенно непригоден?

Чем больше объемы данных, тем критичнее правильный выбор подхода. На малых объемах разница между ожиданием 0,2 или 0,5 секунды не заметна, но на больших объемах речь уже идет о секундах и даже минутах.

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

Что означают O(1), O(n), O(log n) и O(n²)?

Прежде чем разбирать отдельные алгоритмы, нужно понять, как мы описываем их скорость. Для этого используется нотация Big-O. Она показывает не количество миллисекунд, которое потребуется алгоритму, а то, как время выполнения растет с увеличением объема данных.

Вот основные классы сложности:

• O(1) – константная: время выполнения не зависит от размера данных. Пример: доступ к элементу массива по индексу.
• O(log n) – логарифмическая: время растет очень медленно. Бинарный поиск делит диапазон пополам на каждом шаге, поэтому его сложность O(log n).
• O(n) – линейная: время растет пропорционально объему данных. На 1000 элементах алгоритм работает примерно в два раза дольше, чем на 500.
• O(n²) – квадратичная: время растет очень быстро. При удвоении данных требуется примерно в четыре раза больше времени. Многие простые алгоритмы сортировки имеют такую сложность.

Big-O нотация описывает наихудший сценарий, что помогает оценить максимально возможное время выполнения алгоритма.

Более подробное объяснение найдешь в статье Big-O нотация: сложность алгоритмов и эффективность O(1), O(n), O(log n) и в введении к анализу сложности, Big-O, алгоритмам поиска и сортировки.

Для дальнейшего разбора достаточно помнить нашу оценку и различать, когда сложность “ХОРОШАЯ” или “МЕНЕЕ ХОРОШАЯ”.

Линейный поиск

Линейный поиск проходит по элементам списка один за другим, пока не найдет нужный элемент или не достигнет конца. Этот метод работает как с отсортированными, так и с неотсортированными данными.

Ты начинаешь с начала списка и идешь до конца. Может повезти и нужный элемент будет в начале, а может оказаться в самом конце.

def lineare_suche(liste, ziel):
    for index, wert in enumerate(liste):
        if wert == ziel:
            return index
    return -1

• Best Case: O(1) (элемент в начале)
• Worst Case: O(n) (элемент в конце)
• Average Case: O(n)

Линейный поиск прост в реализации, но медленен на больших объемах.

Бинарный поиск

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

def binaere_suche(liste, ziel):
    links = 0
    rechts = len(liste) - 1

    while links <= rechts:
        mitte = (links + rechts) // 2
        if liste[mitte] == ziel:
            return mitte
        if liste[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte - 1

    return -1

• Best Case: O(1)
• Worst Case: O(log n)
• Average Case: O(log n)

На миллионе элементов бинарный поиск в наихудшем случае выполнит всего около 20 сравнений.

А сколько нужно линейному поиску? ;)

Сортировка пузырьком

Сортировка пузырьком повторяющимся образом сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке. Большие значения постепенно “всплывают” вверх.

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

def bubblesort(liste):
    n = len(liste)
    while True:
        vertauscht = False
        for i in range(n - 1):
            if liste[i] > liste[i + 1]:
                liste[i], liste[i + 1] = liste[i + 1], liste[i]
                vertauscht = True
        n -= 1
        if not vertauscht:
            break
    return liste

• Best Case: O(n)
• Worst Case: O(n²)
• Average Case: O(n²)

Сортировка пузырьком интуитивна для понимания, но неэффективна на больших объемах.

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

Сортировка выбором на каждом проходе находит минимальный элемент в неотсортированной части и добавляет его в конец отсортированной части.

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

• Best Case: O(n²)
• Worst Case: O(n²)
• Average Case: O(n²)

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

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

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

def insertion_sort(liste):
    for i in range(1, len(liste)):
        aktuelles = liste[i]
        j = i - 1
        while j >= 0 and liste[j] > aktuelles:
            liste[j + 1] = liste[j]
            j -= 1
        liste[j + 1] = aktuelles
    return liste

• Best Case: O(n)
• Worst Case: O(n²)
• Average Case: O(n²)

Сортировка вставками особенно эффективна, когда массив уже почти отсортирован.

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

Когда какой алгоритм использовать?

Для поиска:

• Линейный поиск используешь на несортированных данных.
• Бинарный поиск используешь на отсортированных данных.

Для сортировки:

• Bubblesort пригоден только для обучения.
• Selection Sort прост, но медлителен.
• Insertion Sort хорош для небольших или почти отсортированных наборов данных.
• На больших объёмах данных лучше применять Quicksort, Mergesort или Heapsort.

Линейный поиск, бинарный поиск, Bubblesort, Selection Sort и Insertion Sort образуют фундамент понимания алгоритмов и структур данных. Они просты, полезны для обучения и хорошо демонстрируют, как Big-O описывает время выполнения. На практике для больших объёмов данных используют более быстрые алгоритмы, но знание этих пяти стандартных алгоритмов необходимо каждому разработчику.

Premium VPS Hosting

Schnelle und sichere VPS Server

Gesponsert

Рекомендации по книгам об алгоритмах и структурах данных

Если хочешь подробнее изучить алгоритмы и структуры данных, рекомендуем следующие книги:

FAQ: стандартные алгоритмы, поиск и сортировка