Посчитать количество действий в сортировке Хоара

@semakk · Регистрация: 19.05.2010

Студворк — интернет-сервис помощи студентам

Программа сравнения эффективности сортировок Хоара и Пузырька
Подскажите куда сунуть счетчики в сортировке Хоара,ибо куда не совал выдает слишком мало что не соответствует действительности(рассчетам по бумажке), в пузырьке всё ок вроде.

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
75
76
77
78
79
80
81
82
83
84
uses crt;
Const N=8;
Type
Mas=array[1..n] of integer;
var
z: mas;
a: mas;
k,i,j,tmp,ncomp,ncopy: integer;
 
function Part(l,r: integer):integer;
var v, i, j, b: integer;
begin
ncomp:=0;
ncopy:=0;
V:=a[r];
I:=l-1;
j:=r;
repeat
repeat
dec(j) ;
until (a[j]<=v) or (j=i+1);
repeat
inc(i)  ;
until (a[i]>=v) or (i=j-1);
b:=a[i];
a[i]:=a[j];
a[j]:=b;
until i>=j;
a[j]:=a[i];
a[i]:= a[r];
a[r]:=b;
part:=i;
end;
procedure QuickSort(l,t: integer);
var i: integer;
begin
if l<t then
begin
i:=part(l, t);
QuickSort(l,i-1);
QuickSort(i+1,t);
end;
end;
 
begin
clrscr;
for k:=1 to 8 do
begin
readln(a[k]);z[k]:=a[k];
end;
QuickSort(1,n);
writeln;
writeln('вывод значений методом Хоара comp= ',ncomp,' ncopy= ',ncopy);
 
 
ncomp:=0; //число сравнений (compare)
ncopy:=0; //число копирований (copy)
for k:=1 to n do
write(a[k]:4);
writeln;
 
for i:=7 downto 1 do
    for j:=1 to i do
        begin
        inc(ncomp);
        if z[j]>z[j+1] then
            begin
               inc(ncopy);
               tmp:=z[j];
               z[j]:= z[j+1];
                inc(ncopy);
               z[j+1]:=tmp;
 
 
            end;
        end;
 
write('вывод значений пузырьком comp= ',ncomp,' ncopy= ',ncopy);
for i:=1 to n do
write(z[i]:4);
writeln;
 
 
end.

@Напильнег · 29.11.2010, 19:12

Сообщение от semakk

Подскажите куда сунуть счетчики в сортировке Хоара,ибо куда не совал выдает слишком мало что не соответствует действительности(рассчетам по бумажке), в пузырьке всё ок вроде.

Ты бы еще другое место в дырку сунул, мать твою! (Ком. х/ф "Буря в стакане")

В пузырьке у тебя не O'k - я тебе по другому показывал. Впрочем, не важно - лучше считать перестановки, а не копирования, так что начинаем с чистого листа.

Увеличения счетчика сравнений надо производить перед сравнением элементов (т.к. после сравнения процесс может ветвиться или там вообще не будет места, как в твоем случае и есть. Значится, сравнения элементов у тебя происходят в условии циклов repeat-until в функции part, соответственно перед until счетчик и увеличиваем. Перестановки считаем как обычно, во время перестановок:

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
var
  ncomp, nrrng: longint;
 
function Part(l, r: integer): integer;
  var
    v, b: integer;
    i, j: integer;
  begin
    v:=a[r];
    i:=l-1;
    j:=r;
    repeat
      repeat
        dec(j);
        inc(ncomp); //!!!
        until (a[j]<=v) or (j=i+1);
      repeat
        inc(i);
        inc(ncomp); //!!!
        until (a[i]>=v) or (i=j-1);
      inc(nrrng); //!!!
      b:=a[i];
      a[i]:=a[j];
      a[j]:=b;
      until (i>=j);
    inc(nrrng); //!!!
    a[j]:=a[i];
    a[i]:=a[r];
    a[r]:=b;
    part:=i;
  end;

Перед вызовом сортировки не забываем обнулить счетчики:

Pascal
1
2
3
4
5
  //быстрая сортировка
  ncomp:=0; //число сравнений (compare)
  nrrng:=0; //число перестановок (rearrangement)
 
  QuickSort(1, n);

@semakk · 30.11.2010, 19:58 **[ТС]**

Напильник, все равно шайтан какойто происходит) просто тупо уже вторую неделю сижу над этой лабой.
криво считает всё( по бумажке не сходится, в Хоаре часто выдает счетчики =2 =2, хотя массив из 10 чисел,как за 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
uses crt;
Const N=10;
Type
Mas=array[1..n] of integer;
var
z: mas;
a: mas;
k,i,j,tmp,ncomp,ncopy: integer;
 
function Part(l,r: integer):integer;
var v, i, j, b: integer;
begin
V:=a[r];
I:=l-1;
j:=r;
ncomp:=0;
ncopy:=0;
repeat
repeat
dec(j) ;
inc(ncomp);
until (a[j]<=v) or (j=i+1);
repeat
inc(i);
inc(ncomp);
until (a[i]>=v) or (i=j-1);
inc(ncopy);
b:=a[i];
a[i]:=a[j];
a[j]:=b;
until i>=j;
inc(ncopy);
a[j]:=a[i];
a[i]:= a[r];
a[r]:=b;
part:=i;
end;
 
procedure QuickSort(l,t: integer);
var i: integer;
begin
if l<t then
begin
i:=part(l, t);
QuickSort(l,i-1);
QuickSort(i+1,t);
end;
end;
 
begin
clrscr;
for k:=1 to N do
begin
readln(a[k]);z[k]:=a[k];
end;
ncomp:=0;
ncopy:=0;
QuickSort(1,n);
writeln;
writeln('вывод значений методом Хоара comp= ',ncomp,' ncopy= ',ncopy);
for k:=1 to n do
write(a[k]:4);
writeln;
for i:=N-1 downto 1 do
for j:=1 to i do
begin
inc(ncomp);
if z[j]>z[j+1] then
begin
inc(ncopy);
tmp:=z[j];
z[j]:=z[j+1];
inc(ncopy);
z[j+1]:=tmp;
end;
end;
write('вывод значений пузырьком comp= ',ncomp,' ncopy= ',ncopy);
for i:=1 to n do
write(z[i]:4);
writeln;
end.

@Напильнег · 30.11.2010, 23:06

Вдумчиво сравни ту функцию part, что я запостил, с тем, что у тебя.

@semakk · 01.12.2010, 10:20 **[ТС]**

сейчас, в этой процедуре, пишет количество перестановок не правильно, при вводе 1234 должно быть 0

@Напильнег · 01.12.2010, 11:59

Подсчет идет верно, это у тебя реализация part такая, что делает лишние перестановки. Найди реализацию с выбором среднего элемента в качестве базового.

Новые блоги и статьи Все статьи Все блоги /
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .

@Напильнег 481 / 119 / 17 Регистрация: 30.09.2010 Сообщений: 473
	30.11.2010, 23:06
	Вдумчиво сравни ту функцию part, что я запостил, с тем, что у тебя. 0

@semakk 24 / 24 / 13 Регистрация: 19.05.2010 Сообщений: 151
	01.12.2010, 10:20 [ТС]
	сейчас, в этой процедуре, пишет количество перестановок не правильно, при вводе 1234 должно быть 0 0

@Напильнег 481 / 119 / 17 Регистрация: 30.09.2010 Сообщений: 473
	01.12.2010, 11:59
	Подсчет идет верно, это у тебя реализация part такая, что делает лишние перестановки. Найди реализацию с выбором среднего элемента в качестве базового. 0