38010

ИССЛЕДОВАНИЕ СОРТИРОВОК РАЗЛИЧНЫХ ТИПОВ

Лабораторная работа

Информатика, кибернетика и программирование

Задача работы: овладеть навыками написания программ при исследовании различных методов сортировки. Теория Среди улучшенных методов сортировки встречаются как доработанные прямые методы так и методы уже более высокого уровня т. с новой идеей где одним из элементов сортировки является прямой метод.

Русский

2013-09-25

156 KB

6 чел.

Лабораторная работа № 6

ИССЛЕДОВАНИЕ СОРТИРОВОК РАЗЛИЧНЫХ ТИПОВ

Цель работы: изучить различные методы сортировки как прямые (выбора, включения и обмена), так и улучшенные (слияниями, пирамидальная - турнирная,  распределяющая, пузырьковая с просеиванием, метод поиска нового номера и метод последовательного поиска минимумов).

Задача работы: овладеть навыками написания программ при исследовании различных методов сортировки.

Порядок работы :

  1.  изучить описание лабораторной работы;
  2.  по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
  3.  написать программу в соответствии с вариантом задания;
  4.  отладить программу;
  5.  решить задачу;
  6.  оформить отчет.

Теория

Среди улучшенных методов сортировки встречаются как доработанные прямые методы, так и методы уже более высокого уровня, т.е. с новой идеей, где одним из элементов сортировки является прямой метод. Эффективность у доработанных прямых методов лучше, чем N*N, но не достигает N*lonN. А у улучшенных методов более высокого уровня эффективность близка к N*lonN. Улучшенные прямые методы обычно применяют на небольших объёмах данных, а вот улучшенные методы более высокого уровня используются для сортировки больших объёмов.

Улучшенные прямые методы

К улучшенным прямым методам относятся: пузырьковая сортировка с просеиванием; сортировка методом поиска нового номера; метод последовательного поиска минимумов.

«Пузырьковая» сортировка с просеиванием. Он аналогичен методу пузырьковой сортировки, но после перестановки пары соседних элементов выполняется просеивание, т.е. наименьший левый элемент продвигается к началу массива, на сколько это возможно, пока не выполняется условие упорядоченности. Преимущество данного метода в том, что он ускоряет работу, если минимальный или максимальный (в зависимости от сортировки) элемент массива стоит в конце. Тогда как прямой обмен проигрывает в таких случаях.

Пример программы «пузырьковой» сортировки с просеиванием:

const n=10;

var x:array[1..n] of integer;

i,j,t,i1:integer;

flagsort:boolean;

procedure P_P;

begin

repeat

flagsort:=true;

for i:=1 to n-1 do

if not(x[i]<=x[i+1]) then

begin

t:=x[i];

x[i]:=x[i+1];

x[i+1]:=t;

j:=i;

while (j>1) and not(x[j-1]<=x[j]) do

begin

t:=x[j];

x[j]:=x[j-1];

x[j-1]:=t;

dec(j);

end;

flagsort:=false;

end;

until flagsort;

end;

begin

for i1:=1 to n do readln(x[i1]);

P_P;

for i1:=1 to n do writeln(x[i1]);

readln;

end.

Метод поиска нового номера. Принцип работы сортировки методом поиска нового номера заключается в том, что последовательно для каждого элемента массива вычисляется его новая позиция в отсортированном массиве. Для этого рассчитывается количество элементов, значения которых меньше значения анализируемого элемента. Или же количество элементов, значения которых меньше и равно значению анализируемого элемента. Особенностью данного метода является то, что требуется дополнительный массив, не чувствительный к изначальной упорядоченности.

Ниже приводится пример программы метода поиска нового номера, если n – это размерность массива, mass1 – это исходный массив, а NewMass – это массив из отсортированных элементов.

const n=8;

type TArr =array[1..100] of integer;

var mass1,NewMass : TArr;

i : integer;

{ }

procedure NewNSort(var mass,Nmass:TArr; size:integer);

var   i,j,NewN : integer;

begin

for i:=1 to size do

begin

NewN:=0;

for j:=1 to size do

if (mass[j]<mass[i]) or((mass[j]=mass[i]) and(j<=i))then inc(NewN);

Nmass[NewN]:=mass[i];

end;

end;

begin

for i:=1 to n do readln(mass1[i]);

NewNSort(mass1,NewMass,n);

for i:=1 to n do writeln(NewMass[i]);

readln;

end.

Метод последовательного поиска минимумов. Рассмотрим принцип работы данного метода. Просматривается весь массив, ищется минимальный элемент и ставится на место первого, а «старый» первый элемент ставится на место найденного.

Ниже приводится программа последовательного поиска минимумов.

Type TArr = array[1..10] of integer;

Var mass : TArr;

n,i1 : integer;

procedure NextMinSearchSort( size:integer);

var

i,j,Nmin,temp:integer;

begin

for i:=1 to size-1 do

begin

nmin:=i;

for j:=i+1 to size do if mass[j]<mass[Nmin] then Nmin:=j;

temp:=mass[i];

mass[i]:=mass[Nmin];

mass[Nmin]:=temp;

end;

end;

begin

readln(n);

for i1:=1 to n do readln(mass[i1]);

NextMinSearchSort(n);

for i1:=1 to n do writeln(mass[i1]);

readln;

end.

Улучшенные методы более высокого уровня

Наряду с быстрой сортировкой, сортировкой Шелла и Пирамидальной сортировкой, существуют и другие улучшенные методы. Это сортировка слияниями, а так же пирамидальная - турнирная сортировка, сложность которых примерно равна N*lonN. Имеет место так же и распределяющая - цифровая - поразрядная сортировка, у которой сложность в определённых случаях близка к величине k*N.

Пирамидальная - турнирная сортировка. Данная сортировка является улучшенным вариантом пирамидальной сортировки. Отличие состоит в том, что вместо пошагового сравнения трёх соседних элементов при просеивании элементов на втором этапе используют сортировку крайних элементов пирамиды по убыванию.

Пример программы пирамидальной - турнирной сортировки:

const n=8;

Type arrType =Array[1 .. n] of Integer;

Procedure HeapSort(Var ar: arrType; n: Integer);

Var i, Left, Right: integer;

x: Integer;

T: Integer;

Procedure sift;

Var i, j: Integer;

Begin

i := Left;

j := 2*i;

x := ar[i];

While j <= Right do

Begin

If j < Right Then If ar[j] < ar[Succ(j)] Then Inc(j);

If x >= ar[j] Then Break;

ar[i] := ar[j];

i := j;

j := 2 * i

End;

ar[i] := x

end;

Begin

Left := Succ(n div 2);

Right := n;

While Left > 1 Do

Begin

Dec(Left);

sift

End;

While Right > 1 Do

Begin

T := ar[ Left ];

ar[ Left ] := ar[ Right ];

ar[ Right ] := T;

Dec(Right);

sift

End

End;

var b:arrType;

i1:integer;

begin

for i1:=1 to n do readln(b[i1]);

HeapSort(b,n);

for i1:=1 to n do writeln(b[i1]);

readln;

end.

Сортировка слияниями. Ниже приводится пример программы, реализующей алгоритм сортировки слияниями.

const n=8;

Type arrType = Array[1 .. n] Of Integer;

var a:arrType;

i1:integer;

Procedure merge(Var ar: arrType; n: Integer);

Procedure Slit( k, q: Integer );

Var m: Integer;

i, j, T: Integer;

d: arrType;

Begin

m := k + (q-k)div 2;

i := k;

j := Succ(m);

t := 1;

While (i <= m) and (j <= q) Do

Begin

If ar[i] <= ar[j] Then

Begin

d[T] := ar[i];

Inc(i)

End

Else

Begin

d[T] := ar[j];

Inc(j)

End;

Inc(T)

End;

While i <= m Do

Begin

d[T] := ar[i];

Inc(i);

Inc(T)

End;

While j <= q Do

Begin

d[T] := ar[j];

Inc(j);

Inc(T)

End;

For i := 1 to Pred(T) Do  ar[Pred(k+i)] := d[i]

End;

Procedure Sort(i, j: Integer);

Var T: integer;

Begin

If i >= j Then Exit;

If j-i = 1 Then

Begin

If ar[j] < ar[i] Then

Begin

T := ar[i];

ar[i] := ar[j];

ar[j] := T

End

End

Else

Begin

Sort(i, i + (j-i)div 2);

Sort(i + (j-i)div 2 + 1, j);

Slit(i, j)

End;

End;

Begin

Sort(1, n);

End;

begin

for i1:=1 to n do readln(a[i1]);

merge(a,n);

for i1:=1 to n do write(a[i1],'  ');

readln;

end.

Распределяющая - цифровая - поразрядная сортировка. Сначала все данные сортируются по младшему байту и делятся на группы, с одинаковым младшим байтом. Далее процесс повторяется для каждой группы. Далее рассмотрим принцип работы сортировки по младшему байту на простеньком примере.

Если необходимо отсортировать последовательность данных, у которых максимум по k байт в каждом ключе, то величина k должна быть известна заранее, до сортировки. За элемент сортировки можно принять так же и слово – это двойной байт, или буквы, если сортируются строки. Разрядность данных m, т.е. количество возможных значений элементов, также должна быть известна заранее и постоянна.

Если сортируются слова, то элемент сортировки – это буква, т.е. m = 33. Если в самом длинном слове 10 букв, то k = 10. Обычно сортируют числовые данные по ключам из k байт, где m=256.

Теперь рассмотрим принцип работы сортировки по младшему байту на простеньком примере. Есть массив source из N элементов по одному байту в каждом, который состоит из элементов {7,9,8,5,4,7,7}. В нашем случае m=9.

Первым делом составляется таблица распределений, где i-ый элемент distr[] – это количество ключей со значением i. Она заполняется так:

for i := 0 to Pred(255) Do distr[i]:=0;

for i := 0 to Pred(n) Do distr[source[i]] := distr[[i]] + 1;

Таким образом, для нашего примера получим таблицу распределений:

distr = ( 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 ).

Далее идёт заполнение таблицы индексов, т.е. помещается информация о будущем количестве символов в отсортированном массиве до символа с ключом i. Для нашего примера index[8] = 5.

index: array[0 .. 255] of integer;

index[0]:=0;

for i := 1 to Pred(255) Do index[i]=index[i-1]+distr[i-1];

Потом заполняется отсортированный массив sorted размера N:

for i := 0 to Pred(n) Do 

Begin

sorted[ index[ source[i] ] ]:=source[i];

{попутно изменяем index уже вставленных символов, чтобы одинаковые ключи шли один за другим:}

index[ source[i] ] := index[ source[i] ] +1;

End;

Таким образом, приведённый массив может быть отсортирован за O(n) действий. Следовательно, если в массиве будут числа, состоящие максимум из k байт, то весь массив будет отсортирован за O(k*n) проходов. Аналогичным образом можно отсортировать строки и числа.

Ниже приводится пример программы распределяющей - цифровой - поразрядной сортировки:

Const  n = 8; m = 256;

Type arrType =Array[0 .. Pred(n)] Of Byte;

var  a,b: arrType;

i1:integer;

Procedure RadixSort(Var source, sorted: arrType);

type indexType =Array[0 .. Pred(m)] Of Byte;

var    distr,index: indexType;

i: integer;

begin

fillchar(distr, sizeof(distr), 0);

for i := 0 to Pred(n) do inc(distr[source[i]]);

index[0] := 0;

for i := 1 to Pred(m) do index[i] :=index[Pred(i)] + distr[Pred(i)];

for i := 0 to Pred(n) do

begin

sorted[index[source[i]] ] := source[i];

index[source[i]] :=index[source[i]]+1;

end;

end;

begin

for i1:=0 to Pred(n) do readln(a[i1]);

RadixSort(a, b);

for i1:=0 to Pred(n) do writeln(b[i1]);

readln;

end.

Быстрая сортировка. Принцип работы сортировки подробно рассматривается в лекциях. Ниже приведём два варианта использования быстрой сортировки.

Первый вариант использования:

const n=8;

Type arrType =Array[1 .. n] Of Integer;

var b:arrType;

i1:integer;

Procedure HoarFirst( Var ar: arrType; n: integer);

Procedure sort(m, l: Integer);

Var i, j, x, w: Integer;

Begin

i := m; j := l;

x := ar[(m+l)div 2];

Repeat

While ar[i] < x Do Inc(i);

While ar[j] > x Do Dec(j);

If i <= j Then

Begin

w := ar[i];

ar[i] := ar[j];

ar[j] := w;

Inc(i);

Dec(j)

End

Until i > j;

If m < j Then Sort(m, j);

If i < l Then Sort(i, l)

End;

Begin

sort(1, n)

End;

begin

for i1:=1 to n do readln(b[i1]);

HoarFirst(b,n);

for i1:=1 to n do writeln(b[i1]);

readln;

end.

Второй вариант использования:

const n=8;

type arrType=array[1..n] of integer;

var b:arrType;

i1:integer;

Procedure HoarSecond(Var ar: arrType; n: Integer);

Procedure Sort(m, l: Integer);

Var i, j, x, w: Integer;

Begin

If m >= l Then Exit;

i := m;

j := l;

x := ar[(m+l) div 2];

While i < j Do If ar[i] < x Then Inc(i)

Else If ar[j] > x Then Dec(j)

Else

Begin

w := ar[i];

ar[i] := ar[j];

ar[j] := w;

End;

Sort(m, Pred(j));

Sort(Succ(i),l);

End;

Begin

Sort(1, n)

End;

begin

for i1:=1 to n do readln(b[i1]);

HoarSecond(b,n);

for i1:=1 to n do writeln(b[i1]);

readln;

end.

Сортировка Шелла. Принцип работы этой сортировки разбирается в одной из лекций. А пример программы, реализующей данный метод сортировки, приведён ниже.

const n=18;

var ii,m,x,s,p,t,k,r,i,j: integer;

a:array[1..n] of integer;

begin

for i:=1 to n do readln(a[i]);

t:= trunc(ln(n)/ln(2));

repeat

t:= t-1;

k:= (1 shl t)-1;

p:= n mod k;

s:= n div k;

if p=0 then p:= k else s:= s+1;

writeln(k,'-cortirovka');

for i:= 1 to k do

{берем и длинные, и короткие подпоследовательности}

begin

if i= p+1 then s:= s-1; {для коротких - уменьшаем     длину}

{метод ПрВст с шагом k}

for j:= 1 to s-1 do if a[i+(j-1)*k]>a[i+j*k]

then

begin

x:= a[i+j*k];

m:= i+(j-1)*k;

while (m>0) and (a[m]>x) do

begin

a[m+k]:= a[m];

m:= m-k;

end;

a[m+k]:= x;

end;

end;

until k=1;

readln;

end.

Исследование улучшенных методов сортировки

Иногда, чтобы определить эффективность работы сортировки, требуется провести небольшое исследование. Это бывает необходимо из-за того, что не всегда можно учесть все различные случаи, т.е. различные варианты состояния изначальных массивов. Для эффективного и точного исследования требуется перебрать большое число последовательностей с разным количеством элементов, чтобы определить характер зависимости числа сравнений или числа перестановок в зависимости от числа элементов сортируемой последовательности при определённых условиях.

Для примера такого исследования был взят метод пирамидальной сортировки. Программа приведена ниже:

var r,i1,z1,N,N1,N2:integer;

z_cpednii:real;

a:array[1..100] of integer;

z_cred:array[1..100] of real;

z:array[1..20] of integer;

function proseit_one_element(b,j:integer):boolean;

var k,x:integer;

begin

proseit_one_element:=false;

while j<=(b div 2) do

begin

k:= 2*j;

if (k+1<=b) and (a[k]<a[k+1]) then k:= k+1;

if a[k]>a[j] then

begin

x:= a[j];

a[j]:= a[k];

a[k]:= x;

j:= k;

proseit_one_element:=true;

end

else break

end

end;

procedure in_put_massiv;

var i:integer;

begin

for i:=1 to N do readln(a[i]);

writeln;

end;

procedure out_put_massiv;

var i:integer;

begin

for i:=1 to N do write(a[i]:2,'  ');

writeln;

end;

procedure Analiz_chisla_proseivanii(v1,v2:integer; var c:integer);

begin

out_put_massiv;

writeln('proseili dla piramidi: ', v1,' chislo raz');

writeln('proseili samy piramidy sortirya: ', v2,' chislo raz');

c:=v1+v2;

{writeln('vsego proseili: ', v1+v2,' chislo raz');}

end;

procedure piramida_sort;

var s1,s2:integer;

i,j,k,x:integer;

begin

in_put_massiv;

out_put_massiv;

{обнуляем счётчики для анализа числа просеиваний}

s1:=0;s2:=0;

{Превращаем исходный массив в пирамиду (с помощью просеивания всех элементов)}

for i:= (N div 2)downto 1 do

begin

j:= i;

{просеиваем один элемент}

if proseit_one_element(N,j) then s1:=s1+1;

end;

{окончательно сортируем пирамиду}

for i:= N downto 2 do

begin

{меняем местами первый элемент с рабочим}

x:= a[1];

a[1]:= a[i];

a[i]:= x;

j:= 1;

{просеиваем один элемент в пирамиде с уменьшающимся числом элементов на 1}

if proseit_one_element(i-1,j) then s2:=s2+1;

end;

{Анализируем число просеиваний}

Analiz_chisla_proseivanii(s1,s2,z[i1]);

end;

procedure piramida_sort_N1;

begin

writeln('vvedite kolichestvo sortirovok');

readln(N1);

for i1:=1 to N1 do piramida_sort;

for i1:=1 to N1 do write(z[i1]:2,' ');

z1:=0;

for i1:=1 to N1 do z1:=z1+z[i1];

z_cpednii:=z1/N1;

writeln('chislo proseivanii crednee',z_cpednii:3:1);

for i1:=1 to N1 do z[i1]:=0;

end;

begin

writeln('skolko raz sortiryem s raznimi chislami elementov');

readln(N2);

for r:=1 to N2 do

begin

writeln('vvedite chislo sortiryemix elementov');

readln(N);

piramida_sort_N1;

z_cred[r]:=z_cpednii;

z_cpednii:=0;

end;

for r:=1 to N2 do write('crednii znachenia',z_cred[r]);

readln;

end.

Для более эффективного исследования можно ручной ввод массива заменить на рандомизированный.

Задания по вариантам:

Необходимо выполнить задание в соответствии с номером варианта, который соответствует столбцу А из таблицы 6.1.

В соответствии с заданием необходимо выполнить исследование предложенного по варианту алгоритма.

Таблица 6.1

Задание на лабораторную работу №6

А

Задание

1

Выявить, как в процентном соотношении отличается эффективность работы алгоритма распределяющей – цифровой – поразрядной сортировки от алгоритма быстрой сортировки (первый способ) по числу сравнений.

2

Выявить, как в процентном соотношении отличается эффективность работы алгоритма «пузырьковой» сортировки с просеиванием от алгоритма «пузырьковой» сортировки по числу сравнений.

3

Выявить, как в процентном соотношении отличается эффективность работы алгоритма пирамидальной – турнирной сортировки от алгоритма пирамидальной сортировки по числу сравнений.

4

Выявить, как в процентном соотношении отличается эффективность работы алгоритма сортировки методом поиска нового номера от алгоритма «пузырьковой» сортировки с просеиванием по числу сравнений.

5

Разобрать принцип работы приведённого алгоритма слияниями и сравнить его с алгоритмом быстрой сортировки (первый способ реализации).

6

Выявить, как в процентном соотношении отличается эффективность работы алгоритма сортировки методом поиска нового номера от алгоритма «пузырьковой» сортировки с просеиванием по числу перемещений.

7

Выявить, как в процентном соотношении отличается эффективность работы алгоритма распределяющей – цифровой – поразрядной сортировки от алгоритма быстрой сортировки (второй способ) по числу сравнений.

8

Выявить, как в процентном соотношении отличается эффективность работы алгоритма «пузырьковой» сортировки с просеиванием от алгоритма «пузырьковой» сортировки по числу перемещений.

9

Выявить, как в процентном соотношении отличается эффективность работы алгоритма пирамидальной – турнирной сортировки от алгоритма пирамидальной сортировки по числу перемещений.

10

Выявить, как в процентном соотношении отличается эффективность работы алгоритма сортировки методом поиска нового номера от алгоритма сортировки прямого включения по числу сравнений.

11

Разобрать принцип работы приведённого алгоритма слияниями и сравнить его с алгоритмом быстрой сортировки (второй способ реализации)

12

Выявить, как в процентном соотношении отличается эффективность работы алгоритма сортировки методом поиска нового номера от алгоритма сортировки методом последовательного поиска минимумов по числу сравнений.

13

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом распределяющей – цифровой – поразрядной сортировки, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.

14

Выявить, как в процентном соотношении отличается эффективность работы алгоритма сортировки методом поиска нового номера от алгоритма сортировки методом последовательного поиска минимумов по числу перемещений.

15

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом пирамидальной – турнирной сортировки.

16

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом «пузырьковой» сортировки с просеиванием.

17

Выявить, как в процентном соотношении отличается эффективность работы алгоритма слияниями от алгоритма быстрой сортировки (первый способ) по числу сравнений.

18

Выявить, как в процентном соотношении отличается эффективность работы алгоритма сортировки методом поиска нового номера от алгоритма сортировки прямого включения по числу перемещений.

19

Выявить, как в процентном соотношении отличается эффективность работы алгоритма распределяющей – цифровой – поразрядной сортировки от алгоритма быстрой сортировки (первый способ) по числу перестановок.

20

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом последовательного поиска минимумов.

21

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом пирамидальной – турнирной сортировки.

22

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом последовательного поиска минимумов.

23

Выявить, как в процентном соотношении отличается эффективность работы алгоритма слияниями от алгоритма быстрой сортировки (второй способ) по числу сравнений.

24

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом «пузырьковой» сортировки с просеиванием.

25

Выявить зависимость числа просеиваний от числа элементов массива, если он сортируется методом пирамидальной – турнирной сортировки.

26

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом сортировки поиска нового номера.

27

Выявить, как в процентном соотношении отличается эффективность работы алгоритма распределяющей – цифровой – поразрядной сортировки от алгоритма быстрой сортировки (второй способ) по числу перестановок.

28

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом поиска минимумов, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.

29

Выявить, как в процентном соотношении отличается эффективность работы алгоритма слияниями от алгоритма быстрой сортировки (первый способ) по числу перестановок.

30

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом поиска минимумов, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.

31

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом пирамидальной сортировки.

32

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом «пузырьковой» сортировки с просеиванием, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.

33

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом распределяющей – цифровой – поразрядной сортировки, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.

34

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом сортировки поиска нового номера.

35

Выявить, как в процентном соотношении отличается эффективность работы алгоритма слияниями от алгоритма быстрой сортировки (второй способ) по числу перестановок.

36

Выявить, как в процентном соотношении отличается эффективность работы алгоритма прямого выбора от алгоритма сортировки методом последовательного поиска минимумов по числу сравнений.

37

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом распределяющей – цифровой – поразрядной сортировки.

38

Выявить, как в процентном соотношении отличается эффективность работы алгоритма прямого выбора от алгоритма сортировки методом последовательного поиска минимумов по числу перемещений.

39

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом пирамидальной сортировки.

40

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом «пузырьковой» сортировки с просеиванием, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.

41

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом слияниями.

42

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом сортировки поиска нового номера, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.

43

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом пирамидальной сортировки, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.

44

Выявить, как в процентном соотношении отличается эффективность работы сортировки последовательного поиска минимумов от алгоритма «пузырьковой» сортировки с просеиванием по числу сравнений.

45

Выявить зависимость числа перемещений от числа элементов массива, если он сортируется методом распределяющей – цифровой – поразрядной сортировки.

46

Выявить, как в процентном соотношении отличается эффективность работы сортировки последовательного поиска минимумов от алгоритма «пузырьковой» сортировки с просеиванием по числу перемещений.

47

Выявить зависимость числа перестановок от числа элементов массива, если он сортируется методом слияниями.

48

Выявить зависимость числа просеиваний от числа элементов массива, если он сортируется методом «пузырьковой» сортировки.

49

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом пирамидальной сортировки, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.

50

Выявить зависимость числа сравнений от числа элементов массива, если он сортируется методом сортировки поиска нового номера, и если массив каждый раз находится в двух состояниях: 1) отсортирован в обратном порядке; 2) уже отсортирован.


 

А также другие работы, которые могут Вас заинтересовать

47161. Государственный экологический контроль. Права государственных экспертов 71.28 KB
  Государственный контроль в области охраны окружающей среды государственный экологический контроль осуществляется федеральными органами исполнительной власти и органами исполнительной власти субъектов Российской Федерации. Государственный контроль в области охраны окружающей среды государственный экологический контроль осуществляется в порядке установленном Правительством Российской Федерации. В случае если при строительстве реконструкции капитальном ремонте объектов капитального строительства предусмотрено осуществление...
47162. Subordinate clauses of adverbial positions 71.5 KB
  Adverbial clauses are usually classified according to their meaning, that is, according to the relation they bear to the main clause. They differ from nominal and attributive clauses in that they are introduced by conjunctions with a more distinct meaning
47163. Загальна характеристика судової системи України. Місцеві державні адміністрації, їх повноваження 66 KB
  Конституційний Суд України є єдиним органом конституційної юрисдикції в Україні. Система судів загальної юрисдикції відповідно до Конституції України будується за принципами територіальності і спеціалізації. Систему судів загальної юрисдикції складають:1 місцеві суди;2 апеляційні суди Апеляційний суд України;3 Касаційний суд України був визнаний неконституційним за рішенням Конституційного Суду України;4 вищі спеціалізовані суди;5 Верховний Суд України.
47164. Предпринимательские функции государства. Особенности функционирования государственных предприятий и их виды 71.9 KB
  Теория безработицы. Причины и формы безработицы. Последствия безработицы закон Оукена. Взаимосвязь инфляции и безработицы.
47166. Региональный уровень организации управления 72 KB
  Многозначность понятия региона отражена в нормативных актах Российской Федерации например в утвержденных 3 июня 1996 года Основных положениях региональной политики в РФ. В данном документе регион трактуется как часть территории Российской Федерации обладающая общностью природных социальноэкономических национальнокультурных и иных условий. Регион может совпадать с границами территории субъекта федерации либо объединять территории нескольких субъектов Российской Федерации. Регионы как субъекты федерации в федеративном государстве...
47168. Предложение, его закон, факторы и эластичность 73.5 KB
  Предприятие представляет собой первичное звено народного хозяйства в системе общественного разделения труда. разделения труда. Общее разделение труда. Частное разделение труда.
47169. Понятие труда. Трудовой процесс и его элементы 72.5 KB
  Понятие труда. Труд: Рассмотрение труда как экономической категории труд как экономический ресурс впервые это затронул Маршалл. Характерные черты труда: Целесообразная деятельность Осознанная деятельность Общественнозначимая деятельность; удовлетворение личных и общественных потребностей Трудовой процесс совокупность действий исполнителей по преобразованию предмета труда в продукт труда выполняемых на рабочем месте. Основные составляющие: Предмет труда Орудие труда Средства труда Работник.