38010

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

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

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

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

Русский

2013-09-25

156 KB

8 чел.

Лабораторная работа № 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) уже отсортирован.


 

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

81812. Наука как социокультурный феномен. Становление науки как социального института 38.59 KB
  Становление науки как социального института. Именно деятельностное понимание науки особо отмечал В. Вернадский: Ее содержание не ограничивается научными теориями гипотезами моделями создаваемой ими картиной мира в основе она главным образом состоит из научных фактов и их эмпирических обобщений и главным живым содержанием является в ней научная работа живых людей Во втором истолковании когда наука выступает как система знаний отвечающих критериям объективности адекватности истинности научное знание пытается обеспечить себе...
81813. Историческое развитие институциональных форм научной деятельности. Научные сообщества и их исторические типы 37.76 KB
  Возникновение науки как социального института связывают с кардинальными изменениями в общественном строе и в частности с эпохой буржуазных революций которая дала мощный толчок развитию промышленности торговли строительству горному делу мореплаванию. Способы организации и взаимодействия ученых менялись на протяжении всего исторического развития науки. Само существование науки в качестве социального института говорило о том что в системе общественного разделения труда она должна выполнять специфические функции а именно отвечать за...
81814. Наука и экономика. Наука и власть.Проблема государственного регулирования науки 28.08 KB
  Проблема государственного регулирования науки. Отношения науки и экономики всегда представляли собой большую проблему. Традиционное представление о том что технология является неотъемлемым приложением науки сталкивается с эмпирическими и практическими возражениями. Однако если прикладные науки обслуживая производство могут надеяться на долю в распределении его финансовых ресурсов то фундаментальные науки напрямую связаны с объемом бюджетного финансирования и наличием тех планов и программ которые утверждены государственными структурами.
81815. Поиск нового типа цивилизационного развития и новые функции науки в культуре 42.75 KB
  Наука действительно являет собой сложный полиструктурный организм целый мир в недрах которого бушуют познавательные страсти схлестываются несовместимые точки зрения ведется кропотливая экспериментаторская и теоретическая работа. Наука обладает способностью поглощать своих субъектов делать их фанатиками исследования. Однако на самом деле наука лишь один из видов человеческой соотнесенности с миром возникший исторически довольно поздно и выполняющий в жизни общества совершенно конкретные функции. Коренное различие состояло в том что...
81816. Роль науки в преодолении глобальных проблем современности 27.77 KB
  Ученые во всеуслышание заявляют о глобальных проблемах современности к которым относят проблемы охватывающие систему мир человек в целом и которые отражают жизненно важные факторы человеческого существования. Глобальные проблемы имеют не локальный а всеохватывающий планетарный характер. К глобальным проблемам современности относят экологические демографические проблемы войны и мира проблемы кризиса культуры. В силу этого глобальные проблемы должны решаться комплексно координированно усилиями всего мирового сообщества.
81817. Предмет современной философии науки 31.34 KB
  Создавая образ философии науки следует четко определить о чем идет речь: о философии науки как направлении западной и отечественной философии или же о философии науки как о философской дисциплине наряду с философией истории логикой методологией культурологией исследующих свой срез рефлексивного отношения мышления к бытию в данном случае к бытию науки. Философия науки как направление современной философии представлена множеством оригинальных концепций предлагающих ту или иную модель развития науки и эпистемологии. Она сосредоточена на...
81818. Понятие науки. Основные аспекты бытия науки 34.37 KB
  Наука как социальный институт или форма общественного сознания связанная с производством научнотеоретического знания представляет собой определенную систему взаимосвязей между научными организациями членами научного сообщества систему норм и ценностей. Они участвуют в разнообразных формах научного общения дискуссии конференции издания монографии учебники читают лекции и т. Выделим самые характерные черты научного знания. Еще Кант в качестве неотъемлемой черты науки отмечал систематичность научного знания: именно этим как он...
81819. Виховне середовище школи як інтегрований чинник впливу на соціальне становлення та розвиток учнівської молоді 74 KB
  У статті розглядається вплив виховного середовища в школі на соціальне становлення та розвиток учнівської молоді. Розкрито залежність типу виховного середовища школи від особистісної центрації педагога та педагогічного колективу загалом.
81820. Логико-эпистемологический подход к исследованию науки 32.07 KB
  Они полагали что причина большинства эпистемологических затруднений в неправильном использовании языка. Правильное же использование языка которому мы пока не научились даст возможность либо вообще избежать ошибок либо по крайней мере свести к минимуму ущерб от них. исследования языка в основу своих эпистемологических поисков неопозитивисты принялись за работу над многими проблемами методологии науки: тут и соотношение уровней познания принципы выбора теории определение факта место логики и математики в познании и т. Карнапа...