Вопрос по скороти сортировки:

[Vitaly1]

Какой метод сортировки быстрее:
1)

for i=1 to n-1
for j=i+1 to n
if a(i)<a(j) then
s=a(i)
a(i)=a(j)
a(j)=s
end if
next j
next i


2)

for i=1 to n-1
max= a(i)
k=i
for j=i+1 to n
if max<a(j) then
max= a(j)
k = j
end if
next j
a(k)=a(i)
a(i) = max
next i


Я знаю кокой быстрей, и почему! А вы знаете?...

[Amed]

Ну, ясно что второй метод быстрее, скорее всего, из-за того, что i-тый элемент массива сохраняется в отдельную переменную...
А вообще - это стандартный "пузырёк"

[Vitaly1]

Удивительно что на этот вопрос ответил только один человек. Второй вариант действительно быстрее, проверено опытом. Я скажу как я предполагаю почему, а другие, пусть выскажут свое мнение.

В первом варианте, при одном обмене между ячейками массива на каждом шаге используется три оператора присвоения. Во втором варианте на каждом цикле J используется только два оператора присвоения, но есть еще два оператора до цила J и после. Таким образом, при двух обменах в обоих алгоритмах выполнятся шесть операторов присваивания, но начиная с третьего объмена, во втором алгоритме будет выполненно на каждом новом цикле на один обмен меньше, что и приведет к более быстрой сортировки достаточно неупорядочных данных. Я прав, или нет???

[Krasavica]

Vitaly1
Немного подкорректировала и написала на Delphi эти алгоритмы
практически одинаковы. Первый обогнал на 3ms при
сортировке 1 млн элементов. Тестировала на Athlon 1600XP+.

Amed
Простите, а можно у вас спросить, что такое "пузырёк"?

[Vitaly1]

Метод "пузырька" это дурацкое название одного из наиболее долгого метода сортировки, который выше не указан, вот он:

for i=1 to n-1
for j=1 to n-1
if a(j)<a(j+1) then
s=a(j)
a(j)=a(j+1)
a(j+1)=s
end if
next j
next i

"Пузырек" потому, что самый "легкий" элемент массива "всплывает" (перемещается в старшую по индексу ячейку массива)


Что значит немного подкорректировала алгоритмы? Там нечего корректировать! Второй алгоритм работает ощутимо быстрее первого, если данные достаточно перепутанны!

[X-BOND]

Каждый метод сортировки имеет свои достоинства.
"Пузырек" самый медленный и самый простой
А вообще один метод быстро отсортирует небольшой массив, а при очень большом количестве элементов быстрее справится другой.
Всегда нужен компромис

[Oxygen]

Насколько мне известно, самый быстый метод - это метод быстрой сортировки, у меня где-то была реализация, только на С++. Переводить очень уж лень. Если нужно очень, я могу кинуть, если у кого есть на VB киньте пожалуйста. А эти методы ИМХО для больших объемов информации очень уж медленные.

[Vitaly1]

Конечно кинь, посмотрим, что за метод.

[GSerg]

http://bbs.vbstreets.ru/viewtopic.php?p=17085#17085

[Oxygen]

Вот еще парочка алгоритмов сортировки.

[Krasavica]

В этом разделе будет рассмотрен знаменитый алгоритм «быстрой» сортировки, по праву считающийся самым быстрым среди неспециализированных алгоритмов сортировки. Для сравнения мы также рассмотрим один из алгоритмов сортировки, имеющих более низкую эффективность, но и более простых алгоритмов – сортировку вставками.

Читайте дальше...

[Sirik]

А почему бы не воспользоваться таким методом:

Код: Выделить всё

for i=1 to n-1
for j=i+1 to n
if a(i)<a(j) then
  s=a(i): a(i)=a(j):a(j)=s
end if
next
next


Быстрей чем стандартный "пузырёк", я всегда его юзаю.

[gaidar]

Товарищи, посмотрите на algolist.manual.ru там есть алгоритмы всех популярных сортировок. На Pascal, конечно.

[Amed]

А почему бы не воспользоваться таким методом:

Код: Выделить всё

for i=1 to n-1
for j=i+1 to n
if a(i)<a(j) then
  s=a(i): a(i)=a(j):a(j)=s
end if
next
next


Быстрей чем стандартный "пузырёк", я всегда его юзаю.

/me катается по полу .
Это и есть "пузырёк"

[Sirik]

/me катается по полу .
Это и есть "пузырёк"

Так то воно, але трішечки не так.

Эта разновидность "пузырька"!!! И она быстрее СТАНДАРТНОГО "пузырька". Я же не отрицал, что это вобще не "пузырёк"?!?
Просто читать надо внимательно.

[Vitaly1]

Ну если уж вам пузырек злочастный нравится, пожалуйс то, некоторое усовершенствования пузырька:

Код: Выделить всё

do
flag = true
for j=1 to n-1
if a(j)<a(j+1) then
flag=false
s=a(j)
a(j)=a(j+1)
a(j+1)=s
end if
next j
loop until flag = true

[Ilya Vasilyev]

Ну если уж вам пузырек злочастный нравится, пожалуйс то, некоторое усовершенствования пузырька:

Что-т я не понял
1. Как ты собираешься за один проход список сортировать
2. При первом удовлетворении условия цикл останавливается

[Vitaly1]

Что-т я не понял
1. Как ты собираешься за один проход список сортировать
2. При первом удовлетворении условия цикл останавливается

Где он остановится! Если хотя бы нашлось одно соответствие а(j) <a(j+1) цикл еще раз повториться, а если на всех а(j) >=a(j+1), то массив уже отсортирован по убыванию!

[Vitaly1]

А я еще придумал, ускорение, для другого метода:

Код: Выделить всё

i=0
do
i=i+1
flag= true
for j=i+1 to n
if a(i)<a(j) then
flag=false
s=a(i)
a(i)=a(j)
a(j)=s
end if
next j
loop until flag=true

можно конечно и так:

Код: Выделить всё

for i=1 to n-1
flag= true
for j=i+1 to n
if a(i)<a(j) then
flag=false
s=a(i)
a(i)=a(j)
a(j)=s
end if
next j
if flag=true then
exit for
end if
next i

но я думаю, что в первом случаи будет быстрее, т.к. компьютер не будет проверять условие i<=n-1

[A.A.Z.]

Народ! Лучше заменить

For i = 1 To j
Next

на

i = 1
Do Until i = j
Loop

Do - Loop быстрее, чем For - Next

[Unstat]

Они одинаковы проверено при 20 элементах массива 190 операций выполняется что у первого что у второго. Вот так вот
___________________________________
http://unstat.narod.ru