Некоторые основные виды сортировки и их применение:

1. Пузырьковая сортировка. 14 Последовательно сравнивает значения соседних элементов и меняет числа местами, если предыдущее оказывается больше последующего. 4 Элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале. 4 Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности. 4
2. Сортировка вставками. 16 Метод делит массив на две части: отсортированную и общую. 6 В начале выполнения алгоритма считается, что первый элемент массива уже стоит на своём месте. 6 Поэтому массив начинают рассматривать со второго элемента и продолжают так до тех пор, пока все элементы в отсортированной части не окажутся на своих местах. 6 Алгоритм сортировки вставками хорошо показывает себя на небольших наборах данных. 6
3. Сортировка выбором. 46 Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). 4 Затем выбранное значение меняют местами со значением первого неотсортированного элемента. 4 Этот шаг нужно повторять до тех пор, пока в массиве не закончатся неотсортированные подмассивы. 4 Сортировка выбором оказывается неэффективной в больших массивах. 6
4. Быстрая сортировка. 46 Это одна из самых быстрых и универсальных сортировок. 6 Алгоритм построен на принципе «Разделяй и властвуй» и чаще всего применяется в реальных проектах. 6 В начале выполнения быстрой сортировки необходимо выбрать опорный элемент. 6 После этого массив делится на две части: элементы меньше «опоры» перемещаются влево, а больше — вправо. 6 Далее рекурсивно выполняют деление и сортировку для каждой части до тех пор, пока части не достигнут минимального размера. 6
5. Сортировка слиянием. 24 Используется, когда структура данных не поддерживает произвольный доступ. 2 Она работает с чистым последовательным доступом, то есть с прямыми итераторами, а не с итераторами произвольного доступа. 2 Сортировка слиянием пригодится для таких структур данных, в которых доступ к элементам осуществляется последовательно (например, для потоков). 4