15. Сортировка обменами, шейкерная сортировка.
Сортирова обменами (пузырьковая):
Простая сортировка, суть которой заключается в циклическом сравнении пар элементов и их обменом, если левый сравниваемые элемент больше правого. гарантируется, что за первую итерацию в конце массива будет расположен максимальный элемент
void bubblesort(int* arr, int size)
{
bool flag = true;
int right = size-1;
while (flag)
{
flag = false;
for(int i = 0; i < right; ++i)
if (arr[i] > arr[i + 1])
{
flag = true;
std::swap(arr[i], arr[i+1]);
}
–right;
}
}
лучший случай: O(N)
средний случай: О( )
Шейкерная сортировка:
Является улучшенной версией сортировки пузырьком. улучшение проявляется за счет второго цикла, который проходит массив с конца, тем самым гарантируя, что за первый проход в начале и в конце будут находиться минимальный и максимальный элемент соответственно
void shackersort(int* arr, int size)
{
bool flag = true;
int left = 0, right = size - 1;
while (flag)
{
flag = false;
for(int i = left; i <= right; ++i)
if (arr[i] > arr[i + 1])
{
flag = true;
std::swap(arr[i], arr[i + 1]);
}
++left;
for(int i = right; i >= left; --i)
if(arr[i] < arr[i-1])
{
flag = true;
std::swap(arr[i], arr[i - 1]);
}
--right;
}
}
лучший случай: O(N)
средний случай: О( )
16.Сортировка выбором.
Принцип работы сортировки заключается в поиске минимального элемента и обменом с неотсортированным началом массива
void selectionsort(int* arr, int size)
{
int min_idx;
for (int i = 0; i < size - 1; i++)
{
min_idx = i;
for (int j = i + 1; j < size; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
std::swap(arr[min_idx], arr[i]);
}
}
17. Сортировка подсчетом. (Требуется проверка)
Принцип состоит в том, что в алгоритме не производятся сравнения, вместо этого заводится массив с количеством уникальных значений, после чего исходный массив заменяется… (короче гифка)
Входной массив должен иметь небольшой разброс с неотрицательными значениями.
void countsort(int *array, int size)
{
unsigned int min, max;
max = min = array[0];
for (int i = 1; i < size; i++)
{
if (array[i] < min)
min = array[i];
if (array[i] > max)
max = array[i];
}
int *counts = new int [max - min + 1];
int count_size = max - min + 1;
for (int i = 0; i < count_size; ++i)
counts[i] = 0;
for (int i = 0; i < size; i++)
counts[array[i] - min]++;
int index = 0;
for (int i = 0; i < count_size; i++)
for (int j = 0; j < counts[i]; j++)
array[index++] = i + min;
}
Сложность: O(n + k) // не понял, что такое k (прим. k - размер вспомогательного массива, количество уникальных значений)