Сортировка простыми вставками.

Просматривается последовательность чисел а₁,…,а _n и каждый очередной элемент а _i вставляется на подходящее место в уже упорядоченную совокупность а_1,…,а _{i -1}. Это место определяется последовательным сравнением а _i с упорядоченными элементами а ₁,…,а _{i -1}.

 

		j		i
2	7	12	23	9	13	31	15

 

2

7

12

23

9

13

31

15

 

 

2

7

12

23

9

13

31

15

 

2

7

12

12

23

13

31

15

 

 

2

7

9

12

23

13

31

15

 

 

Текст программы

 

 void main()

 {float a[30]={6,1,34,16,8,32,56,3,8,4},dop;

int n,i,j,k;

 

n=10;

            for (i=0;i<n;i++)

             printf(" %5.1f",a[i]);

 

for (i=1;i<n;i++)

for (j=0;j<=i-1;j++)

if (a[i]<a[j]) { dop=a[i];

                for (k=i;k>j;k--)

                a[k]=a[k-1];

           a [ j ]= dop;

               }

 

printf("\n отсортированный массив\n ");

for (i=0;i<n;i++)

printf(" %6.1f",a[i]);

 

}

 

  Пример 4 .7

Задана матрица. Отсортировать положение строк по возрастанию элементов ее первого столбца

 

 void main()

 {

float a[10][10],dop;

int n,m,i,j,f=1;

n=5; m=5;

 printf("\n исходная матрица");

 

   for (i=0;i<n;i++)

   {

printf(" \n");

for (j=0;j<m;j++)

{

a[i][j]=0.001*rand();

printf(" %5.1f",a[i][j]);

}

}

 

while(f==1)

{

f=0;

for (i=0;i<n-1;i++)

if (a[i][0]>a[i+1][0])

             for (j=0;j<m;j++)

             {

               dop=a[i][j];

            a[i][j]=a[i+1][j];

            a[i+1][j]=dop;

            f=1;

         }

}

printf("\n отсортированная матрица");

for (i=0;i<n;i++)

    {

    printf(" \n");

    for (j=0;j<m;j++)

    printf(" %5.1f",a[i][j]);

    }

}

Контрольные вопросы для самопроверки

1. Какие массивы называются упорядоченными?

2. В чем заключается смысл сортировки?

3. Как выглядит алгоритм сортировки выбором?

4. Как выглядит алгоритм сортировки обменами?

5. Как выглядит алгоритм сортировки простыми вставками?

 

ФУНКЦИИ

 

Функция - это часть программы, описывающая выполнение заданного набора действий. В языке С любая программа - это функция с именем main(). Функций могут быть стандартными или разработаны программистом. Стандартные функции - это готовые к использованию функции, например sin(x), cos (x), scanf(...), printf(...) и другие. Они размещены в библиотеках языка С. Для их использования необходимо сначала подключить соответствующий заголовочный файл с помощью директивы препроцессора #include, а затем вызвать необходимую стандартную функцию, указав ее имя и задав значения аргументов. Функции, составленные программистом это новые, дополнительные функции. Эти функции разрабатываются, когда структура программы достаточно сложная, когда необходимо несколько раз выполнить одинаковый набор действий для различных величин и т.п.

Для использования функций в программе необходимо:

1. Описать функцию.

2. Сделать к ней обращения (вызвать функцию).

Описание функции

Форма описания функции имеет вид:

Часть функции	Пояснения
<тип>name(<тип1>арг1,…<тип n> арг n)	Заголовок   функции
{	Открытие функции
Описание 1; .... описание n;	Описание внутренних (локальных) переменных
оператор 1;  ......... оператор n;	Операторная часть, или тело функции
}	Закрытие функции

Заголовок функции:

тип>name(<тип1>арг1,…<тип n> арг n)

<тип> – тип результата, который возвращает функция.

Тип может буть определенным – int, float, char, или неопределенным – void. Если тип не определен, то по умолчанию он также может быть- int;

name – идентификатор для обозначения функции

(<тип1>арг1,…<тип n> арг n) – список аргументов функции с указанием их типов.

<тип_і> – тип аргумента;

арг_і – имя аргумента.

Функция может не иметь аргументов, тогда скобки остаются пустыми.

Вызов функции

Чтобы вызвать функцию, нужно указать ее имя и задать конкретные аргументы (фактические аргументы, или параметры), для которых функция выполняет вычисления.

Имеются две формы вызова функций:

1. Функция имеет тип void. Вызов является самостоятельным оператором:

name (факт_арг1, факт_арг2,...);

Фактические аргументы должны соответствовать списку аргументов в описании функции (по количеству, порядку следования, типам).

 

Пример 6.1: Составить функцию, которая определяет большее значение из двух заданных чисел f = max(x,y) и печатает результат в самой функции.

void f_max (float a, float b)

{   

float max;

if(a>b) max = a;

      else max = b;

printf (“\n %4.1f”, max);

}

Int main()

 { float x, y;

scanf(“%f%f”,&x,&y);

f_max(y, x);

 }

 

2. Функция имеет определенный тип (не void). Вызов не является самостоятельным оператором. Он записывается внутри другого оператора или выражения (присваивания, if, printf,...):

b = name (факт_арг1, факт_арг2,...);

Пример 6.2 составить функцию, которая определяет большее значение из двух заданных f = max(x, y) и распечатать результат в основной программе.

  float fmax (float a, float b)

{   

float max;

if(a>b) max = a;

else max = b;

return max;

}

void main()

{  

float x, y, z;

scanf(“%f%f”,&x,&y);

z =fmax(y, x);

printf(“\n%4.1f”, z);

}