10 сент. 2010 г.

Пирамидальная сортировка

Пирамидальная сортировка

Пирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
Может рассматриватъся как усовершенствованная Bubblesort, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям....

Алгоритм

Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево — это такое двоичное дерево, у которого выполнены условия:
  1. Каждый лист имеет глубину либо d либо d − 1, d — максимальная глубина дерева.
  2. Значение в любой вершине больше, чем значения её потомков.
Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] — Array[2i] и Array[2i+1].
Алгоритм сортировки будет состоять из двух основных шагов:
  1. Выстраиваем элементы массива в виде сортирующего дерева:
    2. Array[i]>= Array[2i]
    Array[i]>= Array[2i+1]
    при 1 <= i < n/2.
    Этот шаг требует O(n) операций.
  2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево.
    Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент.
    Тогда Array[1], Array[2], … , Array[n] — упорядоченная последовательность.
    Этот шаг требует O(nlogn) операций.

Пример сортирующего дерева

Пирамидальная сортировка

Реализация быстрой сортировки на С++

01//Пирамидальная сортировка
02using namespace std;
03void iswap(int &n1, int &n2)
04{
05    int temp = n1;
06    n1 = n2;
07    n2 = temp;
08}
09int main()
10{
11    int const n = 100;
12    int a[n];
13    for ( int i = 0; i < n; ++i ) { a[i] = n - i; cout << a[i] << " "; }
14    //заполняем массив для наглядности.
15    //-----------сортировка------------//
16    //сортирует по-возрастанию. чтобы настроить по-убыванию,
17    //поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
18    int sh = 0; //смещение
19    bool b = false;
20    for(;;)
21    {
22    b = false;
23    for ( int i = 0; i < n; i++ )
24    {
25        if( i * 2 + 2 + sh  /* /*<*/ a[i * 2 + 2 + sh] ) )
26        {
27            if ( a[i * 2 + 1 + sh] */ a[i * 2 + 2 + sh] )
28            {
29            iswap( a[i + sh], a[i * 2 + 1 + sh] );
30            b = true;
31            }
32            else if ( a[i * 2 + 2 + sh] */ a[ i * 2 + 1 + sh])
33                 {
34                     iswap( a[ i + sh], a[i * 2 + 2 + sh]);
35                     b = true;
36                 }
37        }
38        }
39        else if( i * 2 + 1 + sh  /*<*/ a[ i * 2 + 1 + sh] )
40                 {
41                     iswap( a[i + sh], a[i * 2 + 1 + sh] );
42                     b = true;
43                 }
44             }
45    }
46    if (!b) sh++; //смещение увеличивается, когда на текущем этапе
47              //сортировать больше нечего
48    if ( sh + 2 == n ) break;
49    }  //конец сортировки
50    cout << endl << endl;
51    for ( int i = 0; i < n; ++i ) cout << a[i] << " ";
52  
53  
54    _getch();
55    return 0;
56}
57/******************/

Достоинства и недостатки

Достоинства:
  • Имеет доказанную оценку худшего случая O(nlogn).
  • Требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).
Недостатки:
  • Сложен в реализации.
  • Неустойчив — для обеспечения устойчивости нужно расширять ключ.
  • На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
  • На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.

Вывод по пирамидальной сортировке

Сортировка слиянием при расходе памяти O(n) быстрее (O(n·logn) с меньшей константой) и не подвержена деградации на неудачных данных.
Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.
в 16:34