| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
сравнительный анализ методов сортировки целочисленных массивов
Freak © (2008-05-05 11:02:00)уважаемые, может кто чего сказать ?
может кто-то это уже делал, или есть примеры?
задача: разработать приложение для Windows в среде Delphi (c 2005-го),
реализующее сортировку массивов следующими прямыми методами:
- прямого включения;
- двоичного включения;
- прямого выбора;
- прямого обмена;
- пузырьковой сортировки;
- шейкерной сортировки;
специальные требования:
1. исходные данные для тестирования приложения подготовить в текстовых файлах.
2. результаты тестирования представить в элементах диалоговых форм.
3. каждый метод оформить в виде подпрограммы, включенной в модуль, не связанной с формой.
сложности следующие:
как реализуются эти методы сортировки на Delphi?
есть ли примеры процедур.
сравнение методов - каким образом реализовать сравнение - таймер какой-нибудь прикручивать?
тогда как это делать ?
Freak (2008-05-05 16:25:00) [1]
> Palladin ©
> а с остальными знакомые девочки-блондинки DrPass'а подскажут
> :)
ох, мне только девочек-блондинок не хватает, за рулём газели с черными номерами ;))))))))
Palladin (2008-05-05 16:18:00) [2]а с остальными знакомые девочки-блондинки DrPass'а подскажут :)
Игорь Шевченко (2008-05-05 16:13:00) [3]
> а как с остальными ?
а что с остальными ?
Freak (2008-05-05 15:56:00) [4]коллеги подсказали -
Метод "пузырька".
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;
а как с остальными ?
app (2008-05-05 15:21:00) [5]Переводи на Дельфи, сложного ничего в этом нет. Иначе это будет поводом для перевода в прочее. Этот форум тематический.
Freak (2008-05-05 15:18:00) [6]
> Anatoly Podgoretsky © (05.05.08 15:13) [17]
> У нас форум по Дельфи
прошу простить, за сишный пример :)
Anatoly Podgoretsky (2008-05-05 15:13:00) [7]У нас форум по Дельфи
Freak (2008-05-05 14:43:00) [8]
> 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;
}
}
}
}
с таким я ещё более-менее разберусь ;)
Jeer (2008-05-05 14:37:00) [9]
> лишь бы были исходники и мои методы сортировки ;)
Как я полагаю, твоих методов сортировки человечество не скоро дождется:)
Исходники - это чей-то конкретный труд на основе труда алгоритмистов.
Либо покупаешь, либо сам, либо изначально это opensource.
Выбор за тобой.
То, что тебе показано - тест-приложение методов (порядка 20) сортировки с возможностью выбора различных моделей исходных данных.
Ты даже не представляешь, похоже, сколько их в реальности возникает.
Anatoly Podgoretsky (2008-05-05 13:25:00) [10]> Freak (05.05.2008 13:15:13) [13]
Ни в коей мере, это вообще попугай получается.
Для реальных данных есть закономерности, для генераторов есть различные распределения.
Методика должна учитывать это и работать с разными наборами тестовых данных, в том числе и отсортированые в прямом и в обратном порядке.
Не маловажна и длина последовательности данных для теста.
Некоторые дают реальное ускорение только на больших массивах, другие наоборот.
Тестирование это отдельная наука. Конечно для учебных целей и так сойдет, там вообще не важна степень достоверности результата.
Freak (2008-05-05 13:15:00) [11]
> Anatoly Podgoretsky ©
>Думаю, что стоит рассматривать,
> поскольку речь о сравнение. Иначе подбираем такие данные,
> что преимущество получил один конкретный метод.Методика
> испытаний важнее самих испытаний. Иначе нет никаких оснований
> верить тестам.
конечно так, но в данной работе берем генератор случайных чисел,
генерим в файл n-целочисленных значений, потом разными методами один файл сортируем и меряем. на псевдослучайной последовательности из
ста чисел, на одной для всех методов сравнение корректно ?
Anatoly Podgoretsky (2008-05-05 13:03:00) [12]> Freak (05.05.2008 12:34:08) [8]
Думаю, что стоит рассматривать, поскольку речь о сравнение. Иначе подбираем такие данные, что преимущество получил один конкретный метод.
Методика испытаний важнее самих испытаний. Иначе нет никаких оснований верить тестам.
Freak (2008-05-05 13:00:00) [13]
> Jeer ©
> > думаю такое упрощение не интересно рассматривать ;)Зря
> так думаешь, степень отсортированности может быть разной.
> Как раз для тебя написан такой софт: http://slil.ru/25757397
то что надо, в моем случае все гораздо проще должно быть,
лишь бы были исходники и мои методы сортировки ;)
> guav ©
> > думаю такое упрощение не интересно рассматривать ;)Почему
> ? Разные алгоритмы по-разному зависят от исходных данных.
> Вот QuickSort тоже хорошо работает на отсортированных массивах,
> также хорошо на отсторированных обратно требуемому порядку,
> но худший случай у него хуже merge sort.Вот тут есть сравнение
> http://en.wikipedia.org/wiki/Sorting_algorithm#List_of_sorting_algorithms
дельно, тут и оценка итераций,
про упрощение - задача учебная,
некоторыми моментами можно принебречь
guav (2008-05-05 12:52:00) [14]> думаю такое упрощение не интересно рассматривать ;)
Почему ? Разные алгоритмы по-разному зависят от исходных данных.
Вот QuickSort тоже хорошо работает на отсортированных массивах, также хорошо на отсторированных обратно требуемому порядку, но худший случай у него хуже merge sort.
Вот тут есть сравнение http://en.wikipedia.org/wiki/Sorting_algorithm#List_of_sorting_algorithms
Jeer (2008-05-05 12:52:00) [15]
> думаю такое упрощение не интересно рассматривать ;)
Зря так думаешь, степень отсортированности может быть разной.
Как раз для тебя написан такой софт:
http://slil.ru/25757397
Freak (2008-05-05 12:34:00) [16]
> Григорьев Антон © (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]
Тот же пузырек даст фору быстрой сортировке на отсортированом
> массиве.
думаю такое упрощение не интересно рассматривать ;)
Anatoly Podgoretsky (2008-05-05 12:07:00) [17]> palva (05.05.2008 11:22:04) [4]
Вообще мне до лампочки склько операций сравнения, интереснее какой быстрее работает. И все равно попугаи, на этом массиве один, а на другом другой. Тот же пузырек даст фору быстрой сортировке на отсортированом массиве.
Григорьев Антон (2008-05-05 11:45:00) [18]http://algolist.manual.ru/- вторая группа в первой колонке как раз про сортировку
Freak (2008-05-05 11:33:00) [19]
> Kolan ©
> Если тебе ехать, то бери QuickSort.Если шашечки, то береш
> описания всех алгоритмов, реализуешь их, выбираешь критерий
> сравнения (например время) и сравниваешь.
пасиб, Threads уже использую, этого не хватает
> DrPass ©
>Слушай, когда я учился,
> у нас в группе даже девочки-блондинки смогли потратить
> время и самостоятельно написать такую программу, причем
> не на Delphi, а еще на Турбо-Паскале. Разберись и ты сам,
> а?
угу, пыхчу...
palva (2008-05-05 11:22:00) [20]Часто используют такой критерий эффективности сортировки как количество сравнений. То есть внутрь реализации методов надо вставить счетчик. Можно еще отдельно подсчитывать записи и чтения. Это важно, если запись/чтение дорого обходится, например, алгоритм используется для сортировки секторов дискеты.
| |
Страницы: 