heapsort - сложность реализации

Я написал heapsort (Cormen). Алгоритм сортируется правильно, но сложность выше ожидаемой.heapsort - сложность реализации

void heap_sort(int tab[], int length) 
{ 
    build_max_heap(tab, length); 
    int heap_size = length; 
    for (int i = length-1; i > 1; i--) 
    { 
     int tmp = tab[1]; 
     tab[1] = tab[i]; 
     tab[i] = tmp; 
     heap_size--; 
     max_heapify(tab, 1, heap_size); 
    } 
} 

void max_heapify (int tab[], int i, int length) 
{ 
    int largest; 
    int l = i * 2; 
    int r = i * 2 + 1; 
    if (l < length and tab[l] > tab[i]) 
     largest = l; 
    else 
     largest = i; 
    if (r < length and tab[r] > tab[largest]) 
     largest = r; 
    if (largest != i) 
    { 
     int tmp = tab[i]; 
     tab[i] = tab[largest]; 
     tab[largest] = tmp; 
     max_heapify(tab, largest, length); 
    } 
} 

void build_max_heap(int tab[], int length) 
{ 
    for (int i = length/2; i >= 1; i--) 
     max_heapify(tab, i, length); 
}

Для 15000000 чисел, сгенерированных рандов() она длилась дольше, чем сортировка с Шелла в этой реализации:

void shell_sort (int tab[], int length) 
{ 
    int x = 2; 
    int q; 
    do 
    { 
     x*=2; 
     q=2*(length/x) + 1; 
     for(int i = q, val, j; i < length; i++) 
     { 
      val = tab[i]; 
      for(j = i - q ; j >= 0 and tab[j] > val; j-=q) 
      { 
       tab[j + q] = tab[j]; 
      } 
      tab[j + q] = val; 
     } 
    }while (q > 1); 
}

Тест:

HEAPSORT 
Time for 1000000 elements: 0.336 s 
Time for 2000000 elements: 0.732 s 
Time for 3000000 elements: 1.142 s 
Time for 4000000 elements: 1.595 s 
Time for 5000000 elements: 2.034 s 
Time for 6000000 elements: 2.513 s 
Time for 7000000 elements: 3.023 s 
Time for 8000000 elements: 3.51 s 
Time for 9000000 elements: 4.02 s 
Time for 10000000 elements: 4.558 s 
Time for 11000000 elements: 5.095 s 
Time for 12000000 elements: 5.595 s 
Time for 13000000 elements: 6.183 s 
Time for 14000000 elements: 6.7 s 
Time for 15000000 elements: 7.367 s 

SHELLSORT 
Time for 1000000 elements: 0.343 s 
Time for 2000000 elements: 0.779 s 
Time for 3000000 elements: 1.182 s 
Time for 4000000 elements: 1.654 s 
Time for 5000000 elements: 2.218 s 
Time for 6000000 elements: 2.672 s 
Time for 7000000 elements: 3.34 s 
Time for 8000000 elements: 3.778 s 
Time for 9000000 elements: 4.297 s 
Time for 10000000 elements: 4.903 s 
Time for 11000000 elements: 4.872 s 
Time for 12000000 elements: 5.514 s 
Time for 13000000 elements: 6.29 s 
Time for 14000000 elements: 6.994 s 
Time for 15000000 elements: 7.121 s

Я повторил тест много раз. Что случилось с алгоритом?

источник

2016-03-18 maksym

После создания кучи, чтобы отсортировать его: 'while (first! = Last) {std :: pop_heap (first, last--); } ' – David

Поскольку это делается для образовательных целей, мне не разрешено использовать' std :: pop_heap'. Я должен был упомянуть об этом. – maksym

Ну, в организационных целях я рекомендую упростить работу, написав функции 'make_heap',' sort_heap', 'push_heap' и' pop_heap' отдельно, где 'sort_heap' - это всего лишь 2 лайнер, который я написал выше. – David

Первое примечание, большой-O и необработанные характеристики имеют сложные отношения. В случае с heapsort, плохая локальность памяти приведет к тому, что он будет хуже ухудшаться на компьютерах, чем предполагал Big-O. В отличие от вида оболочки, только немного хуже, чем O(n log(n)), и большинство его проходов имеют приличную память.

Поэтому я не удивлен, что они сопоставимы.

При этом вы можете попробовать превратить max_heapify из рекурсивной функции в цикл. Это может избежать определенного количества манипуляций с стеками.

источник

2016-03-19 01:06:18 btilly

heapsort - сложность реализации

ответ

Смежные вопросы