и их реализация на С++
Сортировка выбором (Selection sort)
Пузырьковая сортировка (Bubble sort)
Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
Шейкерная сортировка (двунаправленная пузырьковая сортировка).
Сортировка выбором (Selection sort)
Алгоритм сортировки выбором заключается в следующем:
- На первой итерации цикла находим наименьший элемент массива, запоминаем его индекс.
- Меняем местами наименьший элемент и нулевой.
- На второй итерации перебираем все элементы от первого до последнего. Находим наименьший и запоминаем его индекс.
- Ставим наименьший элемент в первую позицию массива.
И так далее, пока не останется один последний элемент массива. К тому времени массив будет отсортирован по возрастанию.
Реализация алгоритма сотрировки выбором на с++:
void Select(int* arr, const int size) {
int tmp = 0;
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++)
if (arr[j] < arr[i]) {
tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
}
Пузырьковая сортировка (Bubble sort)
Пузырькова сортировка заключается в следующем:
При первом проходе сравниваются сначала нулевой и первый элементы массива. И если нулевой больше первого, то они меняются местами. Потом сравниваются первый и втророй, если первый больше второго, то они меняются местами. В конце сравниваются предпоследний и последний элементы. Если предпоследний элемент больше последнего, то они меняются местами. Таким образом наибольший элемент массива оказывается на последнем месте.
При втрором проходе все тоже самое, но до последнего элемента.
Итак, пока не останутся два первый элемента.
В результате такого алгоритма массив будет отсортирован в порядке возрастания.
Код реализации пузырьковой сортировки на С++:
void Bubble(int* arr, const int size) {
int tmp = 0;
for (int i = 0; i < size - 1; i++)
for (int j = 1; j < size - i; j++)
if (arr[j - 1] < arr[j]) {
tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
}
}
Сортировка вставками (Insertion sort)
Алгоритм сортировки вставками работает следующим образом:
Весь массив делится на две части упорядочинную и неупорядоченную. Изначально нулевой элемент массива является упорядоченной частью массива, а остальная часть массива неупорядоченной. Все элементы из неупорядоченной части перемещаются в упорядоченную в нужную позицию.
При первом проходе элемент с индексом 1 обозначается ключем. Он сравнивается с элементом с индексом 0. Если элемент 1 меньше элемента 0, то они меняются местами.
На втором проходе ключем выбирается элемент с индексом 2. Он смещается влево пока элементы слева больше ключа. Таким образом текущий элемент становится на свое место смещая вправо все элементы, которые больше ключа.
И так, пока очередь не дойдет до последнего элемента.
В результате массив будет отсортирован по возрастанию.
Реализация алгоритма на С++:
void Insert(int* arr, const int size) {
int j = 0;
int key = 0;
for (int i = 1; i < size; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
arr[j + 1] = key;
}
}
}
Сортировка слиянием (Merge Sort)
Сортировка слиянием работает следующим образом:
Исходный массив разбивается на две части. Каждая из частей рекурсивно разбивается на две части или сортируется, если их размер равен 2.
Сортировка слиянием в процессе работы использует много оперативной памяти!
Поэтому для тестирования алгоритма попробуйте использовать массив небольшого размера. У меня на ноутбуке этот алгоритм работает с массивом в пять элементов.
Реализация сортировки слиянием на С++:
void Merge(int* arr, int first, int last) {
int mid = first + (last - first) / 2 + 1;
int size = last - first + 1; // размер массива
int* c = new int[size];
memset(c, 0, size * sizeof(int));
// индекс первого элемента второй половины
int i = first; // временный поток
int c1 = first; // индекс первого потока
int c2 = mid; // индекс второго потока
while (c1 < mid && c2 <= last) {
// выбор наименьшего элемента из двух потоков
// и запись во временный массив
if (arr[c1] <= arr[c2]) {
c[i] = arr[c1];
c1++;
i++;
}
else {
c[i] = arr[c2];
c2++;
i++;
}
}
// запись оставшихся элементов во временный массив
while (c1 < mid) {
c[i] = arr[c1];
c1++;
i++;
}
while (c2 <= last) {
c[i] = arr[c2];
c2++;
i++;
}
// копирование временного массива в исходный
for (int i = first; i <= last; i++) {
arr[i] = c[i];
}
}
void MergeSort(int* arr, int first, int last) {
int size = last - first + 1;
// индекс первого элемента второй половины
int mid = size / 2 + 1;
//if (size % 2)mid++;
// первый элемент первого потока
int Lfirst = first;
// последний элемент первого потока
int Llast = mid - 1;
// первый элемент второго потока
int Rfirst = mid;
// последний элемент второго потока
int Rlast = last;
if (size > 2) {
// рекурсивный вызов первого потока
MergeSort(arr, Lfirst, Llast);
// рекурсивный вызов второго потока
MergeSort(arr, Rfirst, Rlast);
// слияние двух потоков
Merge(arr, first, last);
}
// сортировка, если в массиве всего два элемента
if (size == 2) {
if (arr[first] > arr[last]) {
int tmp = arr[first];
arr[first] = arr[last];
arr[last] = tmp;
}
}
}
Быстрая сортировка (Quick sort)
Быстрая сортировка соответствует своему названию, так как работает быстрее других алгоритмов. Этот алгоритм работает следующим образом:
На первом шаге в массиве выбирается один опорный элемент, желетельно средний или околосредний. Все элементы, которые находятся слева от опорного и которые больше него меняются местами с элементами, которые находятся спава и меньше опорного. Таким образом, слева от опорного элемента оказываются все элементы меньшие опорного, а справа элементы большие опорного.
На втором шаге рекурсивно выполняются операции из первого шага для двух половин массива.
И так далее функция будет выполнятся рекурсивно, пока части массива не будут содержать минимальное количество элементов.
Реализация быстрой сортировки на С++:
void QuickSort(int* arr, int first, int last) {
int mid, tmp;
int f = first, l = last;
mid = arr[(f + l) / 2];
do {
// сдвиг левого указателя вправо
// до значения большего опорного
while (arr[f] < mid) f++;
// сдвиг правого указателя влево
//до значения меньшего опорного
while (arr[l] > mid) l--;
if (f <= l) {
// выбранные значения меняются местами
tmp = arr[f];
arr[f] = arr[l];
arr[l] = tmp;
f++;
l--;
}
} while (f < l);
// рекурсивный вызов функции для обеих частей массива
if (first < l) QuickSort(arr, first, l);
if (f < last) QuickSort(arr, f, last);
}
Шейкерная сортировка.
Шейкерная сортировка работает по принципу пузырьковой сортировки, но в двух направлениях. А именно, при первом проходе сравниваются нулевой элемент массива с первым: если нулевой больше, то они меняются местами. Потом первый со вторым и так далее…
В результате максимальный элемент оказывается на последнем месте.
Потом идет проход в обратном направлении аналагичным образом. В результате: минимальный элемент становится на нулевую позицию.
Потом в обратном направлении начиная с первого и до конца неотсортированной части массива. И так, пока весь массив не будет отсортирован. В результае такого алгоритма массив будет отсортирован по возрастанию.
Реализация «шейкерной сортировки» на С++:
void Swap(int* arr, int i)
{
int tmp;
tmp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = tmp;
}
void ShakerSort(int* arr, int start, const int size)
{
int Left, Right, i;
Left = start;
Right = size - 1;
while (Left <= Right) {
for (i = Right; i >= Left; i--)
if (arr[i - 1] > arr[i]) Swap(arr, i);
Left++;
for (i = Left; i <= Right; i++)
if (arr[i - 1] > arr[i]) Swap(arr, i);
Right--;
}
}
Если есть вопросы по работе алгоритмов, задавайте в комментариях: с удовольствием отвечу!
