Почему в сортировке расческой используют число 1.247?

@Соколиный глаз · Регистрация: 25.07.2014

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

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
const
  n = 5;
 
var
  a: array [0..n] of integer;
  i, j: integer;
 
begin
  for i := 0 to n do a[i] := Random(12);
  j := n;
  while i < i + j do
  begin
    i := 0;
    while i + j <= n do
    begin
      if a[i] > a[i + j] then
      begin
        a[i] := a[i] + a[i + j];
        a[i + j] := a[i] - a[i + j];
        a[i] := a[i] - a[i + j];
      end;
      Inc(i);
    end;
    Dec(j);
  end;
  Writeln(a);
end.

Я написал свой код и без 1.247. В чем фишка этого числа?

@Shamil1 · 04.04.2017, 23:00

Сообщение от Volobuev Ilya

В чем фишка этого числа?

Скорость сортировки зависит от функции изменения расстояния между сравниваемыми элементами. В Вашем случае это Dec в строке 24. Оптимальная функция j = (int)(j/1.247). Попробуйте и сравните различные варианты на массивах размером 50 тыс.

@Соколиный глаз · 11.04.2017, 17:55 **[ТС]**

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
const
  n = 5;
 
var
  a: array [0..n] of integer;
  i, jr: integer;
  j: real;
 
begin
  for i := 0 to n do a[i] := Random(12);
  Writeln(a);
  j := n;
  while i < i + j do
  begin
    i := 0;
    while i + j <= n do
    begin
      if a[i] > a[i + Round(j)] then
      begin
        jr := Round(j); // избавляю программу от вычислений много раз Round(j), записывая результат в переменную jr
        a[i] := a[i] + a[i + jr];
        a[i + jr] := a[i] - a[i + jr];
        a[i] := a[i] - a[i + jr];
      end;
      Inc(i);
    end;
    j := j - 1.247;
  end;
  Writeln(a);
end.

Добавлено через 14 минут
* j := j / 1.247;
там так надо

@Shamil1 · 11.04.2017, 18:49

Условие в строке 13 выглядит странно.
Round(j) всё равно вычисляется несколько раз - в строке 18.
Внутренний цикл может вычисляться несколько раз с одинаковым jr (2 и 3).
После завершения работы алгоритма, массив может быть не отсортированным. (При jr=1 нужно повторять проходы, пока были обмены - сортировка пузырьком).

@Соколиный глаз · 12.04.2017, 08:26 **[ТС]**

Вы хотите сказать что нужен второй цикл простого пузырька?

Добавлено через 1 минуту
Строка 18 - мой косяк

Добавлено через 15 минут
while i < i + jr do
Может так? Ну а jr вычислить сразу один раз до цикла

@Shamil1 · 12.04.2017, 09:26

Условие i < i + jr тождественно 0 < jr.

Добавлено через 2 минуты

Сообщение от Volobuev Ilya

Вы хотите сказать что нужен второй цикл простого пузырька?

Да.
В принципе, можно объединить два алгоритма, добавив "or swapped" в условие цикла, но это будет менее эффективно.

@Соколиный глаз · 12.04.2017, 10:18 **[ТС]**

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
const
  n = 5;
 
var
  a: array [0..n] of integer;
  i, jr: integer;
  j: real;
 
begin
  for i := 0 to n do a[i] := Random(12);
  Writeln(a);
  j := n;
  jr := Round(j);
  while i < i + jr do
  begin
    i := 0;
    jr := Round(j);
    while i + j <= n do
    begin
      if a[i] > a[i + Round(j)] then
      begin
        a[i] := a[i] + a[i + jr];
        a[i + jr] := a[i] - a[i + jr];
        a[i] := a[i] - a[i + jr];
      end;
      Inc(i);
    end;
    j := j / 1.247;
  end;
  for i := 0 to n do
  begin
    for jr := 0 to i - 1 do
    begin
      if a[jr] > a[jr + 1] then
      begin
        a[jr] := a[jr] + a[jr + 1];
        a[jr + 1] := a[jr] - a[jr + 1];
        a[jr] := a[jr] - a[jr + 1];
      end;
    end;
  end;
  Writeln(a);
end.

Добавлено через 4 минуты

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
  i := 0;
  swapped := false;
  while swapped = false do
  begin
    swapped := true;
    if a[jr] > a[jr + 1] then
    begin
      a[jr] := a[jr] + a[jr + 1];
      a[jr + 1] := a[jr] - a[jr + 1];
      a[jr] := a[jr] - a[jr + 1];
      swapped := false;
    end;
  end;

Ну или так

@Shamil1 · 12.04.2017, 16:23

У Вас по-прежнему:

1. i + Round(j) в строке 20

2. Если, например, j = 3.4, то jr два раза подряд будет равно 3.

Дополнительно:
Формально это не ошибка, но swapped имеет смысл "был обмен". Нужно либо менять "знак", либо переименовывать.

Вот мой вариант (не тестировал - возможны ошибки):

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
procedure combSort(var a: TIntArray);
    var
        i, j, gap, temp: integer;
        swapped: boolean;
    begin
        gap := length(a);
        while (gap > 1) do
        begin
            for i := 1 to length(a) - gap do
                if a[i] > a[i+gap] then
                begin
                    temp := a[i];
                    a[i] := a[i+gap];
                    a[i+gap] := temp;
                end;
            gap := trunc(gap / 1.247);
        end;
        swapped := true;
        j := 1;
        while swapped do
        begin
            swapped := false;
            for i := 1 to length(a) - j do
                if a[i] > a[i+1] then
                begin
                    temp := a[i];
                    a[i] := a[i+1];
                    a[i+1] := temp;
                    swapped := true;        
                end;
            j := j + 1
        end;
    end;

@Соколиный глаз · 12.04.2017, 20:49 **[ТС]**

Спасибо

Добавлено через 29 секунд
Логика кода понятна

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера 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 с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,879
	11.04.2017, 18:49
	Условие в строке 13 выглядит странно. Round(j) всё равно вычисляется несколько раз - в строке 18. Внутренний цикл может вычисляться несколько раз с одинаковым jr (2 и 3). После завершения работы алгоритма, массив может быть не отсортированным. (При jr=1 нужно повторять проходы, пока были обмены - сортировка пузырьком). 0

@Соколиный глаз Alvin Seville 343 / 273 / 134 Регистрация: 25.07.2014 Сообщений: 4,537 Записей в блоге: 22
	12.04.2017, 08:26 [ТС]
	Вы хотите сказать что нужен второй цикл простого пузырька? Добавлено через 1 минуту Строка 18 - мой косяк Добавлено через 15 минут while i < i + jr do Может так? Ну а jr вычислить сразу один раз до цикла 0

@Соколиный глаз Alvin Seville 343 / 273 / 134 Регистрация: 25.07.2014 Сообщений: 4,537 Записей в блоге: 22
	12.04.2017, 20:49 [ТС]
	Спасибо Добавлено через 29 секунд Логика кода понятна 0