Метод сортировки вставками элемента
void vstavka(int a[], int n)
{
for( int i = 1; i<n; i++)
for( int j = 0; j< i-1; j++)
if( a[j] > a[i])
{
int r=a[i];
for( int k = i; k> j+1; k++)
{
a[k] = a[k-1];
a[k-1] = r;
}
}
}
19. Алгоритм сортировки выбором элемента
Сортировка выбором элемента - это наиболее привычный и в то же время не самый худший способ решения задачи. В массиве нужно найти элемент с минимальным значением и поменять его местами с первым элементом массива (для сортировки по убыванию - это нужно сделать с максимальным элементом!). После этого элемент с минимальным значением отыскивается среди всех элементов, кроме первого, и меняется значениями со вторым элементом массива и т.д. В результате все элементы выстраиваются по порядку.
Данный алгоритм имеет общую опенку трудоемкости на уровне 0(n2). По сравнению с алгоритмами вставки и "пузырька" он обеспечивает существенно меньшее количество перемещений элементов (обменов) и в большинстве случаев может оказаться более быстрым, чем они. Для учащихся, испытывающих затруднения с программированием более сложных и громоздких алгоритмов, метод можно рекомендовать в качестве учебного.
// Метод сортировки выбором элемента
void vwibor(int a[], int n)
{
for( int i = 0; i<n-1; i++)
{
int r =i;
for( int j = i+1; j<n; j++)
if( a[r] > a[j])
r =j;
swap( &a[r], &a[i]);
}
}
Контрольные вопросы
1. Чем отличается операция от оператора?
2. Объясните основные свойства операции: арность, ассоциативность, приоритет.
3. В чем состоит оптимизация компилятора при вычислении логических выражений?
4. Объясните разницу между автоматическим и отложенным инкрементированием.
5. Чему равно (2 + 7/3)%3
6. Чему равно ~x | x для целого типа x
7. Вычислите 10 & 15 | 20.
8. Замените оператор условия
if(x<5)
y=z;
else
e=-z;
одним выражением.
9. Вычислите 25>>2<<3
10. Найдите максимальное число из трех чисел с помощью одного выражения.
11. В переменной char c сбросьте флаги, то есть замените 1 на 0, если они есть, во втором и пятом битах.
12. Преобразуйте цикл for в while
for(int i=-2; i<5; i++)
13. Преобразуйте цикл while в for
float q=4.5;
while(q--)
printf(“%f”, q);
С помощью перестройки улучшите структуру следующего фрагмента программы
done = i = 0;
while ( i < MAXI && !done){
if(( x/2 ) > 1 ) { i++; continue;}
done++;}
Запишите без оператора goto следующий фрагмент
m: if(A)
{
B;
goto m;
}
14. Перепишите операторы условного перехода так, чтобы их условия не содержали логических операций.
if(A && B || !C)
D;
else if(B || C)
E;
Else F;
15. Вычислить факториал n! тремя способами с помощью трех видов цикла.
16. Запишите двойной цикл
for (int i = 0; i<5; i++)
{
printf(“\n”);
for (int j = 0; j<4; j++)
printf(“%3d”, i*j);
}
с помощью одинарного цикла с теми же счетчиками i, j..
17. Замените оператор
if(A)
B;
эквивалентным оператором цикла for