6 алгоритмов сортировки в гифках

Сортировка – важный аспект программирования. Отсортированные данные позволяют быстрее и эффективнее работать с данными.

Для описания эффективности алгоритма мы использовали два основных критерия: расход памяти и асимптотическую временную сложность (О-нотация).

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

Bubble Sort

Сортировка пузырьком считается учебной и самой легкой в понимании. В её основе лежит поочередное сравнение соседних элементов. Если они стоят в неверном порядке, их меняют местами. Так, наибольший элемент “всплывает” наверх с каждым проходом.

Это самый медленный из алгоритмов с квадратичной скоростью O(n 2 ). Однако он самый легкий в реализации и не использует много памяти.

Insertion Sort

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

Принцип прост. Все элементы просматриваются по очереди. Просмотренные элементы считаются отсортированными и каждый новый ставится на нужное место в ранее упорядоченной последовательности.

Shell Sort

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

Quick Sort

Быстрая сортировка или сортировка Хоара является одной из самых эффективных: на случайных данных достигает производительности O(n log(n)). Однако алгоритм является рекурсивным, поэтому использует много дополнительной памяти.

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

Merge Sort

Сортировка слиянием похожа по принципу на быструю и тоже является рекурсивной. Скорость алгоритма O(n log(n)) и требует дополнительной памяти в размере исходной последовательности.

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

HeapSort

Пирамидальная сортировка или сортировка кучей тоже имеет асимптотическую сложность O(n log(n)), но на практике оказывается медленнее предыдущих двух и применяется достаточно редко, хоть и не требует дополнительного выделения памяти.

Алгоритм интересен своим подходом. Принцип похож на сортировку вставками. Только мы не ищем место элемента в массиве, а просеиваем его в двоичную кучу (Heap).

Чтобы понять, почему это ускоряет процесс с n до log(n), давайте разберем, что это за структура данных. По сути, куча – бинарное дерево, которое удовлетворяет дополнительным условиям:

Вы пропустили

AEGIS Algorithms Android Angular Apache Airflow Apache Druid Apache Flink Apache Spark API API Canvas AppSec Architecture Artificial Intelligence Astro Authentication Authorization AutoGPT AWS AWS Aurora AWS Boto3 AWS EC2 AWS Lambda Azure Babylon.js Backend bash Beautiful Soup Bento UI Big Data Binary Tree Browser API Bun Career Cassandra Charts ChatGPT Chrome Extension Clean Code CLI ClickHouse Coding Codux Combine Compose Computer Context Fusion Copilot Cosmo Route CProgramming cron Cryptography CSS CTF Cypress DALL-E Data Analysis Data science Database dbt dbt Cloud deno Design Design Patterns Detekt Development Distributed Systems Django Docker Docker Hub Drizzle DRY DuckDB Express FastAPI Flask Flutter For Beginners Front End Development Game Development GCN GCP Geospatial Git GitHub Actions GitHub Pages Gitlab GMS GoFr Golang Google Google Sheets Google Wire GPT-3 GPT3 Gradio Gradle Grafana Graphic Design GraphQL gRPC Guidance HMS Hotwire HTML Huawei HuggingFace IndexedDB InfoSec Interview iOS Jackknife Java JavaScript Jetpack Compose JSON Kafka Kotlin Kubernetes LangChain Laravel Linux LlaMA LLM localStorage Logging Machine Learning Magento Math Mermaid Micro Frontends Mobile Mobile App Development mondayDB MongoDB Mongoose MySQL Naming NestJS NET NetMock Networks NextJS NLP Node.js Nodejs NoSQL NPM OOP OpenAI OTP Pandas PDF PHP Playwright Plotly Polars PostgreSQL Prefect Productivity Programming Prometheus Puppeteer Pushover Python Pytorch Quarkus Rabbitmq RAG Ramda Raspberry Pi React React Native Reactor Redis REST API Revolut Riverpod RProgramming Ruby Ruby on Rails Rust Scalene SCDB ScyllaDB Selenium Servers Sklearn SLO SnowFlake Snowkase Software Architecture Software Development Solara Solid Spring Boot SQL SQLite Streamlit SudoLang Supabase Swift SwiftUI Tailwind CSS Taipy Terraform Testing Transformers TURN TypeScript Ubuntu UI Design Unix UX UX Design Vim Vite VSCode Vue Web Architecture Web Components Web Development Web Frameworks Web Scraping Web-разработка Webassembly Websocket Whisper Widgets WordPress YAML YouTube Zed Наука о данных Разное Тренды

Современный подход к разработке с использованием Next.js