Сортировка методом поиска нового номера (в новый массив)
Краткая теория: Последовательно для каждого элемента массива вычисляется его новая позиция в отсортированном массиве, рассчитывается кол-во элементов, значения которых
- < значения анализируемого
- значения которых = значению анализируемого элемента и номера которых <= номера анализируемого.
Особенности: Требуется дополнительный массив, не чувствительный к изначальной упорядоченности.
Оценка числа операций: N*N
type
TArr = array[1..100] of integer;
var
mass1,NewMass : TArr;
n : integer;
{
n-размерность массива, mass1 - исходный массив,
NewMass - удет состоять из отсотртированных элементов массива mass1
}
procedure NewNSort(var mass, Nmass: TArr; size: integer);
var i, j, NewN: integer;
begin
for i:=1 to size do begin
NewN:=0;
for j:=1 to size do
if (mass[j]<mass[i]) or ((mass[j]=mass[i]) and (j<=i)) then inc(NewN);
Nmass[NewN]:=mass[i];
end;
end;
Пример использования:
NewNSort(mass1, NewMass, n);
Массив
NewMass будет состоять из элементов массива
mass1, но уже отсортированных.
На небольших массивах работает неплохо.
Добавлено:
Тесты на скорость (в условных единицах):
1. (набор данных - массив из 8 элементов типа integer)
Количество тестов: n = 4 000 000
#1: 292 (метод нового номера)
#2: 558 (сортировка пузырьком)
#3: 490 (поразрядная сортировка - radixsort)
2. (набор данных - массив из 800 элементов типа integer)
Количество тестов: n = 225
#1: 95 (метод нового номера)
#2: 174 (сортировка пузырьком)
#3: 2 (поразрядная сортировка - radixsort)
На небольших массивах действительно достаточно быстрый метод, но с увеличением размера массива "метод нового номера" начинает значительно проигрывать поразрядной сортировке.
volvo