#include <iostream>
using namespace std;
void inclusion()
{
int size = 20;
int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10};
int comparisons = 0;
int permutations = 0;
cout << "Массив ДО сортировки методом прямого включения:" << endl;
for(int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом прямого включения:" << endl;
for (int i = 0; i<size; i++)
{
int value = arr[i];
int index = i;
while ((index > 0) && (arr[index - 1] > value))
{
arr[index] = arr[index - 1];
index --;
permutations += 1;
comparisons += 1;
}
arr[index] = value;
comparisons += 1;
}
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << endl << "перестановки - " << permutations;
cout << endl << "сравнения - " << comparisons << endl;
}
void selection()
{
int size = 20;
int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10};
int comparisons = 0;
int permutations = 0;
int min, temp; // для поиска минимального элемента и для обмена
cout << "Массив ДО сортировки методом прямого выбора:" << endl;
for(int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом прямого выбора:" << endl;
for (int i = 0; i < size - 1; i++)
{
min = i; // запоминаем индекс текущего элемента
// ищем минимальный элемент чтобы поместить на место i-ого
for (int j = i + 1; j < size; j++) // для остальных элементов после i-ого
{
if (arr[j] < arr[min]) // если элемент меньше минимального,
{
min = j; // запоминаем его индекс в min
comparisons += 1;
}
else{
comparisons += 1;}
}
temp = arr[i]; // меняем местами i-ый и минимальный элементы
arr[i] = arr[min];
arr[min] = temp;
permutations += 1;
}
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << endl << "перестановки - " << permutations;
cout << endl << "сравнения - " << comparisons << endl;
}
void bubble()
{
int size = 20;
int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10};
int comparisons = 0;
int permutations = 0;
cout << "Массив ДО сортировки методом пузырька:" << endl;
for(int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом пузырька:" << endl;
// Для всех элементов
for (int i = 0; i < size - 1; i++)
{
for (int j = (size - 1); j > i; j--) // для всех элементов после i-ого
{
if (arr[j - 1] > arr[j]) // если текущий элемент меньше предыдущего
{
int temp = arr[j - 1]; // меняем их местами
arr[j - 1] = arr[j];
arr[j] = temp;
permutations += 1;
}
comparisons += 1;
}
}
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << endl << "перестановки - " << permutations;
cout << endl << "сравнения - " << comparisons << endl;
}
void Shell()
{
int size = 20;
int arr[size] = {20, 1, 19, 2, 18, 3, 17, 4, 16, 5, 15, 6, 14, 7, 13, 8, 12, 9, 11, 10};
int comparisons = 0;
int permutations = 0;
int d = 4;
cout << "Массив ДО сортировки методом Шелла:" << endl;
for(int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout <<endl <<endl << "Массив ПОСЛЕ сортировки методом Шелла:" << endl;
while (d > 0)
{
for (int i = d; i < size; i++)
{
int index = i;
int value = arr[i];
while ((index >=d) && (arr[index - d] > value))
{
arr[index] = arr [index - d];
index = index - d;
permutations += 1;
comparisons += 1;
}
arr[index] = value;
comparisons += 1;
}
if (d/2 != 0)
d = d/2;
else if (d == 1)
d = 0;
else
break;
}
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << endl << "перестановки - " << permutations;
cout << endl << "сравнения - " << comparisons;
}
int main()
{
inclusion();
cout << "==================================================" << endl;
selection();
cout << "==================================================" << endl;
bubble();
cout << "==================================================" << endl;
Shell();
return 0;
}