Heapsort как не модульный


На данный момент я не заинтересован в любом рекурсивное решение. Код не модульный; все тело находится внутри функции main.

#include<iostream.h>
#include<stdlib.h>
/*This code is written by NF between any time of 120711 and 210711;modified at 231211*/

int main()
{
    int length=0,min_heapified=0,start_length=0,index=0;
    cout<<"Enter Array Length:";
    cin>>length;
    int array[length];
    for(int i=0;i<length;i++)
    {
        array[i]=rand()%100;
    }
    cout<<"Array is filled now with random elements";
    cout<<"\nSorted Array:"<<endl;
    do
    {       
            do
            {
                min_heapified=0;
                for(int root=0;root<length/2;root++)/*As the leaf nodes have no child they should not be in a consideration while swapping so looping upto length/2 is enough*/
                {

                    int left=((2*root)+1);
                    int right=((2*root)+2);

                    if(left<length)
                    {
                           if(array[left]<array[root])
                           {
                                int swap=array[left];
                                array[left]=array[root];
                                array[root]=swap;
                                min_heapified=1;    
                           }
                     }
                    if(right<length)
                     {
                            if(array[right]<array[root])
                            {
                                 int swap=array[right];
                                 array[right]=array[root];
                                 array[root]=swap;
                                 min_heapified=1;    
                             }
                      }

                  }

             }while(min_heapified>0);

            int swap=array[0];
            array[0]=array[--length];/*modification done at this point to avoid keeping the sorted elements into another array;and swapping done between the 0th and last element*/
            array[length]=swap;
            cout<<array[length]<<" "; 

 }while(length>0);

  return 0;

}


3420
7
задан 22 ноября 2011 в 09:11 Источник Поделиться
Комментарии
3 ответа

Других ответов покрыть стилистические проблемы вашего кода уже довольно хорошо. Однако, есть еще одна большая проблема с ваш код, что гарантирует еще (хоть и поздно)ответ: это неправильно реализован!

В "heapsort как" алгоритм, который реализован уже во время выполнения сложность о(N2). Судя по вашему комментарию, вы, наверное, поняли, что что-то было слишком плохо, так как во время выполнения взлетели, как вы пытались разобрать больше деталей.

Здесь представлены проблемные зоны, я вижу, что это вызывает катастрофические показатели:


  • Вы повторно heapifying на весь массив на каждой итерации. Это, конечно, совершенно неправильно, и это самая главная причина, почему ваш код выполняется так плохо. Вы только предположим, чтобы heapify массив один раз, в начале, когда вы начинаете сортировать.

  • Переложив все элементы вниз на один после удаления мельчайших. Это является o(n) операций, которые можно избежать с перепланировкой.

  • Использовать временный массив-это тоже лишнее. Как и быстрая сортировка, одним из преимуществ heapsort как заключается в том, что он способен сортировки на месте, без необходимости выделять временный буфер.

  • Heapifying "лист" элементы напрасно. По определению, элементы листьев не иметь дочерних узлов под ними так что нечего спихивать. Поэтому не имеет смысла heapify пройти последний родительский элемент. Другими словами, вы должны идти от корня = 0 для корня < (длина / 2). Проходит длина / 2 будет просто привести к ненужным сравнения: слева < длина и право < длина будет всегда ложным.

Обычно пишут 2 вспомогательные функции при реализации heapsort как: heapify , что превращает массив в куче, и push_down или filter_down функции для реализации кучи собственность на передаваемый элемент. Вы обычно реализуют heapify с помощью функции фильтра.

Обратите внимание, что в STL есть куча функций, что делает именно эти задачи: push_heap, pop_heap и make_heap.

Я оставлю полезных функций для вас, чтобы выяснить, а вот как сверху heapsort как должно выглядеть:

void heapsort(int *begin, int *end)
{
// assume end is one pass the last element. eg. arry + length;
heapify(begin, end);

while(begin != --end)
{
swap(*begin, *end); // invariant: the next item to order will be at the top
// after the swap, the next biggest/smallest item may not be
// at the top. use push_down to fix this and preserve the heap property.
push_down(begin, end);
}
}

Обратите внимание, что вы не называете heapify внутри цикла. После замены, только верхний элемент может нарушать кучи собственность -- остальные остальные элементы все в кучу. Чтобы исправить верхний нужно просто push_down этого элемента, пока не достигнет нужного уровня. Это может быть сделано в o(зарегистрируйте N), так вот как глубоко дерево может когда-либо быть.

Редактирования: добавил Более подробное объяснение и пример.

Аналогия может помочь прояснить идея heapsort как. Вы можете думать heapsort как как проводит отборочный турнир, где каждый матч-кронштейн 3 претендентов герцог его. Победителем будет двигаться вверх скобу на следующий матч-и 2 лузеры сидят, где они находятся. Турнир начинается, делая все матч-апы на нижней планке во-первых, постепенно двигаясь вверх -- это в основном heapifying фразы.

После heapify, что заканчивает один весь турнир -- чемпион в массив[0] и призеров будет массив[1] или Array[2]. Чтобы найти бегун-вверх вы размещаете еще один матч-между ними, плюс 3-й претендент снизу кронштейна.

Теперь, если вы думаете 'push_down' как своего рода секретарь, его задача-отслеживать победителей и перемещать их вверх кронштейн + что матчи должны проходить. Каждый матч-вверх, 1 'защитник'(у парня один кронштейн) и 2 'претендентов'. Если защитник проигрывает, он меняет места с претендентом, который победил его. Если есть еще претенденты ниже новое место защитника, еще один матч-между ними. Защитник будет отодвинута еще дальше и дальше вниз по Матч-кронштейн, пока он не сможет успешно защищать свое место или нет больше противников, чтобы защититься.

Функция 'push_down' является, пожалуй, самым важным помощником, так вот где порядка на самом деле происходит. Это почти аналогично секции в qsort или слиянием сортировка слиянием.

Вот в основном то, что функция push_down будет выглядеть так: (Обратите внимание, это не тщательно протестированы)

void push_down(int *begin, int *end, size_t defender = 0)
{
// at the very bottom?
if(defender >= std::distance(begin, end) / 2) return;

size_t challenger = defender * 2 + 1;
// is there a right-child?
// Note that in even# arrays, last parent doesn't have a right child
if(begin + challenger + 1 != end)
if(begin[challenger + 1] < begin[challenger])
++challenger;

// defended successfully?
if( !(begin[challenger] < begin[defender]) ) return;

// challenger wins
std::swap(begin[challenger], begin[defender]);
push_down(begin, end, challenger);
}

Обратите внимание, что массив будет отсортирован в порядке убывания, если маленький находится в верхней части. Но это тривиально, чтобы исправить когда-то сортировка работает-просто переверните сравнение делается.

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

4
ответ дан 19 декабря 2011 в 03:12 Источник Поделиться

int length=0,min_heapified=0,start_length=0,index=0;

Я предпочитаю одно объявление на каждую линию, потому что его легче читать и находить тип переменных. Кроме того, min_heapified используется только внутри делать-в то время как петли, так объявите это здесь:

do {       
int min_heapified = 0;
do {
...


Изменение

if(x<=(length-1))

для

if (x < length)

Это более распространенный и простой.


Вместо

int swap=array[left];
array[left]=array[root];
array[root]=swap;

вы должны создать своп функции. Может быть, он уже существует в библиотеке.

int swap(array, index, rootIndex) {
int swap = array[index];
array[index] = array[rootIndex];
array[root] = swap;
}


Если я прав можно извлечь следующие новые функции:

if(array[left]<array[root])
{
int swap=array[left];
array[left]=array[root];
array[root]=swap;
min_heapified=1;
}

Кажется, что другие если сделать то же самое. Единственным отличием является используемый индекс, так что я мог бы написать что-то вроде этого:

int swapIfLess(array, index, rootIndex) {
if (array[index] < array[rootIndex]) {
swap(array, index, rootIndex)
return 1;
}
return 0;
}

if (left < length) {
if (swapIfLess(array, left, root)) {
min_heapified=1;
}
}
if (right < length) {
if (swapIfLess(array, right, root)) {
min_heapified=1;
}
}


У меня переменная выглядит ненужным:

int root=i;

Использовать корень переменной в цикле for:

for (int root = 0; root < length; root++)

Может быть, вы должны переименовать его в rootIndex.


Извлечь больше функций. В для петли (внутри делать-в то время как петли) выглядит как хороший кандидат для этого. Кроме того, вы должны иметь readInputArray функции и printResults функции тоже.

7
ответ дан 22 ноября 2011 в 12:11 Источник Поделиться

Позволяет объявить одну переменную в строке.
Также не объявлять все, что вам переменные в верхней части. Объявить их как можно ближе к точке использования.

    int length=0,min_heapified=0,start_length=0,index=0;

Объявления массивов, как это не действует. Это функциональность кондиционера. ваш компилятор не позволю тебе уйти с ним, но не все компилятор. Размер массива должен быть статичен и известен во время компиляции. Если вам нужно размер динамических массивов, а затем использовать std::вектор

    int array[length],sorted_array[length];

C++ уже есть объект std::своп() использовать, а не делать это вручную.

использовать < а не <= (это выглядит более естественно для большинства программистов С/С++). В вашем случае это тем более Бог, как вы все равно вычитая одно.

if(root <= (length-1))
// Prefer the following
if(root < length)

Это ООН-необходимо проверить:

if(root < length)

корень - это я и я - это переменная цикла вынужден быть меньше, чем длина. Пока мы здесь, вы не должны использовать меня в качестве имени переменной. Он передает никакого смысла (это не Фортран). Название ваших переменных. Тоже думаю о сопровождающему поиск всех использует Я-реальная боль, как буква i используется повсеместно. Название ваших переменных, поэтому оно может быть легко найдено.

Предпочитают использовать пре-инкремент.

for(int root=0;root<length;root++)
// prefer
for(int root=0;root<length;++root)

В данном случае это без разницы. Но при использовании типов классов (как многие итераторы) стандартным образом проводить пост инкремент делать копию (как возвращаемое значение), то колл пре-инкремент. Таким образом, он может быть немного менее эффективным, чтобы использовать пост инкремент, когда переменной типа класса. Проблема с пост инкрементом наступает не тогда, когда вы пишете код, но когда вы поддерживаете его. Если кто-то преобразует контейнер стандартный контейнер, а затем преобразует цикл iteratos и т. д. Вам нужно определить и изменить шаг. Будучи последовательным и всегда использовать пре-инкремент изменения в видах имеют меньше влияют на изменения в код (т. е. это поможет, когда меняются (особенно при смене типа далеко от типа).

Вы используете min_heapified как логическое. Объявить ее как таковой и использовать надлежащим образом.

min_heapified=0;

В то время как вы на него. Заявляю это здесь, а не в верхней.

bool min_heapified = false;

2
ответ дан 22 ноября 2011 в 05:11 Источник Поделиться