VPF::Метод пузырька - Форум программистов

Delphist

Дата 27.10.2008, 16:41 (ссылка)

(нет голосов)

Загрузка ...

Delphist Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2145
Регистрация: 3.2.2004
Где: всегда в сети

Репутация: 2
Всего: 3

Есть у меня три варианта сортировки методом пузырька, скажите, пожалуйста, какой из них наиболее быстрый и наиболее правильней.

Код


var
  i, j, p: integer;

  arr: array of integer;
  //1-ый вариант
  for i := Length(arr) - 2 downto 0 do
    for j := 0 to i do
      if arr[j] > arr[j+1] then
      begin
        p := arr[j];
        arr[j] := arr[j+1];
        arr[j+1] := p;
      end;

  //2-ой вариант
  for i := 1 to Length(arr) - 1 do
    for j := Length(arr) - 1 downto i do
      if arr[j-1] > arr[j] then
      begin
        p := arr[j-1];
        arr[j-1] := arr[j];
        arr[j] := p;
      end;

  //3-ий вариант
   n:= Length(arr)-1;
   if n < 1 then exit;
   repeat
     b:= true;
     Dec(n);
     for i:= 0 to n do
     if arr[i] > arr[i+1] then
     begin
       p:= arr[i];
       arr[i]:= arr[i+1];
       arr[i+1]:= p;
       b:= false;
     end;
   until b;

--------------------

ProcessInfo 1-ая моя программа (аналог spyxx.exe с гораздо большим функц-ом - внедрение dll в адр. простр. процесса, перехват API-функций, разбор приложения на окна мн.др).
Когда-то давным-давно использовал это...

morpheyushka

Дата 27.10.2008, 17:02 (ссылка)

(нет голосов)

Загрузка ...

Зеленый человек

Профиль
Группа: Участник
Сообщений: 563
Регистрация: 26.2.2008
Где: Киев

Репутация: 3
Всего: 8

Не одной из перечисленных реализации не помню...на сколько помню - нужно так:

Код


var
  i, j, p: integer;
  arr: array of integer;
...
  for j := 1 to High(arr) - 1 do
    for i := 0 to High(arr) - j do
      if arr[i] > arr[i + 1] then
        begin
          p := arr[i];
          arr[i] := arr[i + 1];
          arr[i + 1] := p;
        end;

--------------------

Спасибо делается вот так!!!

Delphist

Дата 27.10.2008, 17:13 (ссылка)

(нет голосов)

Загрузка ...

Delphist Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2145
Регистрация: 3.2.2004
Где: всегда в сети

Репутация: 2
Всего: 3

Цитата(morpheyushka @ 27.10.2008, 18:02

)

Не одной из перечисленных реализации не помню...на сколько помню - нужно так:

Твой вариант неправилен, для случая когда массив состоит из 2-х элементов

Это сообщение отредактировал(а) Delphist - 27.10.2008, 17:20

--------------------

morpheyushka

Дата 27.10.2008, 17:17 (ссылка)

(голосов:2)

Загрузка ...

Зеленый человек

Профиль
Группа: Участник
Сообщений: 563
Регистрация: 26.2.2008
Где: Киев

Репутация: 3
Всего: 8

Цитата(Delphist @ 27.10.2008, 17:13

)

а из моих какой быстрей?

так протестируй сам...позасекай время на одном массиве и сравни smile

--------------------

Спасибо делается вот так!!!

Delphist

Дата 27.10.2008, 17:21 (ссылка)

(голосов:3)

Загрузка ...

Delphist Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2145
Регистрация: 3.2.2004
Где: всегда в сети

Репутация: 2
Всего: 3

Цитата(morpheyushka @ 27.10.2008, 18:17

)

так протестируй сам...позасекай время на одном массиве и сравни

Твой вариант неправилен, для случая когда массив состоит из 2-х элементов

--------------------

morpheyushka

Дата 27.10.2008, 17:31 (ссылка)

(нет голосов)

Загрузка ...

Зеленый человек

Профиль
Группа: Участник
Сообщений: 563
Регистрация: 26.2.2008
Где: Киев

Репутация: 3
Всего: 8

Цитата(Delphist @ 27.10.2008, 17:21

)

Твой вариант неправилен, для случая когда массив состоит из 2-х элементов

Я знаю

Если в этом есть необходимость - то я ставил всегда проверку smile

Добавлено через 58 секунд
Зато он классно работает - он не проходит по несколько раз по отсортированной части массива

--------------------

Спасибо делается вот так!!!

Poseidon

Дата 28.10.2008, 09:34 (ссылка)

(нет голосов)

Загрузка ...

Delphi developer

Профиль
Группа: Комодератор
Сообщений: 5273
Регистрация: 4.2.2005
Где: Гомель, Беларусь

Репутация: 53
Всего: 133

Не нашел принципиальной разницы между первым и вторым вариантами. Они будут равны по скорости. Третий вариант будет быстрее, если массив не вильно рассортирован. Например массив (5,1,2,3,4) в третьем варианте будет отсртирван за один цикл, а то время как в первых вариантах надо 4 цикла (при этом в каждом из этих циклов по 4 подцикла). При этом первые два варианта будут полностью гонять циклы аже если им передать уже сортированный массив. Третий вариант проверит за один раз.

ИМХО, выбирать надо третий.

--------------------

Если хочешь, что бы что-то работало - используй написанное,
если хочешь что-то понять - пиши сам...

Mayk

Дата 28.10.2008, 09:43 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: нет
Всего: 134

Цитата(Poseidon @ 28.10.2008, 13:34

)

ИМХО, выбирать надо третий.

имхо выбирать надо quick sort. От бубл сорта вообще прока нет.

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Poseidon

Дата 28.10.2008, 09:49 (ссылка)

(нет голосов)

Загрузка ...

Delphi developer

Профиль
Группа: Комодератор
Сообщений: 5273
Регистрация: 4.2.2005
Где: Гомель, Беларусь

Репутация: 53
Всего: 133

Цитата(Mayk @ 28.10.2008, 09:43

)

имхо выбирать надо quick sort

Где ты это нашел в первм посте. Там 3 варианта и спрашивается какой лучше из этих трех! Если бы был вопрос, какой метод сортировки лучше в принципе, тогда твой ответбыл бы уместен.

--------------------

Если хочешь, что бы что-то работало - используй написанное,
если хочешь что-то понять - пиши сам...

THandle

Дата 28.10.2008, 09:52 (ссылка)

(голосов:2)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 65
Всего: 372

Копия моего поста с исходников:

Ну что ж... Решил потестировать сортировочки smile

Все тесты проводились на количестве итераций цикла = 100000 + 1.
"Время" засекалось с помощью GetTickCount.

Вот результаты:

Размерность массива = 10:

1 вариант: 62
2 вариант: 63
3 вариант: 47
Быстрая сортировка: 78

Размерность массива = 25:

1 вариант: 281
2 вариант: 297
3 вариант: 297
Быстрая сортировка: 219

Размерность массива = 50:

1 вариант: 1047
2 вариант: 1062
3 вариант: 1047
Быстрая сортировка: 485

Размерность массива = 100:

1 вариант: 4109
2 вариант: 4109
3 вариант: 4110
Быстрая сортировка: 1094

Размерность массива = 200:

1 вариант: 16922
2 вариант: 16781
3 вариант: 16672
Быстрая сортировка: 2250

Размерность массива = 500:

1 вариант: 107687
2 вариант: 106531
3 вариант: 105969
Быстрая сортировка: 6141

Из всех этих тестов напрашивается вывод - все три сортировки примерно равны, разница во времени выполнения
начинает замечаться только на больших массивах(в данном случае размером в 500 элементов). То есть самая быстрая получается 3, потом 2, потом 1.

Только не понятно зачем нужна эта сортировка пузырьками, когда быстрая сортировка уже на массиве в 100 элементов работает в 4 раза быстрее.
А вообще, в связи с недавним конкурсом, из всех тестируемых мною сортировок было выявлено следующее:

на маленьких массивах(до 50 элементов, примерно) лучше всего себя показывает сортировка поиском минимального/максимального, а на больших - быстрая сортировка.

Тест проводился с помощью такой вот незамысловатой программки:

Код

program Project1;

{$APPTYPE CONSOLE}

uses
  Windows;

const
  MAX = 500;
var
  i, j, p, n, k: integer;
  b: boolean;
  arr: Array [0..MAX - 1] of integer;
  Start, Finish: Cardinal;

procedure RandomArray;
begin
  for i := 0 to MAX - 1 do
    arr[i] := Random(1000);
end;

procedure Sort1;
begin
  for i := Length(arr) - 2 downto 0 do
    for j := 0 to i do
      if arr[j] > arr[j+1] then
      begin
        p := arr[j];
        arr[j] := arr[j+1];
        arr[j+1] := p;
      end;
end;

procedure Sort2;
begin
    for i := 1 to Length(arr) - 1 do
    for j := Length(arr) - 1 downto i do
      if arr[j-1] > arr[j] then
      begin
        p := arr[j-1];
        arr[j-1] := arr[j];
        arr[j] := p;
      end;
end;

procedure Sort3;
begin
   n:= Length(arr)-1;
   if n < 1 then exit;
   repeat
     b:= true;
     Dec(n);
     for i:= 0 to n do
     if arr[i] > arr[i+1] then
     begin
       p:= arr[i];
       arr[i]:= arr[i+1];
       arr[i+1]:= p;
       b:= false;
     end;
   until b;
end;

procedure Sort4(mine, maxe: integer);
var
  i, j, n : integer;
procedure Swap(pos1, pos2 : integer);
var
  tmp : integer;
begin
  tmp := Arr[pos1];
  Arr[pos1] := Arr[pos2];
  Arr[pos2] := tmp;
end;
begin
  if mine >= maxe then
    exit;
  n := Arr[mine];
  i := mine - 1;
  j := maxe + 1;
  while i < j do
    begin
      repeat
        inc(i);
      until Arr[i] >= n;
      repeat
        dec(j);
      until Arr[j] <= n;
    if i < j then
      swap(i, j);
   end;
  Sort4(mine, j);
  Sort4(j + 1, maxe);
end;

begin
  Randomize;
  Start := GetTickCount;
  for k := 0 to 100000 do
  begin
    RandomArray;
    Sort1;
  end;
  Finish := GetTickCount;
  WriteLn('Sort1 time: ', Finish - Start);
  Start := GetTickCount;
  for k := 0 to 100000 do
  begin
    RandomArray;
    Sort2;
  end;
  Finish := GetTickCount;
  WriteLn('Sort2 time: ', Finish - Start);
  Start := GetTickCount;
  for k := 0 to 100000 do
  begin
    RandomArray;
    Sort3;
  end;
  Finish := GetTickCount;
  WriteLn('Sort3 time: ', Finish - Start);
  Start := GetTickCount;
  for k := 0 to 100000 do
  begin
    RandomArray;
    Sort4(0, MAX - 1);
  end;
  Finish := GetTickCount;
  WriteLn('Sort4 time: ', Finish - Start);
  ReadLn;
end.

На процессоре Intel Core 2 Duo E6300 1,86x2.

Удачи =)

Poseidon

Дата 28.10.2008, 10:42 (ссылка)

(нет голосов)

Загрузка ...

Delphi developer

Профиль
Группа: Комодератор
Сообщений: 5273
Регистрация: 4.2.2005
Где: Гомель, Беларусь

Репутация: 53
Всего: 133

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

--------------------

Если хочешь, что бы что-то работало - используй написанное,
если хочешь что-то понять - пиши сам...

THandle

Дата 28.10.2008, 11:09 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 65
Всего: 372

Poseidon, согласен. Тест немного некорректен, но все таки общие позиции показывает.

maFFin

Дата 15.9.2010, 13:10 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 15.9.2010

Репутация: нет
Всего: нет

подскажите, какой из этих кодов самый тупой и самый простой? мне нужно с двумя For-ами где один до N а другой до N-1
спасибо

THandle

Дата 15.9.2010, 14:09 (ссылка)

(нет голосов)

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

Репутация: 65
Всего: 372

maFFin, думаю вот это:

http://forum.vingrad.ru/faq/topic-200441.html

...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Delphi: Общие вопросы \| Следующая тема »