Метод сортировки вставками элемента

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(n²). По сравнению с алгоритмами вставки и "пузырька" он обеспечивает существенно меньшее количество перемещений элементов (обменов) и в большинстве случаев может оказаться более быстрым, чем они. Для учащихся, испытывающих затруднения с программированием более сложных и громоздких алгоритмов, метод можно рекомендовать в качестве учебного.

// Метод сортировки выбором элемента

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

Дата добавления: 2014-01-05