сравнительный анализ методов сортировки целочисленных массивов

← →
Freak © (2008-05-05 11:02) [0]

уважаемые, может кто чего сказать ?
может кто-то это уже делал, или есть примеры?

задача: разработать приложение для Windows в среде Delphi (c 2005-го),
реализующее сортировку массивов следующими прямыми методами:
- прямого включения;
- двоичного включения;
- прямого выбора;
- прямого обмена;
- пузырьковой сортировки;
- шейкерной сортировки;

специальные требования:
1. исходные данные для тестирования приложения подготовить в текстовых файлах.
2. результаты тестирования представить в элементах диалоговых форм.
3. каждый метод оформить в виде подпрограммы, включенной в модуль, не связанной с формой.

сложности следующие:
как реализуются эти методы сортировки на Delphi?
есть ли примеры процедур.
сравнение методов - каким образом реализовать сравнение - таймер какой-нибудь прикручивать?
тогда как это делать ?

← →
Kolan © (2008-05-05 11:06) [1]

Если тебе ехать, то бери QuickSort.

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

← →
DrPass © (2008-05-05 11:18) [2]

> сложности следующие:
> как реализуются эти методы сортировки на Delphi?
> есть ли примеры процедур

Слушай, когда я учился, у нас в группе даже девочки-блондинки смогли потратить время и самостоятельно написать такую программу, причем не на Delphi, а еще на Турбо-Паскале. Разберись и ты сам, а?

← →
Anatoly Podgoretsky © (2008-05-05 11:21) [3]

> Kolan (05.05.2008 11:06:01) [1]

А код?

← →
palva © (2008-05-05 11:22) [4]

Часто используют такой критерий эффективности сортировки как количество сравнений. То есть внутрь реализации методов надо вставить счетчик. Можно еще отдельно подсчитывать записи и чтения. Это важно, если запись/чтение дорого обходится, например, алгоритм используется для сортировки секторов дискеты.

← →
Freak © (2008-05-05 11:33) [5]

> Kolan ©
> Если тебе ехать, то бери QuickSort.Если шашечки, то береш
> описания всех алгоритмов, реализуешь их, выбираешь критерий
> сравнения (например время) и сравниваешь.

пасиб, Threads уже использую, этого не хватает

> DrPass ©
>Слушай, когда я учился,
> у нас в группе даже девочки-блондинки смогли потратить
> время и самостоятельно написать такую программу, причем
> не на Delphi, а еще на Турбо-Паскале. Разберись и ты сам,
> а?

угу, пыхчу...

← →
Григорьев Антон © (2008-05-05 11:45) [6]

http://algolist.manual.ru/ - вторая группа в первой колонке как раз про сортировку

← →
Anatoly Podgoretsky © (2008-05-05 12:07) [7]

> palva (05.05.2008 11:22:04) [4]

Вообще мне до лампочки склько операций сравнения, интереснее какой быстрее работает. И все равно попугаи, на этом массиве один, а на другом другой. Тот же пузырек даст фору быстрой сортировке на отсортированом массиве.

← →
Freak © (2008-05-05 12:34) [8]

> Григорьев Антон © (05.05.08 11:45) [6]
> http://algolist.manual.ru/ - вторая группа в первой колонке
> как раз про сортировку

пасиб, ценное приобретеньице

> palva © (05.05.08 11:22) [4]
> Часто используют такой критерий эффективности сортировки
> как количество сравнений. То есть внутрь реализации методов
> надо вставить счетчик. Можно еще отдельно подсчитывать записи
> и чтения. Это важно, если запись/чтение дорого обходится,
> например, алгоритм используется для сортировки секторов
> дискеты.

поскольку пример учебный, думаю, подсчет времени одного отсортированного массива разными способами достаточен,
про счетчик итераций это мысль, спасибо ;)

> Anatoly Podgoretsky © (05.05.08 12:07) [7]
Тот же пузырек даст фору быстрой сортировке на отсортированом
> массиве.

думаю такое упрощение не интересно рассматривать ;)

← →
Jeer © (2008-05-05 12:52) [9]

> думаю такое упрощение не интересно рассматривать ;)

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

Как раз для тебя написан такой софт:
http://slil.ru/25757397

← →
guav © (2008-05-05 12:52) [10]

> думаю такое упрощение не интересно рассматривать ;)

Почему ? Разные алгоритмы по-разному зависят от исходных данных.
Вот QuickSort тоже хорошо работает на отсортированных массивах, также хорошо на отсторированных обратно требуемому порядку, но худший случай у него хуже merge sort.
Вот тут есть сравнение http://en.wikipedia.org/wiki/Sorting_algorithm#List_of_sorting_algorithms

← →
Freak © (2008-05-05 13:00) [11]

> Jeer ©
> > думаю такое упрощение не интересно рассматривать ;)Зря
> так думаешь, степень отсортированности может быть разной.
> Как раз для тебя написан такой софт:http://slil.ru/25757397

то что надо, в моем случае все гораздо проще должно быть,
лишь бы были исходники и мои методы сортировки ;)

> guav ©
> > думаю такое упрощение не интересно рассматривать ;)Почему
> ? Разные алгоритмы по-разному зависят от исходных данных.
> Вот QuickSort тоже хорошо работает на отсортированных массивах,
> также хорошо на отсторированных обратно требуемому порядку,
> но худший случай у него хуже merge sort.Вот тут есть сравнение
> http://en.wikipedia.org/wiki/Sorting_algorithm#List_of_sorting_algorithms

дельно, тут и оценка итераций,
про упрощение - задача учебная,
некоторыми моментами можно принебречь

← →
Anatoly Podgoretsky © (2008-05-05 13:03) [12]

> Freak (05.05.2008 12:34:08) [8]

Думаю, что стоит рассматривать, поскольку речь о сравнение. Иначе подбираем такие данные, что преимущество получил один конкретный метод.
Методика испытаний важнее самих испытаний. Иначе нет никаких оснований верить тестам.

← →
Freak © (2008-05-05 13:15) [13]

> Anatoly Podgoretsky ©
>Думаю, что стоит рассматривать,
> поскольку речь о сравнение. Иначе подбираем такие данные,
> что преимущество получил один конкретный метод.Методика
> испытаний важнее самих испытаний. Иначе нет никаких оснований
> верить тестам.

конечно так, но в данной работе берем генератор случайных чисел,
генерим в файл n-целочисленных значений, потом разными методами один файл сортируем и меряем. на псевдослучайной последовательности из
ста чисел, на одной для всех методов сравнение корректно ?

← →
Anatoly Podgoretsky © (2008-05-05 13:25) [14]

> Freak (05.05.2008 13:15:13) [13]

Ни в коей мере, это вообще попугай получается.
Для реальных данных есть закономерности, для генераторов есть различные распределения.
Методика должна учитывать это и работать с разными наборами тестовых данных, в том числе и отсортированые в прямом и в обратном порядке.
Не маловажна и длина последовательности данных для теста.
Некоторые дают реальное ускорение только на больших массивах, другие наоборот.

Тестирование это отдельная наука. Конечно для учебных целей и так сойдет, там вообще не важна степень достоверности результата.

← →
Jeer © (2008-05-05 14:37) [15]

> лишь бы были исходники и мои методы сортировки ;)

Как я полагаю, твоих методов сортировки человечество не скоро дождется:)
Исходники - это чей-то конкретный труд на основе труда алгоритмистов.

Либо покупаешь, либо сам, либо изначально это opensource.
Выбор за тобой.

То, что тебе показано - тест-приложение методов (порядка 20) сортировки с возможностью выбора различных моделей исходных данных.
Ты даже не представляешь, похоже, сколько их в реальности возникает.

← →
Freak © (2008-05-05 14:43) [16]

> Jeer ©
> > лишь бы были исходники и мои методы сортировки ;)Как я
> полагаю, твоих методов сортировки человечество не скоро
> дождется:)Исходники - это чей-то конкретный труд на основе
> труда алгоритмистов.Либо покупаешь, либо сам, либо изначально
> это opensource.Выбор за тобой.То, что тебе показано - тест-
> приложение методов (порядка 20) сортировки с возможностью
> выбора различных моделей исходных данных.Ты даже не представляешь,
> похоже, сколько их в реальности возникает.

конечно не представляю, я программировать не умею,
просто я ожидал нечто вроде :

метод пузырька это:
template<class T>
void bubbleSort(T a[], long size) {
long i, j;
T x;

for( i=0; i < size; i++) { // i - номер прохода
for( j = size-1; j > i; j-- ) { // внутренний цикл прохода
if ( a[j-1] > a[j] ) {
x=a[j-1]; a[j-1]=a[j]; a[j]=x;
}
}
}
}

с таким я ещё более-менее разберусь ;)

У нас форум по Дельфи

Переводи на Дельфи, сложного ничего в этом нет. Иначе это будет поводом для перевода в прочее. Этот форум тематический.

коллеги подсказали -

Метод "пузырька".

procedure IntSort(var a: array of Integer);
var i,c,n: Integer; L: boolean;
begin
n:= Length(a);
if n<2 then exit;
repeat
L:= true;
for i:= 0 to n-2 do
if a[i]>a[i+1] then
begin
c:= a[i]; a[i]:= a[i+1]; a[i+1]:= c; L:= false;
end;
until L;
end;

а как с остальными ?

> а как с остальными ?

а что с остальными ?

а с остальными знакомые девочки-блондинки DrPass"а подскажут :)

> Palladin ©
> а с остальными знакомые девочки-блондинки DrPass"а подскажут
> :)

ох, мне только девочек-блондинок не хватает, за рулём газели с черными номерами ;))))))))

сравнительный анализ методов сортировки целочисленных массивов Найти похожие ветки