2.5 Контрольные примеры решения задачи с помощью алгоритма сортировки простыми включениями

Пример сортировки массива, отсортированного случайным образом.

Пусть задан такой массив из восьми элементов: (32,43,2,30,82,8,5,52) (см. Таб. 1).

Пошаговое решение:

Шаг 1:

1) i=2;

2) x=43; a[0]=43; j=1;

3) x > a[j]=32;

3.2) a[2]= 43;

4) i=3; i ? n=8 > п. 2;

Шаг 2:

2) x=2; a[0]=2; j=2;

3) x < a[j]=43;

3.1) a[3]=43; j=1; > п. 3;

3) x < a[j]=32;

3.1) a[2]=32; j=0; > п. 3;

3) x = a[j];

3.2) a[1]=2;

4) i=4; i<n > п. 2;

Шаг 3:

2) x=30; a[0]=30; j=3;

3) x < a[j]=43;

3.1) a[4]=43; j=2; > п. 3;

3) x < a[j]=32;

3.1) a[3]=32; j=1; > п. 3;

3) x > a[1]=2

3.2) a[2]=30;

4) i=5; i<n > п. 2;

Шаг 4:

2) x=82; a[0]=82; j=4;

3) x > a[j];

3.2) a[5] = 82;

4) i=6; i<n > п. 2;

Шаг 5:

2) x=8; a[0]=8; j=5;

3) x < a[j]=82;

3.1) a[6]=82; j=4; > п. 3;

3) x < a[j]=43;

3.1) a[5]=43; j=3; > п. 3;

3) x < a[j]=32;

3.1) a[4]=32; j=2; > п. 3;

3) x < a[j]=30;

3.1) a[3]=30; j=1; > п. 3;

3) x > a[j]=2;

3.2) a[2]=8;

4) i=7; i<n > п. 2;

Шаг 6:

2) x=5; a[0]=5; j=6;

3) x < a[j]=82;

3.1) a[7]=82; j=5; > п. 3;

3) x < a[j];

3.1) a[6]=43; j=4; > п. 3;

3) x < a[j]=32;

3.1) a[5]=32; j=3; > п. 3;

3) x < a[j]=30;

3.1) a[4]=30; j=2; > п. 3;

3) x < a[j]=8;

3.1) a[3]=8; j=1; > п. 3;

3) x > a[j]=2;

3.2) a[2]=5;

4) i=8; i?n > п. 2;

Шаг 7:

2) x=52; a[0]=52; j=7;

3) x < a[j]=82;

3.1) a[8]=82; j=6; > п. 3;

3) x > a[j]=43;

3.2) a[7]=52;

4) i=9; i>n > конец алгоритма.

Таким образом, имеем 21 пересылку элементов и 20 сравнений.

Пример сортировки уже отсортированного массива.

Пусть задан такой массив из восьми элементов: (2,5,8,30,32,43,52,82).

Пошаговое решение:

Шаг 1:

1) i=2;

2) x=5; a[0]=2; j=1;

3) x > a[j]=2;

3.2) a[2]=5;

4) i=3; i<n > п. 3;

Шаг 2:

2) x=8; a[0]=8; j=2;

3) x > a[j]=5;

3.2) a[3]=8;

4) i=4; i<n > п. 3;

Шаг 3:

2) x=30; a[0]=30; j=3;

3) x > a[j]=8;

3.2) a[4]=30;

4) i=5; i<n > п. 3;

Шаг 4:

2) x=32; a[0]=32; j=4;

3) x > a[j]=30;

3.2) a[5]=32;

4) i=6; i<n > п. 3;

Шаг 5:

2) x=43; a[0]=43; j=5;

3) x > a[j]=32;

3.2) a[6]=43;

4) i=7; i<n > п. 3;

Шаг 6:

2) x=52; a[0]=52; j=6;

3) x > a[j]=43;

3.2) a[7]=52;

4) i=8; i?n > п. 3;

Шаг 7

2) x=82; a[0]=82; j=7;

3) x > a[j]=52;

3.2) a[8]=82;

4) i=9; i>n >конец алгоритма.

Таким образом получили 7 пересылок и 7 сравнений.

Пример сортировки массива, отсортированного в обратном порядке.

Пусть задан такой массив из восьми элементов: (82,52,43,32,30,8,5,2).

Пошаговое решение:

Шаг 1:

1) i=2;

2) x=52; a[0]=52; j=1;

3) x< a[j]=52;

3.1) a[2]=82; j=0; > п. 3;

3) x=a[j];

3.2) a[1]=52;

4) i=3; i<n > п. 2;

Шаг 2:

2) x=43; a[0]=43; j=2;

3) x < a[j]=82;

3.1) a[3]=82; j=1; > п. 3;

3) x < a[j]=52;

3.1) a[2]=52; j=0; > п. 3;

3) x = a[j];

3.2) a[1]=43;

4) i=4; i<n > п. 2;

Шаг 3:

2) x=32; a[0]=32; j=3;

3) x < a[j]=82;

3.1) a[4]=82; j=2; > п. 3;

3) x < a[j]=52;

3.1) a[3]=52; j=1; > п. 3;

3) x < a[j]=43;

3.1) a[2]=43; j=0; > п. 3;

3) x=a[j];

3.2) a[1]=32;

4) i=5; i<n > п. 2;

Шаг 4:

2) x=30; a[0]=30; j=4;

3) x < a[j]=82;

3.1) a[5]=82; j=3; > п. 3;

3) x < a[j]=52;

3.1) a[4]=52; j=2; > п. 3;

3) x < a[j]=43;

3.1) a[3]=43; j=1; > п. 3;

3) x < a[j]=32;

3.1) a[2]=32; j=0; > п. 3;

3) x=a[j];

3.2) a[1]=30;

4) i=6; i<n > п. 2;

Шаг 5:

2) x=8; a[0]=8; j=5;

3) x < a[j]=82;

3.1) a[6]=82; j=4; > п. 3;

3) x < a[j]=52;

3.1) a[5]=52; j=3; > п. 3;

3) x < a[j]=43;

3.1) a[4]=43; j=2; > п. 3;

3) x < a[j]=32;

3.1) a[3]=32; j=1; > п. 3;

3) x < a[j]=30;

3.1) a[2]=30; j=0; > п. 3;

3) x=a[j];

3.2) a[1]=8;

4) i=7; i<n > п. 2;

Шаг 6:

2) x=5; a[0]=5; j=6;

3) x < a[j]=82;

3.1) a[7]=82; j=5; > п. 3;

3) x < a[j]=52;

3.1) a[6]=52; j=4; > п. 3;

3) x < a[j]=43;

3.1) a[5]=43; j=3; > п. 3;

3) x < a[j]=32;

3.1) a[4]=32; j=2; > п. 3;

3) x < a[j]=30;

3.1) a[3]=30; j=1; > п. 3;

3) x < a[j]=8;

Страницы: 1, 2, 3, 4