Форум программистов, компьютерный форум, киберфорум
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
0 / 0 / 0
Регистрация: 25.02.2018
Сообщений: 20
1

Для челночной сортировки определить количество сравнений и обменов

27.02.2018, 16:19. Просмотров 1397. Ответов 8
Метки нет (Все метки)


Челночная сортировка.
Размерность сортируемого массива: n = 10, n = 50, n = 250.

Для указанного в задании алгоритма сортировки необходимо составить программу сорти-
ровки целочисленного массива. При этом приведенные программы можно
упростить, заменив массив из записей типа item массивом целых чисел. Тогда
роль поля item.key (или a[i].key) будет выполнять сам элемент массива a[i].
Исходный массив заполняется случайным образом при помощи обра-
щения к стандартной функции random(т), возвращающей псевдослучайные
числа в диапазоне от 0 до m – 1. Например:
for i := 1 to n do a[i] := random(m);
При этом всегда будем считать, что m = 100. Помните о том, что до
первого использования функции random в программе необходимо один раз
94
вызвать процедуру без параметров randomize (например, сразу после первого
begin).
В результате выполнения данного задания необходимо получить для
каждой из приведенных в задании размерностей массива число обменов, со-
вершаемых в процессе сортировки. Для этого необходимо ввести в програм-
му целочисленный счетчик (устанавливаемый в 0 в начале работы алгоритма
сортировки), который будет увеличиваться на единицу после каждой опера-
ции обмена (т.е. операции присваивания, в правой или левой части которой
встречается элемент массива a). Поскольку искомая величина будет меняться
с каждым пуском программы (т.к. сортируемый массив задается случайным
образом), повторите сортировку (для размерности сортируемого массива) 10
раз и выдайте среднее число обменов за 10 сортировок
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.02.2018, 16:19
Ответы с готовыми решениями:

Количество сравнений и обменов при сортировке матрицы разными способами
Необходимо создать однородную таблицу. Затем применить три метода сортировки: Бинарным включением,...

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

Методы сортировки: цифровой сортировки и деревьев сравнений
помогите решить методы сортировки: цифровой сортировки и деревьев сравнений ДАНО :номер...

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

__________________
Помогаю в написании студенческих работ здесь.
8
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5698 / 3413 / 2430
Регистрация: 22.11.2013
Сообщений: 9,580
Записей в блоге: 1
27.02.2018, 17:24 2
Челнок, он же шейкер, можно взять здесь:
Сортировки

Делаете пару утилит для сравнения и обмена, внутри увеличиваете счетчик, заменяете ими сравнение и обмен:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
var CCmp, CXch: Word;
 
function IsLess(a, b: Integer): Boolean;
begin
  Inc(CCmp); IsLess:=a<b;
end;
 
procedure Swp(var a, b: Integer);
var t: Integer;
begin
  Inc(CXch); t:=a; a:=b; b:=t;
end:
и генерируете и сортируете свой массив нужное число раз.
0
Модератор
62965 / 46969 / 32371
Регистрация: 18.05.2008
Сообщений: 113,838
27.02.2018, 18:42 3
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
uses crt;
const n1=10;
      n2=50;
      n3=250;
type mas=array[1..n3] of integer;
procedure vvod(var a:mas;n:integer);
var i:integer;
begin
for i:=1 to n do
a[i]:=-10+random(21);
end;
procedure sort(var a:mas;n:integer;var ob:integer);
var i,j,k,d,x:integer;
begin
d:=1;
i:=0;
ob:=0;
for k:=n-1 downto 1 do { k - количество сравниваемых пар }
 begin
  i:=i+d;
  for j:=1 to k do
   begin
    if (a[i]-a[i+d])*d>0 then
    {меняем местами соседние элементы}
     begin
      inc(ob);
      x:=A[i];
      a[i]:=a[i+d];
      a[i+d]:=x;
     end;
   inc(i,d);
  end;
 d:=-d;
{меняем направление движения на противоположное}
end;
end;
 
var a:mas;
    i,o,k:integer;
begin
clrscr;
randomize;
k:=0;
writeln('Массив размером ',n1);
for i:=1 to 10 do
 begin
  vvod(a,n1);
  sort(a,n1,o);
  k:=k+o;
 end;
k:=round(k/n1);
writeln('Среднее число обменов=',k);
k:=0;
writeln('Массив размером ',n2);
for i:=1 to 10 do
 begin
  vvod(a,n2);
  sort(a,n2,o);
  k:=k+o;
 end;
k:=round(k/n2);
writeln('Среднее число обменов=',k);
k:=0;
writeln('Массив размером ',n3);
for i:=1 to 10 do
 begin
  vvod(a,n3);
  sort(a,n3,o);
  k:=k+o;
 end;
k:=round(k/n3);
writeln('Среднее число обменов=',k);
readln;
end.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5698 / 3413 / 2430
Регистрация: 22.11.2013
Сообщений: 9,580
Записей в блоге: 1
27.02.2018, 20:40 4
Ну и 43-72 можно свернуть:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
const n: array [1..3] of Integer = (10, 50, 250);
var j: Integer;
...
 
  for j:=Low(n) to High(n) do begin
    k:=0;
    WriteLn('Массив размером ',n[j]);
    for i:=1 to n[j] do begin
      vvod(a,n1);
      sort(a,n1,o);
      k:=k+o;
    end;
    WriteLn('Среднее число обменов=',k/n[j]:0:2);
  end;
Выпало число сравнений.
0
Модератор
62965 / 46969 / 32371
Регистрация: 18.05.2008
Сообщений: 113,838
27.02.2018, 20:43 5
Цитата Сообщение от bormant Посмотреть сообщение
Выпало число сравнений.
Так вроде нужно
Цитата Сообщение от Alexandr_msk Посмотреть сообщение
выдайте среднее число обменов за 10 сортировок
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
5698 / 3413 / 2430
Регистрация: 22.11.2013
Сообщений: 9,580
Записей в блоге: 1
27.02.2018, 21:07 6
В сухом остатке для варианта из #2:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
type TElement = Integer;
var CCmp, CXch: Word;
 
procedure ShakerSort(var a: array of TElement; nn: Integer);
  function IsLess(a, b: TElement): Boolean;
  begin
    Inc(CCmp); IsLess:=a<b;
  end;
  procedure Swp(var a, b: TElement);
  var t: TElement;
  begin
    Inc(CXch); t:=a; a:=b; b:=t;
  end;
var
  l, r, n, j: Integer;
  t: TElement;
begin
  l:=0; n:=l; r:=nn-1;
  while l<r do begin
    for j:=l to r-1 do
      if IsLess(a[j+1],a[j]) then begin
        n:=j; Swp(a[j+1],a[j]);
      end;
    r:=n;
    for j:=r downto l+1 do
      if IsLess(a[j],a[j-1]) then begin
        n:=j; Swp(a[j],a[j-1]);
      end;
    l:=n;
  end;
end;
 
const
  nt=10; nm=250; W=6; D=1;
  n: array [0..2] of TElement = (10, 50, nm);
var
  a: array [0..nm-1] of TElement;
  i, j, k: Integer;
begin
  Randomize;
  for i:=Low(n) to High(n) do begin
    CCmp:=0; CXch:=0;
    for j:=1 to nt do begin
      for k:=0 to n[i]-1 do a[k]:=-10+Random(21);
      ShakerSort(a,n[i]);
    end;
    WriteLn('Длина: ',n[i]:4,' Попыток: ',nt,
      ' Средние: обменов ',CXch/nt:W:D,' сравнений ',CCmp/nt:W:D);
  end;
  Write('Нажмите Enter...'); ReadLn;
end.
Добавлено через 2 минуты
Цитата Сообщение от Puporev Посмотреть сообщение
Так вроде нужно
Хм, стало быть про сравнения где-то еще на глаза попалось, а в этом задании действительно не нужно. Ступил-с
Ок, пусть остается для истории...
0
Модератор
62965 / 46969 / 32371
Регистрация: 18.05.2008
Сообщений: 113,838
28.02.2018, 07:52 7
Цитата Сообщение от bormant Посмотреть сообщение
про сравнения где-то еще на глаза попалось
Так в названии темы.
0
bormant
28.02.2018, 15:35
  #8

Не по теме:

Puporev,
можно подумать это название написал ТС ;)
Короче говоря, сам себя запутал :D

0
Модератор
62965 / 46969 / 32371
Регистрация: 18.05.2008
Сообщений: 113,838
28.02.2018, 15:37 9
bormant, Глянь на досуге мое горе в этой теме.
Сделать калькулятор матриц (сложение, вычитание, умножение)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.02.2018, 15:37

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Программа подсчёта количества обменов и сравнений алгоритма сортировки вставками
Нужно написать программу со счётчиками,которые выводят числа,которые обозначают количества обменов...

Количество обменов и сравнений в HeapSort
Всем доброго времени суток! :) Помогите, пожалуйста, разобраться с задачей. Мне нужно подсчитать...

Сортировка вставками: количество сравнений и обменов
реализация сортировки вставками где поставить счетчики сравнения и обменов ? вот код: //...

Быстрая сортировка: посчитать количество сравнений и обменов
помогите, пожалуйста ) нужно посчитать количество сравнений и обменов в алгоритме &quot;быстрой&quot;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.