Тестировалось на массиве целых чисел (25000 элементов).
Прирост скорости относительно простой пузырьковой сортировки - около 75%...
Метод последовательного поиска минимумов
Теория: Просматривается весь массив, ищется минимальный элемент и ставится на место первого, "старый" первый элемент ставится на место найденного
type TArr = array[1..100] of integer; var mass1 : TArr; n : integer; procedure NextMinSearchSort(var mass:TArr; size:integer); var i, j, Nmin, temp: integer; begin for i:=1 to size-1 do begin nmin:=i; for j:=i+1 to size do if mass[j]<mass[Nmin] then Nmin:=j; temp:=mass[i]; mass[i]:=mass[Nmin]; mass[Nmin]:=temp; end; end;
Сортировка вставками
Сортировка простыми вставками в чем-то похожа на вышеизложенные методы. Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность... Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы. Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.
Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда
1. Hайден элемент, меньший x или
2. Достигнуто начало последовательности.
Type arrType = Array[1 .. n] Of Integer; Procedure Insert(Var ar: arrType; n: Integer); Var i, j, T: Integer; Begin For i := 1 To n Do Begin T := ar[i]; j := Pred(i); While (T < ar[j]) and (j > 0) Do Begin ar[Succ(j)] := ar[j]; Dec(j); End; ar[Succ(j)] := T; End; End;
Сложность О(n^2)
Распределяющая сортировка - RadixSort - цифровая – поразрядная
Пусть имеем максимум по k байт в каждом ключе (хотя за элемент сортировки вполне можно принять и что-либо другое, например слово - двойной байт, или буквы, если сортируются строки). k должно быть известно заранее, до сортировки.
Разрядность данных (количество возможных значений элементов) - m - также должна быть известна заранее и постоянна. Если мы сортируем слова, то элемент сортировки - буква, m = 33. Если в самом длинном слове 10 букв, k = 10. Обычно мы будем сортировать данные по ключам из k байт, m=256.
Пусть у нас есть массив source из n элементов по одному байту в каждом.
Для примера можете выписать на листочек массив source = <7, 9, 8, 5, 4, 7, 7>, и проделать с ним все операции, имея в виду m=9.
I. Составим таблицу распределения. В ней будет m (256) значений и заполняться она будет так:
for i := 0 to Pred(255) Do distr[i]:=0; for i := 0 to Pred(n) Do distr[source[i]] := distr[[i]] + 1;
Для нашего примера будем иметь distr = <0, 0, 0, 0, 1, 1, 0, 3, 1, 1>, то есть i-ый элемент distr[] - количество ключей со значением i.
II. Заполним таблицу индексов:
index: array[0 .. 255] of integer;
index[0]:=0;
for i := 1 to Pred(255) Do index[i]=index[i-1]+distr[i-1];
В index[ i ] мы поместили информацию о будущем количестве символов в отсортированном массиве до символа с ключом i.
Hапример, index[8] = 5 : имеем <4, 5, 7, 7, 7, 8>.
III. А теперь заполняем новосозданный массив sorted размера n:
for i := 0 to Pred(n) Do Begin sorted[ index[ source[i] ] ]:=source[i];
{
попутно изменяем index уже вставленных символов, чтобы
одинаковые ключи шли один за другим:
}
index[ source[i] ] := index[ source[i] ] +1;
End;
Итак, мы научились за O(n) сортировать байты. А от байтов до строк и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.
Будем действовать в десятичной системе и сортировать обычные числа ( m = 10 ).
сначала они в сортируем по младшему на один беспорядке: разряду: выше: и еще раз: 523 523 523 088 153 153 235 153 088 554 153 235 554 235 554 523 235 088 088 554
Hу вот мы и отсортировали за O(k*n) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то 'поразрядная сортировка' оказывается гораздо быстрее даже 'быстрой сортировки'! Реализация алгоритма "распределяющей" сортировки: Const n = 8; Type arrType = Array[0 .. Pred(n)] Of Byte; Const m = 256; a: arrType = (44, 55, 12, 42, 94, 18, 6, 67); Procedure RadixSort(Var source, sorted: arrType); Type indexType = Array[0 .. Pred(m)] Of Byte; Var distr, index: indexType; i: integer; begin fillchar(distr, sizeof(distr), 0); for i := 0 to Pred(n) do inc(distr[source[i]]); index[0] := 0; for i := 1 to Pred(m) do index[i] := index[Pred(i)] + distr[Pred(i)]; for i := 0 to Pred(n) do begin sorted[ index[source[i]] ] := source[i]; index[source[i]] := index[source[i]]+1; end; end; var b: arrType; begin RadixSort(a, b); end.
Теория чисел.
Теория чисел является, возможно, самым интересным и красивым разделом математики. Доказательство Евклидом существования бесконечного количества простых чисел остается таким же четким и ясным сегодня, каким оно было более двух тысяч лет назад. Такие невинные вопросы, как существуют ли решения уравнения аn+bn=cn для целых a,b,c и n>2, часто оказывается совсем не такими невинными. Более того, это формулировка великой теоремы Ферма!
Компьютеры уже долгое время используют в исследованиях теории чисел. Проведение некоторых вычислений, связанных с теорией, для больших чисел требует значительной эффективности. К счастью, существует множество алгоритмов, которые могут помочь в этом.
Простые числа
Целое число р>1 называют простым, если оно делится только на 1 и на само себя. Говоря другими словами, если р – простое число, то равенство р=a*b для целых a≤b эквивалентно тому, что a=1 и b=p. Первые десять простых чисел: 2, 3, 5, 7,11, 13, 17, 19, 23 и 29.
Мы говорим, что число р является множителем числа х, если оно входит в его разложение на простые множители. Любое число не являющееся простым, называется составным.
Нахождение количества делителей и самих делители числа а.
Для этого будем перебирать все числа i, подходящие на роль делителя. Очевидно, что 1 <= i <= a. Чтобы ускорить работу алгоритма заметим, что если i – делитель а, то a/i – тоже делитель a, и к тому же одно из чисел i и a/i не превышает Sqrt(a) (если предположить противное, то получим a = i*(a/i) > Sqrt(a)*Sqrt(a) = a – противоречие). Поэтому достаточно перебирать числа i в пределах от 1 до Trunc(Sqrt(a)) и при нахождении, что некоторое i – делитель выдавать, что a/i – тоже делитель и увеличивать количество делителей на 2. Этот алгоритм не будет работать, когда a – точный квадрат, что легко исправляется.
Приведенные соображения реализованы в алгоритме (2):
c:= 0;
For i:= 1 to Trunc(Sqrt(a)) do
If a mod i = 0 then begin
If i*i = a then begin
c:= c+1;
WriteLn(‘Найден делитель ’, i);
end
else begin
c:= c+2;
if i=a div i then c:=c-1;
WriteLn(‘Найден делитель ‘, i);
WriteLn(‘Найден делитель ‘, a div i);
end;
WriteLn(‘Количество делителей ‘, c);
Для того, чтобы проверить, является ли число простым, нужно посчитать количество его делителей, используя алгоритм 2.
Нахождение всех простых чисел, не превосходящих заданное число N.
Возможны несколько подходов к решению этой задачи:
1) Метод Эратосфена. Выпишем все числа от 2 до N. Затем, пока есть числа, которые не вычеркнуты и не обведены, делаем следующий набор операций: обводим минимальное из оставшихся чисел, вычеркиваем все числа, кратные ему. После окончания работы алгоритма все простые числа будут обведены.
Доказательство. Данный алгоритм не может вычеркнуть простое число, так как если число вычеркивается, то оно заведомо делится на какое-то другое, не равное ему. Теперь докажем по индукции, что для любого N алгоритм обводит все простые числа, не превосходящие N. База: при N = 2 утверждение верно, так как 2 будет обведено на 1-м шаге. Индуктивный переход: пусть утверждение верно при 2 <= N <= k-1. Рассмотрим N = k. Если N – составное, то у числа N есть простой делитель t, в качестве которого можно взять, например, его минимальный делитель (почему?). По индукции, на каком-то шаге число t будет обведено, на этом же шаге будет вычеркнуто N. Если же N – простое, то оно не может быть вычеркнуто, поэтому на каком-то шаге станет минимальным из оставшихся и будет обведено. Утверждение доказано.
Страницы: 1, 2, 3
