Реализации алгоритмов/Сортировка/Пирамидальная: различия между версиями

→‎C++ (другой вариант): Нормальное оформление кода
(→‎C++ (другой вариант): Нормальное оформление кода)
<source lang="cpp">
#include <iostream>
#include <conio.h>
 
using namespace std;
 
void iswap (int &n1, int &n2) {
{
int temp = n1;
n1 = n2;
}
 
int main () {
unsigned const n = 100u;
{
int const n = 100;
int a[n];
for ( int i = 0; i < n; ++i ) { a[i] = n - i; cout << a[i] << " "; }
//заполняем массив для наглядности.
//-----------сортировка------------//
//сортирует по-возрастанию. чтобы настроить по-убыванию,
//поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
int sh = 0; //смещение
bool b = false;
for(;;)
{
b = false;
for ( int i = 0; i < n; i++ )
{
if( i * 2 + 2 + sh < n )
{
if( ( a[i + sh] > /*<*/ a[i * 2 + 1 + sh] ) || ( a[i + sh] > /*<*/ a[i * 2 + 2 + sh] ) )
{
if ( a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh] )
{
iswap( a[i + sh], a[i * 2 + 1 + sh] );
b = true;
}
else if ( a[i * 2 + 2 + sh] < /*>*/ a[ i * 2 + 1 + sh])
{
iswap( a[ i + sh], a[i * 2 + 2 + sh]);
b = true;
}
}
//дополнительная проверка для последних двух элементов
//с помощью этой проверки можно отсортировать пирамиду
//состоящую всего лишь из трех элементов
if( a[i*2 + 2 + sh] < /*>*/ a[i*2 + 1 + sh] )
{
iswap( a[i*2+1+sh], a[i * 2 +2+ sh] );
b = true;
}
}
else if( i * 2 + 1 + sh < n )
{
if( a[i + sh] > /*<*/ a[ i * 2 + 1 + sh] )
{
iswap( a[i + sh], a[i * 2 + 1 + sh] );
b = true;
}
}
}
if (!b) sh++; //смещение увеличивается, когда на текущем этапе
//сортировать больше нечего
if ( sh + 2 == n ) break;
} //конец сортировки
 
// Для наглядности заполняем массив числами от n до 0.
for (unsigned i = 0u; i < n; ++i) {
a[i] = n - i;
std::cout << a[i] << ' ';
}
 
// ----------- Сортировка ------------
cout << endl << endl;
// Сортирует по возрастанию. Чтобы получить сортировку по убыванию,
for ( int i = 0; i < n; ++i ) cout << a[i] << " ";
// поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
unsigned sh = 0u; // Смещение
bool b;
do {
b = false;
for (unsigned i = 0u; i < n; ++i) {
if (i * 2 + 2 + sh < n) {
if ((a[i + sh] > /*<*/ a[i * 2 + 1 + sh]) || (a[i + sh] > /*<*/ a[i * 2 + 2 + sh])) {
if (a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh]) {
iswap(a[i + sh], a[i * 2 + 1 + sh]);
b = true;
} else if (a[i * 2 + 2 + sh] < /*>*/ a[i * 2 + 1 + sh]) {
iswap(a[i + sh], a[i * 2 + 2 + sh]);
b = true;
}
}
// Дополнительная проверка для последних двух элементов;
// с её помощью можно отсортировать пирамиду
// состоящую всего лишь из трёх элементов
if (a[i * 2 + 2 + sh] < /*>*/ a[i * 2 + 1 + sh]) {
iswap(a[i * 2 + 1 + sh], a[i * 2 + 2 + sh]);
b = true;
}
} else if (i * 2 + 1 + sh < n) {
if (a[i + sh] > /*<*/ a[ i * 2 + 1 + sh]) {
iswap(a[i + sh], a[i * 2 + 1 + sh]);
b = true;
}
}
}
if (!b)
++sh; // Смещение увеличивается, когда на текущем этапе сортировать больше нечего
} while (sh + 2 < n); // Конец сортировки
 
std::cout << std::endl << std::endl;
for (unsigned i = 0u; i < n; ++i)
std::cout << a[i] << ' ';
 
getch();
return 0;
}
Анонимный участник