Сортировка массивов

1. Сортировка массивов

Сортировка обменом (пузырьковая
сортировка)
5
3
5
2
5
0
5
1
5
4
x[i]>x[i+1]

2.

3
2
3
0
3
1
4
5
2
0
2
1
3
4
5
x[i]>x[i+1]

3.

…
for (i=0; i<n-1; i++){
flag = 0;
for (j=0; j<n-i-1; j++)
if (x[j]>x[j+1]) {
flag = 1;
temp = x[j];
x[j]=x[j+1];
x[j+1]=temp; }
if (flag==0) break;
…

4.

Сортировка выбором
5
3
2
0
1
5
5
3
2
0
0
i=0
4
Поиск
минимального
элемента на
текущую
позицию

5.

0
3
2
5
1
i=1
3
2
2
1
0
1
2
5
3
2
2
2
2
5
3
4
5
3
3
i=2
0
i=3
1
4
1
4

6.

0
1
2
i=4
3
5
4
5
4
…
for(int i=0;i<n-1;i++)
{ int k = i;
for (int j=i+1;j<n;j++)
if (x[k]>x[j]) k=j;
if(k!=i) { int temp=x[i]; x[i]=x[k] ;
x[k]=temp;}
}…

7. Сортировка вставками

5
3
2
0
1
4
3
vs =x[1]
j=-1
j=0
Пока vs<x[j] и
j>=0

8.

5
2
vs =x[2]
2
3
0
1
4
j=-1
j=1
j=0
Пока vs<x[j] и
j>=0

9.

2
3
vs =x[3]
5
0
1
4
0
j=-1
j=2
j=1
j=0
Пока vs<x[j] и
j>=0

10.

0
2
vs =x[4]
3
5
1
4
1
j=3
j=0
j=1
j=2
Пока vs<x[j] и
j>=0

11.

0
1
vs =x[5]
2
3
5
4
4
j=4
j=3
Пока vs<x[j] и
j>=0

12. Многомерные массивы

Инициализация матриц
i
j
00
01
…
0n-2 0n-1
10
11
…
1n-2 1n-1
…
…
…
…
m-20
m-21
…
m-2n-2 m-2n-1
m-10
m-11
…
m-1n-2
…
m-1n-1

13.

Механизм
выделения
памяти
int **x, i;
x=(int**)malloc(sizeof( int*)*n);
for(i=0;i<n;i++)
x[i] = (int*)malloc(sizeof(int)*m);
x[0]
x00
x01 … X0m-1
x[1]
x10
x11 … X1m-1
x[2]
x20
x21 … X2m-1
xi0
xi1 … Xim-1
…
x[i]
…
x[n-1]
Xn-10 Xn-11 … Xn-1m-1

14.

Механизм
освобождения
памяти
for(i=n-1;i>=0;i--)
free (x[i]);
free(x);
x[0]
x00
x01 … X0m-1
x[1]
x10
x11 … X1m-1
x[2]
x20
x21 … X2m-1
xi0
xi1 … Xim-1
…
x[i]
…
x[n-1]
Xn-10 Xn-11 … Xn-1m-1

15. Обращение к элементу матрицы x[i,j]

фиксируется строка
for(i=0;i<n;i++)
фиксируется столбец
for(j=0;j<m;j++)
…
индекс строки
индекс столбца
X[i][j]

16.

i
j
00
01
…
0m-2 0m-1
10
11
…
1m-2 1m-1
…
…
…
…
n-20
n-21
…
n-2m-2 n-2m-1
n-10
n-11
…
n-1m-2
…
n-1m-1

17.

for(i=0;i<m;i++)
for(j=0;j<n;j++)
… x[j][i]
фиксируется строка
фиксируется столбец
i
j
00
01
…
0m-2 0m-1
10
11
…
1m-2 1m-1
…
…
…
…
n-20
n-21
…
n-2m-2 n-2m-1
n-10
n-11
…
n-1m-2 n-1m-1
…

18. Инициализация элементов матрицы. Ввод данных с клавиатуры.

…
float **A;
int n,m,i,j;
printf ("Введите количество строк матрицы: ");
scanf("%d",&n);
printf ("Введите количество столбцов матрицы: ");
scanf("%d",&m);
A = (float**) malloc(sizeof(float*)*n);

19.

for(i=0;i<n;i++)
A[i] = (float*) malloc(sizeof(float)*m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{ printf("A[%d][%d]= ",i,j);
scanf("%f",&(A[i][j]));
}
…

20. Получение значений случайным образом

…
float **x;
int n,m,i,j;
…
x = (float**) malloc(sizeof(float*)*n);
for( i=0;i<n;i++)
x[i] = (float*)malloc(sizeof(float)*m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
x[i][j] = rand()%200/(rand()%100+1.);
…

21. Печать элементов матрицы

i
j
00
01
… 0m-2 0m-1 “/n”
10
11
… 1m-2 1m-1 “/n”
…
…
…
n-20
n-21
…
n-2m-2 n-2m-1
n-10
n-11
…
n-1m-2 n-1m-1
…
…

22.

…
for(i=0;i<n;i++)
{
for( j=0;j<m;j++)
printf("%8.3f ",x[i][j]);
// переход на новую строку экрана
printf("\n");
}
…

23. Выделение областей матриц

Выделение строки с номером k:
k0
k1
…
km-2
km-1
…
for (i=0;i<m;i++)
Обращение к элементу x[k][i];
…

24. Выделение столбца с номером f

0f
1f
…
n-2f
n-1f
…
for (i=0;i<n;i++)
Обращение к элементу x[i][f];
…

25. Выделение блоков матриц

…
for ( i=0;i<n;i++)
for(j=0;j<=k;j++)
Обращение к элементу x[i][j];
…
z
k
…
for (i=0;i<=z;i++)
for(j=0;j<m;j++)
Обращение к элементу x[i][j];
…

26.

…
for (int i=z+1;i<n;i++)
for(int j=k+1;j<m;j++)
Обращение к элементу x[i][j];
…
z
k

27. Квадратные матрицы

0,0
0,n-1
1,1
1,n-2
2,2
i,n-1-i
…
for (i=0;i<n;i++)
Обращение к элементу
x[i][i];
…
i,i
…
m==n
for (i=0;i<n;i++)
Обращение к элементу
x[i][n-i-1];
…

28.

0,n-1
0,0
1,1
1,n-2
2,2
i,n-1-i
i,i
…
for (i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
Обращение к элементу
x[i][j];
…
…
for (i=1;i<n;i++)
for (j=0;j<i;j++)
Обращение к элементу
x[i][j];
…

29.

0,n-1
0,0
1,1
1,n-2
2,2
i,n-1-i
i,i
…
for (i=0;i<n-1;i++)
for (j=0;j<n-i-1;j++)
Обращение к элементу
x[i][j];
…
…
for (i=1;i<n;i++)
for (j=n-i;j<n;j++)
Обращение к элементу
x[i][j];
…

30.

В вещественной матрице размерности
nxm элементов найти минимальный
элемент и его местоположение в матрице.
#include <stdio.h>
#include <stdlib.h>
…
{
printf("Введите количество строк: ");

31.

int n,m,i,j;
srand(time(NULL));
scanf("%d",&n);
printf("Введите количество столбцов: ");
scanf("%d",&m);
float **x = (float**) malloc(sizeof(float*)*n);
for(i=0;i<n;i++)
x[i]=(float*)malloc(sizeof(float)*m);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{ x[i][j]=rand()%100/(rand()%100)+1.);

32.

printf("%8.2f",x[i][j]);}
printf("\n");
}
int imin,jmin;
float min = x[0][0];
for (i=0;i<n;i++)
for( j=0;j<m;j++)
if (min>x[i][j]) {
min = x[i][j];
imin=i;
jmin=j;}
printf("Минимальный элемент x[%d,%d] =
%8.2f \n",imin,jmin,min);

33.

for(i=n-1;i>=0;i--)
free( x[i]);
free( x);
…
}

34.

Отсортировать строки целочисленной матрицы
A[nxm] по возрастанию минимальных
элементов строк. //main51.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
…
{…
printf("Введите количество строк: ");

35.

int n,m,i ,j;
srand(time(NULL));
scanf("%d",&n);
printf("Введите количество столбцов: ");
scanf("%d",&m);
int **a = (int**)malloc(sizeof(int*)*n);
for(i=0;i<n;i++)
a[i]=(int*)malloc(sizeof(int)*m) ;
int* min = (int*)malloc(sizeof(int)*n);
for (i=0;i<n;i++)
min[i] = INT_MAX;
for(i=0;i<n;i++)
{

36.

for(j=0;j<m;j++)
{a[i][j]=rand()%101;
if (min[i]>a[i][j]) min[i] = a[i][j];
printf("%4d",a[i][j]); }
printf(" min = %4d",min[i]);
printf("\n");
}
int k;
int *temp;
for (i=0;i<n-1;i++)
for (j=0;j<n-1-i;j++)
{
if(min[j]>min[j+1]) {
temp = a[j];

37.

a[j]= a[j+1];
a[j+1]= temp;
k= min[j];
min[j] = min[j+1];
min[j+1] = k; }
}
printf("\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{

38.

printf("%4d",a[i][j]);}
printf(" min = %4d",min[i]);
printf("\n");
}
for(i=n-1;i>=0;i--)
free( a[i]);
free( a);
free(min);
system(“pause”);
}

39.

40.

Удалить из целочисленной матрицы А[nxm]
столбцы с последним отрицательным
элементом. // main52.c
#include …
int main() {
…// инициализация и печать матрицы a[n][m]
int k = 0,c;
for(i=0,c=0;c<m;i++,c++){
if (a[n-1][i]<0){
k++; i--;}
for(j=0;j<n;j++)
a[j][i+1]=a[j][i+k+1];
}
… // печать измененной матрицы a[n][m-k]
}