Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Общие вопросы > Метод пузырька

Автор: Delphist 27.10.2008, 16:41

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

Код


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;

Автор: morpheyushka 27.10.2008, 17:02

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

Код


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

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

)

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

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

Автор: morpheyushka 27.10.2008, 17:17

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

)

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

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

Автор: Delphist 27.10.2008, 17:21

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

)

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

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

Автор: morpheyushka 27.10.2008, 17:31

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

)

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

Я знаю

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

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

Автор: Poseidon 28.10.2008, 09:34

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

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

Автор: Mayk 28.10.2008, 09:43

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

)

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

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

Автор: Poseidon 28.10.2008, 09:49

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

)

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

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

Автор: THandle 28.10.2008, 09:52

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

Ну что ж... Решил потестировать сортировочки 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 раза быстрее.
А вообще, в связи с недавним http://forum.vingrad.ru/forum/topic-231619.html, из всех тестируемых мною сортировок было выявлено следующее:

на маленьких массивах(до 50 элементов, примерно) лучше всего себя показывает сортировка поиском http://forum.vingrad.ru/faq/topic-201072.html, а на больших - быстрая сортировка.

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

Код

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

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

Автор: THandle 28.10.2008, 11:09

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

Автор: maFFin 15.9.2010, 13:10

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

Автор: THandle 15.9.2010, 14:09

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

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

...