Can you list the main sorting algorithms and explain their principles?

Main sorting algorithms and their principles:

1. Bubble Sort — multiple passes through the array, comparing and swapping neighboring elements if they are in the wrong order. A simple but inefficient algorithm.

2. Selection Sort — at each step, the minimum (or maximum) element from the unsorted part is selected and swapped with the first element of that part.

3. Insertion Sort — elements are inserted one by one into the already sorted part of the array, shifting elements as necessary.

4. Quick Sort — a pivot element is chosen, the array is partitioned into elements less than and greater than the pivot, then these parts are recursively sorted.

5. Merge Sort — the array is recursively divided in half, then the sorted halves are merged into a single sorted array.

6. Heap Sort — a heap is built from the elements, then the maximum element is extracted and placed at the end of the array, repeated for the remaining elements.

Example of bubble sort in C++:

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}