#include <iostream>
int main()
{
int i;
int tmp;
int comp; // количество сравнений
int per; // количество перестановок
int N=10;
int a[11];
//заполнение массива почти отсортированными данными
for (i = 0; i < N-1; ++i) // цикл проходов, i - номер прохода
{
a[i]=i+1;
}
a[N-1]=0;
for (int i = 0; i <= N-1; i++) {
std::cout << a[i] <<" ";
}
std::cout<<" Исходный массив (почти отсортированный)"<<std::endl;
per=0;
comp=0;
for (int i = 1, j; i < N; ++i) // цикл проходов, i - номер прохода
{
tmp = a[i];
for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности
{
a[j + 1] = a[j]; // сдвигаем элемент направо, пока не дошли
++per;
++comp;
}
a[j + 1] = tmp; // место найдено, вставить элемент
++per;
}
for (int i = 0; i <= N-1; i++) {
std::cout << a[i] << " ";
}
std::cout<<" Массив, отсортированный методом вставки"<<std::endl;
std::cout<<per<<" перестановок "<<comp<<" сравнений"<< std::endl;
//заполнение массива случайными данными
for (i = 0; i < N; ++i) // цикл проходов, i - номер прохода
{
a[i]=rand() % 9 ;
}
for (int i = 0; i <= N-1; i++) {
std::cout << a[i] << " ";
}
std::cout<<" Исходный массив (случайный)"<<std::endl;
per=0;
comp=0;
for (int i = 1, j; i < N; ++i) // цикл проходов, i - номер прохода
{
tmp = a[i];
for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности
{
a[j + 1] = a[j]; // сдвигаем элемент направо, пока не дошли
++per;
++comp;
}
a[j + 1] = tmp; // место найдено, вставить элемент
++per;
}
for (int i = 0; i <= N-1; i++) {
std::cout << a[i] << " ";
}
std::cout<<" Массив, отсортированный методом вставки"<<std::endl;
std::cout<<per<<" перестановок "<<comp<<" сравнений"<< std::endl;
//заполнение массива перевёрнутыми данными данными
for (i = 0; i < N; ++i) // цикл проходов, i - номер прохода
{
a[i]=N-i-1;
}
for (int i = 0; i <= N-1; i++) {
std::cout << a[i] <<" ";
}
std::cout<<" Исходный массив (перевёрнутый)"<<std::endl;
per=0;
comp=0;
std::cout<<per<<" перестановок "<<comp<<" сравнений"<< std::endl;
for (int i = 1, j; i < N; ++i) // цикл проходов, i - номер прохода
{
tmp = a[i];
for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности
{
a[j + 1] = a[j]; // сдвигаем элемент направо, пока не дошли
++per;
++comp;
}
a[j + 1] = tmp; // место найдено, вставить элемент
++per;
}
for (int i = 0; i <= N-1; i++) {
std::cout << a[i] << " ";
}
std::cout<<" Массив, отсортированный методом вставки"<<std::endl;
std::cout<<per<<" перестановок "<<comp<<" сравнений"<< std::endl;
return 0;
}