<< На главную

Сортировка с помощью d-кучи

Алгоритм имеет вычислительную сложность C*n*log(n), C - константа; n - длина массива.

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

Вообще доказано, что имея операцию сравнения невозможно отсортировать массив за более лучшее время.

Алгоритм сортировки
Подробнее см. "Лекции по Теории Алгоритмов".

Для представления сортируемой последовательности используем структуру d-кучи. Сортировку можно провести в два этапа.
1. Образовать очередь, применяя последовательно операцию ПОГРУЖЕНИЕ по очереди к узлам (n - 1), (n - 2), … , 0 в предположении, что сначала все n ключей занимают в произвольном порядке массив key [0 .. n - 1]. 
2. Осуществить окончательную сортировку следующим образом. Первый (минимальный) элемент кучи меняем местами с последним, уменьшаем размер кучи на 1 (минимальный элемент остается в последней позиции массива key, не являясь уже элементом кучи) и применяем операцию ПОГРУЖЕНИЕ к корню, затем повторяем аналогичные действия, пока размер кучи не станет равным 1.
Эти два этапа реализуются с помощью процедуры Sort, которая сортирует массив по убыванию ключей. 

procedure SORT(n);
begin
for i := n - 1 downto 0 do ПОГРУЖЕНИЕ (i);
while n > 1 do { tr (1, n); n:= n - 1; ПОГРУЖЕНИЕ (1) }
end;

Заметим, что процедура Sort не требует дополнительной памяти, размер которой зависел бы от длины массива Key.

Реализация на C++

#ifndef SorterH
#define SorterH

// Шаблонный класс сортировки
// Type - тип сортируемых элементов
// Пример использования см. ниже

template <class Type>
class TSorter
{

protected:
long int ArraySize; // РАЗМЕР МАССИВА ДЛЯ СОРТИРОВКИ
Type * Array; // УКАЗАТЕЛЬ НА НАЧАЛО МАССИВА 
int d; // ПОКАЗАТЕЛЬ "d" d-кучи (используют в основном 2,3 или 4)

public:

//КОНСТРУКТОР КЛАССА
// ПЕРЕДАЕТСЯ УКАЗАТЕЛЬ НА МАССИВ, РАЗМЕР МАССИВА, ПАРАМЕТР d

TSorter(Type * A = NULL,long int Size = 0,int dd=2):Array(A),ArraySize(Size),d(dd){};

// ФУНКЦИЯ ЭКВИВАЛЕНТНАЯ КОНСТРУКТОРУ
void SetArray(Type * A = NULL,long int Size = 0,int dd=2)
{
Array = A;
ArraySize = Size;
d = dd;
}

// ФУНКЦИЯ СОРТИРОВКИ
void sort()
{
int n = ArraySize;
for (long int i = ArraySize/2;i>=0;i--) Down(i);
while (ArraySize>0)
{
Type temp = Array[0];
Array[0] = Array[ArraySize-1];
Array[ArraySize-1] = temp;
ArraySize--;
Down(0);
}
ArraySize = n;
}

protected:

Type min(Type a,Type b)
{ return (a>b)?b:a; }

long int minchild(long int i)
{
long int _minchild;
if ((i*d+1)>=ArraySize) _minchild = 0;
else
{
long int first_child = i*d+1;
long int t1 = (i+1)*d;
long int t2 = ArraySize-1;
long int last_child = (t1<t2)?t1:t2;
Type min_key = Array[first_child];
_minchild = first_child;
for (long int i = first_child;i<=last_child;i++)
if (Array[i]<min_key)
{
min_key = Array[i]; _minchild = i;
}
}
return _minchild;
}

// ПЕРЕСТАНОВКА ЭЛЕМЕНТОВ
void tr(long int i,long int j)
{
Type temp = Array[i];
Array[i] = Array[j];
Array[j] = temp;
}

// ПОГРУЖЕНИЕ
void Down(long int i)
{
long int c = minchild(i);
while ((c!=0)&&(Array[c]<Array[i]))
{
// tr(i,c);
Type temp = Array[i];
Array[i] = Array[c];
Array[c] = temp;

i = c;
c = minchild(c);
}
}

};

#endif


Пример использования
Пусть необходимо отсортировать массив Key длины KeySize...
...

TSorter<int> Sort1;
int *Key;
long int KeySize;

KeySize = 500000;
Key = new int[KeySize];

//Случайное заполнение
for (long int i =0 ;i<=KeySize;i++)
{
Key[i] = random(10000);
}

Sort1.SetArray(Key,KeySize,3);

// Сортируем 
Sort1.sort();

...

delete [] Key;

...


<< На главную