C++ 中的排序算法：详细指南

Here is the translated HTML article in English:

What is it and why? (a real-life analogy)

Imagine you are a librarian, and you have a huge stack of books that need to be arranged on shelves in alphabetical order. If there are only five books, you can do it in a couple of minutes. But what if there are a thousand books? Or ten thousand? You would spend hours moving books from place to place, getting confused and tired.

This is where sorting algorithms come to the rescue. They are a set of clear instructions that tell the computer: "Take this list of numbers (or names, or any other data) and arrange them in order — from smallest to largest or vice versa."

Sorting is not just about "arranging numbers nicely." It is the foundation for the operation of many other algorithms. For example:

• Search: If the array is sorted, finding the desired element can be hundreds of times faster (binary search).
• Databases: To show you products by price or date, the database sorts millions of records.
• Graphics: In games, objects are sorted to determine which one to draw first (closer to the camera).

💡 Remember: If you learn to understand sorting, you will understand how a computer "thinks" and makes decisions. This is the first step towards writing fast and efficient programs.

In this article, we will cover three of the most popular algorithms: Bubble Sort (the simplest to understand), Insertion Sort (like how we usually sort cards in our hand), and Quick Sort (the fastest and most popular).

Theory: how it works internally

Before writing code, let's understand how each algorithm "thinks." Each has its own strategy.

1. Bubble Sort

Analogy: Imagine you are standing in a line, and the tallest person needs to go to the end. You look at two neighbors on the left. If the left one is taller than the right one, you swap them. You go through the entire line over and over again until the tallest one "bubbles up" to the end, like a bubble in soda.

How it works:

1. Take the first element of the array.
2. Compare it with the second. If the first is greater than the second, swap them.
3. Move to the second element, compare it with the third. And so on until the end of the array.
4. After the first pass, the largest element ends up at the end.
5. Repeat steps 1-4 for the remaining part of the array (without the last element).
6. Repeat until the array is sorted.

Complexity: O(n²) — very slow for large arrays. But very simple to understand.

2. Insertion Sort

Analogy: You are playing cards. You take a new card from the deck and insert it into the correct place among the already sorted cards in your hand. At first, you have one card in your hand (it is already sorted). Then you take a second card and decide whether to put it to the left or right of the first. And so on.

How it works:

1. Start with the second element (index 1). Consider the first element (index 0) as the already sorted part.
2. Store the current element in a variable key.
3. Look at the elements to the left of key (in the sorted part). If they are greater than key, shift them one position to the right.
4. As soon as you find an element that is less than or equal to key, insert key into the vacated position.
5. Repeat for all elements of the array.

Complexity: O(n²) in the worst case, but on nearly sorted data it works very fast (O(n)).

3. Quick Sort

Analogy: Imagine you need to sort a pile of T-shirts by size. You take one T-shirt (let's call it the "pivot"). All T-shirts smaller than the pivot, you throw into the left pile, and those larger, into the right pile. Then you take each pile and repeat the same trick with a new pivot T-shirt. And so on until each pile has only one T-shirt left.

How it works:

1. Choose a pivot element. Usually, the middle or last element is taken.
2. Rearrange the elements so that all elements smaller than the pivot are to its left, and all elements greater are to its right. This is called partitioning.
3. Now the pivot is in its "rightful" place.
4. Recursively (call the function on itself) apply steps 1-3 to the left and right parts of the array.

Complexity: O(n log n) on average — this is very fast. O(n²) in the worst case (if the pivot is chosen poorly), but in practice this rarely happens.

Syntax in C++: all forms and variants

In C++, there are two approaches to sorting: write your own algorithm (for learning) or use the built-in function (for real work).

Standard function: std::sort

This is the "Swiss Army knife" of sorting. It is located in the <algorithm> library. It uses a hybrid algorithm (usually IntroSort — a mix of Quick Sort, Heap Sort, and Insertion Sort), which in 99% of cases works faster than anything you would write yourself.

Call form	Description	Example
std::sort(start, end)	Sorts from start to end (excluding end) in ascending order.	std::sort(arr, arr + n);
std::sort(start, end, comp)	Sorts with a custom comparator (comparison function).	std::sor