Форум: "Основная";
Текущий архив: 2004.04.04;
Скачать: [xml.tar.bz2];
Вниз
Сортировка массива Найти похожие ветки
← →
Дас Виндовс 45 (2004-03-11 12:21) [0]Какой алгоритм самый оптимальный для сортировки целочисленного массива?
← →
Я © (2004-03-11 12:26) [1]Оптимальность алгоритмов сортировки определяется по многим параметрам:
- скорость
- используемый объем памяти
- устойчивость сортировки
- количество проходов (частично коррелируется со скоростью)
- и т.д.
Все аспекты сортировки хорошо изложены в работе Дональда Э. Кнута "Искусство программирования", том 3 (2?) "Сортировка и поиск".
← →
kaif © (2004-03-11 12:30) [2]Оптимальный алгоритм от характера самих данных тоже зависит. Например, если массив "почти упорядочен", то обычно самая меленная - пузырьковая сртировка может оказаться самой быстрой.
← →
Я © (2004-03-11 12:37) [3]2 kaif
Спорим, я знаю сортировку медленнее "пузырька"?
Шутка :)
← →
Игорь Шевченко © (2004-03-11 12:40) [4]А можно не мучиться и использовать QuickSort, она в большинстве случаев оправдывает свое название.
← →
kaif © (2004-03-11 12:44) [5]2 Игорь Шевченко © (11.03.04 12:40) [4]
Алгоритм QuickSort я, кажется знаю (перестановка групп). Хотя, может, я и ошибаюсь. А что, есть реализация в виде функции в Delphi или в API? Если есть, подскажите, пожалуйста, может и мне пригодится (иногда нужно бывает)
← →
Игорь Шевченко © (2004-03-11 13:16) [6]kaif © (11.03.04 12:44)
В виде API есть на NT-платформе в ntdll (там почти все наиболее употребительные функции из сишной run-time библиотеки)
В VCL в классе TStringList есть метод QuickSort
← →
Дас Виндовс 45 (2004-03-11 13:20) [7]Можно пример QuickSort?
← →
Тимохов © (2004-03-11 13:22) [8]можно
Tlist + f1 -> methods -> sort -> example.
← →
PVOzerski © (2004-03-11 13:31) [9]Интересно, я сейчас глянул через QuickView на crtdll.dll в NT4 и нашел экспортируемую ф-цию qsort. Это, часом, не оно? А если оно, так должно быть на всех win32-платформах, по логике?
← →
Игорь Шевченко © (2004-03-11 13:36) [10]PVOzerski © (11.03.04 13:31)
Оно :) Только и calling convention у нее сишные
← →
kaif © (2004-03-11 13:36) [11]2 Игорь Шевченко © (11.03.04 13:16) [6]
StringList-овский Sort я обычно и использую. Но это сортировка строк. Иногда хотелось бы иметь более быструю сортировку - для целых чисел. Спасибо за информацию. Если что - буду искать функцию в ctrldll.
← →
PVOzerski © (2004-03-11 13:43) [12]> Только и calling convention у нее сишные
Это-то не страшно, надо будет при случае попробовать функцию в деле.
← →
ZrenBy © (2004-03-11 13:44) [13]classes.pas
procedure QuickSort ...
Кстати. Вопрос к математикам.
Насколько глубока может быть рекурсия в самом наихудшем варианте?
А вообще то есть и итерационная реализация QS
← →
Игорь Шевченко © (2004-03-11 13:45) [14]kaif © (11.03.04 13:36)
#include <cruntime.h>
#include <stdlib.h>
#include <search.h>
/* prototypes for local routines */
static void __cdecl shortsort(char *lo, char *hi, unsigned width,
int (__cdecl *comp)(const void *, const void *));
static void __cdecl swap(char *p, char *q, unsigned int width);
/* this parameter defines the cutoff between using quick sort and
insertion sort for arrays; arrays with lengths shorter or equal to the
below value use insertion sort */
#define CUTOFF 8 /* testing shows that this is good value */
/***
*qsort(base, num, wid, comp) - quicksort function for sorting arrays
*
*Purpose:
* quicksort the array of elements
* side effects: sorts in place
*
*Entry:
* char *base = pointer to base of array
* unsigned num = number of elements in the array
* unsigned width = width in bytes of each array element
* int (*comp)() = pointer to function returning analog of strcmp for
* strings, but supplied by user for comparing the array elements.
* it accepts 2 pointers to elements and returns neg if 1<2, 0 if
* 1=2, pos if 1>2.
*
*Exit:
* returns void
*
*Exceptions:
*
*******************************************************************************/
/* sort the array between lo and hi (inclusive) */
void __cdecl qsort (
void *base,
unsigned num,
unsigned width,
int (__cdecl *comp)(const void *, const void *)
)
{
char *lo, *hi; /* ends of sub-array currently sorting */
char *mid; /* points to middle of subarray */
char *loguy, *higuy; /* traveling pointers for partition step */
unsigned size; /* size of the sub-array */
char *lostk[30], *histk[30];
int stkptr; /* stack for saving sub-array to be processed */
/* Note: the number of stack entries required is no more than
1 + log2(size), so 30 is sufficient for any array */
if (num < 2 || width == 0)
return; /* nothing to do */
stkptr = 0; /* initialize stack */
lo = base;
hi = (char *)base + width * (num-1); /* initialize limits */
/* this entry point is for pseudo-recursion calling: setting
lo and hi and jumping to here is like recursion, but stkptr is
prserved, locals aren"t, so we preserve stuff on the stack */
recurse:
size = (hi - lo) / width + 1; /* number of el"s to sort */
/* below a certain size, it is faster to use a O(n^2) sorting method */
if (size <= CUTOFF) {
shortsort(lo, hi, width, comp);
}
else {
/* First we pick a partititioning element. The efficiency of the
algorithm demands that we find one that is approximately the
median of the values, but also that we select one fast. Using
the first one produces bad performace if the array is already
sorted, so we use the middle one, which would require a very
wierdly arranged array for worst case performance. Testing shows
that a median-of-three algorithm does not, in general, increase
performance. */
mid = lo + (size / 2) * width; /* find middle element */
swap(mid, lo, width); /* swap it to beginning of array */
/* We now wish to partition the array into three pieces, one
consisiting of elements <= partition element, one of elements
equal to the parition element, and one of element >= to it. This
is done below; comments indicate conditions established at every
step. */
loguy = lo;
higuy = hi + width;
/* Note that higuy decreases and loguy increases on every iteration,
so loop must terminate. */
for (;;) {
/* lo <= loguy < hi, lo < higuy <= hi + 1,
A[i] <= A[lo] for lo <= i <= loguy,
A[i] >= A[lo] for higuy <= i <= hi */
do {
loguy += width;
} while (loguy <= hi && comp(loguy, lo) <= 0);
/* lo < loguy <= hi+1, A[i] <= A[lo] for lo <= i < loguy,
either loguy > hi or A[loguy] > A[lo] */
do {
higuy -= width;
} while (higuy > lo && comp(higuy, lo) >= 0);
/* lo-1 <= higuy <= hi, A[i] >= A[lo] for higuy < i <= hi,
either higuy <= lo or A[higuy] < A[lo] */
if (higuy < loguy)
break;
/* if loguy > hi or higuy <= lo, then we would have exited, so
A[loguy] > A[lo], A[higuy] < A[lo],
loguy < hi, highy > lo */
swap(loguy, higuy, width);
/* A[loguy] < A[lo], A[higuy] > A[lo]; so condition at top
of loop is re-established */
}
/* A[i] >= A[lo] for higuy < i <= hi,
A[i] <= A[lo] for lo <= i < loguy,
higuy < loguy, lo <= higuy <= hi
implying:
A[i] >= A[lo] for loguy <= i <= hi,
A[i] <= A[lo] for lo <= i <= higuy,
A[i] = A[lo] for higuy < i < loguy */
swap(lo, higuy, width); /* put partition element in place */
/* OK, now we have the following:
A[i] >= A[higuy] for loguy <= i <= hi,
A[i] <= A[higuy] for lo <= i < higuy
A[i] = A[lo] for higuy <= i < loguy */
/* We"ve finished the partition, now we want to sort the subarrays
[lo, higuy-1] and [loguy, hi].
We do the smaller one first to minimize stack usage.
We only sort arrays of length 2 or more.*/
if ( higuy - 1 - lo >= hi - loguy ) {
if (lo + width < higuy) {
lostk[stkptr] = lo;
histk[stkptr] = higuy - width;
++stkptr;
} /* save big recursion for later */
if (loguy < hi) {
lo = loguy;
goto recurse; /* do small recursion */
}
}
else {
if (loguy < hi) {
lostk[stkptr] = loguy;
histk[stkptr] = hi;
++stkptr; /* save big recursion for later */
}
if (lo + width < higuy) {
hi = higuy - width;
goto recurse; /* do small recursion */
}
}
}
/* We have sorted the array, except for any pending sorts on the stack.
Check if there are any, and do them. */
--stkptr;
if (stkptr >= 0) {
lo = lostk[stkptr];
hi = histk[stkptr];
goto recurse; /* pop subarray from stack */
}
else
return; /* all subarrays done */
}
← →
Игорь Шевченко © (2004-03-11 13:46) [15]
/***
*shortsort(hi, lo, width, comp) - insertion sort for sorting short arrays
*
*Purpose:
* sorts the sub-array of elements between lo and hi (inclusive)
* side effects: sorts in place
* assumes that lo < hi
*
*Entry:
* char *lo = pointer to low element to sort
* char *hi = pointer to high element to sort
* unsigned width = width in bytes of each array element
* int (*comp)() = pointer to function returning analog of strcmp for
* strings, but supplied by user for comparing the array elements.
* it accepts 2 pointers to elements and returns neg if 1<2, 0 if
* 1=2, pos if 1>2.
*
*Exit:
* returns void
*
*Exceptions:
*
*******************************************************************************/
static void __cdecl shortsort (
char *lo,
char *hi,
unsigned width,
int (__cdecl *comp)(const void *, const void *)
)
{
char *p, *max;
/* Note: in assertions below, i and j are alway inside original bound of
array to sort. */
while (hi > lo) {
/* A[i] <= A[j] for i <= j, j > hi */
max = lo;
for (p = lo+width; p <= hi; p += width) {
/* A[i] <= A[max] for lo <= i < p */
if (comp(p, max) > 0) {
max = p;
}
/* A[i] <= A[max] for lo <= i <= p */
}
/* A[i] <= A[max] for lo <= i <= hi */
swap(max, hi, width);
/* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */
hi -= width;
/* A[i] <= A[j] for i <= j, j > hi, loop top condition established */
}
/* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
so array is sorted */
}
/***
*swap(a, b, width) - swap two elements
*
*Purpose:
* swaps the two array elements of size width
*
*Entry:
* char *a, *b = pointer to two elements to swap
* unsigned width = width in bytes of each array element
*
*Exit:
* returns void
*
*Exceptions:
*
*******************************************************************************/
static void __cdecl swap (
char *a,
char *b,
unsigned width
)
{
char tmp;
if ( a != b )
/* Do the swap one character at a time to avoid potential alignment
problems. */
while ( width-- ) {
tmp = *a;
*a++ = *b;
*b++ = tmp;
}
}
← →
Digitman © (2004-03-11 13:50) [16]
> Дас Виндовс 4
var
IntList: TList;
i: Integer;
s: String;
...
function ComareTwoInteger(Item1, Item2: Pointer): Integer;
begin
Result := Integer(Item1) - Integer(Item2);
end;
...
IntList := TList.Create;
with IntList do
try
//формируем произвольный список псевдослуч. целых чисел со знаком
for i:= 0 to 9 do
Add(Pointer(Random(100)));
//покажем оригинальный (неотсортированный) список
for i:= 0 to 9 do
s := s + IntToStr(Integer(Items[i])) + #10;
ShowMessage("Original list :"#10 + s);
//сортируем оригинальный список при пом. встроенного в класс TList алгоритма сортировки QuickSort
Sort(@ComareTwoInteger);
//покажем результат сортировки
s := "";
for i:= 0 to 9 do
s := s + IntToStr(Integer(Items[i])) + #10;
ShowMessage("Sorted list :"#10 + s);
finally
Free;
end;
← →
Verg © (2004-03-11 13:56) [17]Пример БС:
procedure QSort(var A: array of Integer);
procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
Lo, Hi, Mid, T: Integer;
begin
Lo := iLo;
Hi := iHi;
Mid := A[(Lo + Hi) div 2];
repeat
while A[Lo] < Mid do Inc(Lo);
while A[Hi] > Mid do Dec(Hi);
if Lo <= Hi then
begin
T := A[Lo];
A[Lo] := A[Hi];
A[Hi] := T;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if Hi > iLo then QuickSort(A, iLo, Hi);
if Lo < iHi then QuickSort(A, Lo, iHi);
end;
begin
QuickSort(A, Low(A), High(A));
end;
Размер стека (глубина рекурсии).
При произвольной организации (случайные данные), максимальный размер стека пропорционален ~log N
Для вырожденных (частично упорядоченных) - вплоть до N.
← →
Romkin © (2004-03-11 14:01) [18]Чего вы ругаетесь?!
http://algolist.manual.ru/sort/index.php
Radix sort подходит, когда список с целыми числами, он линейный
← →
Дас Виндовс 45 (2004-03-11 15:20) [19]Благодарю.
← →
Serginio666 (2004-03-11 15:28) [20]Сортиовка слиянием очень быстрая (особенно с хорошей памятью и шиной) и главное в отличие от остальных стабильна но требует дополнительного места и работает на уровне QuickSort
http://algolist.manual.ru/sort/merge_sort.php
QuickSort показывает плохие результаты при большом количестве дубликатов значений.
Вообще читайте Джулиана Бакнелла. Прекраснейшая книга.
← →
WebErr © (2004-03-11 15:36) [21]Какая разница!!! Всё равно большинство вариантов дают сложность алгоритма N * Log(2, N), где N - длина массива... Остальное тонкости, как раз те самые, которые настоящие программеры так любят! :))))
← →
Serginio666 (2004-03-11 15:42) [22]Джулиан Бакнелл Фундаментальные алгоритмы и структуры данных в Delphi
Сайт издательства http://www.diasoft.kiev.ua
← →
Тимохов © (2004-03-11 15:43) [23]
> WebErr © (11.03.04 15:36) [21]
Насколько я понимаю разные сортировки хоть и дают n log n отличаются накладными расходами.
Наверное, все зависит от задачи.
← →
WebErr © (2004-03-11 15:45) [24]
> Тимохов © (11.03.04 15:43) [23]
Вот именно - от задачи! :))))
← →
Serginio666 (2004-03-12 13:49) [25]Бакнелл Джулиан М.
http://www.diasoft.kiev.ua/cgi/webshop.cgi?config=/home/www/htdocs/diasoft/cgi/config.txt&uid=UPTiZgAA1079088484&command =link--ds_materials_set
← →
stream © (2004-03-12 14:01) [26]Если сортировать массивы целых чисел, то самые эффективные алгоритмы - поразрядная и "карманная" сортировки, они имеют сложность O(n). Если сортировка идет по произвольным объектам (например, по строкам) или вы сами задаете порядок на множестве, то пирамидальная сортировка имеет сложность O(n*Log(n)) даже в наихудшем случае, в отличии от быстрой сортировки, которая, в среднем, работает быстрее пирамидальной.
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2004.04.04;
Скачать: [xml.tar.bz2];
Память: 0.55 MB
Время: 0.21 c
