[C++] Przerobienie fragmentu kodu na wersję nierekurencyjna

[mario5046]

Witam, pomożecie przerobić poniższą część kodu z wersji rekurencyjnej na wersję nierekurencyjną?

Kod: Zaznacz cały

void heapify(int * tab, int i)
{
   int l = 2*i;
   int r = 2*i+1;
   int largest,x;

   if ((l<=heap_size)&&(tab[l]>tab[i])) largest = l;
   else largest = i;
   if ((r<=heap_size)&&(tab[r]>tab[i])) largest = r;

   if(largest != i)
   {
      x = tab[largest];
      tab[largest] = tab[i];
      tab[i] = x;
      heapify(tab, largest);   
   }
}

to jest fragment kodu sortującego

[knrdk]

Zauważ że twoje rekurencyjne wywołanie polega na zamianie i na largest, więc całość funkcji wsadź do pętli

Kod: Zaznacz cały

while(i<=heap_size) 

Rekurencyjne wywołanie zamień na:

Kod: Zaznacz cały

i=largest;

no i gdy i==largest przerwij pętle/wyjdź z funkcji

[mario5046]

Super, bardzo dziękuję za pomoc. Wielki plus dla ciebie

[Mariusz M]

U niego heap_size jest zmienną globalną ?

Ja coś podobnego znalazłem w sieci

Kod: Zaznacz cały

void heapify(int* tab,int i, int heap_size)
{
      int l,r,largest;
      int x;
      bool isheap=false;
      while((i<=heap_size)&&(!isheap))
       {
             l=2*i;
             r=2*i+1;
             if((l<=heap_size)&&tab[l]>tab[i]) largest=l;
             else largest=i
             if((r<=heap_size)&&tab[r]>tab[largest]) largest=r;
             if(largest!=i)
              {
                     x=tab[largest];
                     tab[largest]=tab[i];
                     tab[i]=x;
                     i=largest;
              }
              else isheap=true;
                  
       }
}

Jaka jest złożoność czasowa takiego kodu
Czy aby na pewno nie wyjdziemy poza zakres typu int
Dlaczego akurat tak należało zbudować instrukcję iteracyjną
oraz instrukcję warunkową w której następuje zamiana