[Algorytmy] Algorytmy sortowania

[ann_]

Mam problem z rozwiązaniem tych zadań:
1) Sortowanie tablicy f [1.....N]={1,2,3,4,5,6,7} algorytmem heapshort. Sterte utwórz w pętli for(t,i,N); Na wierzchu sterty umieść element największy. Podaj jak wyglądać będzie sterta a następnie jak wyglądać będzie tablica po wstawieniu kolejnych elementów na swoje miejsce ( w sumie wymaga to wypełniania tablicy 7 razy łącznie z ostatnim posortowaniem.

2) Wypisz kolejne drzewa BST powstałe przez wykonanie następujących operacji na pustym drzewie: i(6),i(10),i(8),i(4),i(9),i(2),i(3),d(6),i(11),i(1),d(10). Przyjmij, że usuwając element, który nie jest lisciem wpisujesz na jego miejsce odpowiedni element z jego prawego poddrzewa.

3) Napisz algorytm liscie(node*), który wywołany dla argumentu tree zwróci liczbę liści w drzewie na które wskazuje tree. Przyjmij, że node jest strukturą postaci struct node {int key, node *left, node *right;}

4) Wyszukujemy z 8 elementów o kluczach: a,b,c,g,h,x,y,z. Prawdopodobieństwa wyszukiwania elementu o danym kluczy są podane w nawisach a(0.1),b(0.05),c(0.3),g(0.1),h(0.05),x(0.2),y(0.1),z(0.1). Zbuduj optymalną listę nieuporządkowaną, która pozwoli zminimalizować koszt wyszukania jednego elementu. Oblicz średni koszt wyszukania elementu na liście (czyli średnią liczbę odwiedzonych elementów listy) Możesz założyć, że nigdy nie są wyszukiwane elementy spoza listy.

5) Oszacuj z dokładnością do O(.) czas działania algorytmu (wzgl. rozmiaru tablicy n=koniec-poczatek+1)

Kod: Zaznacz cały

Bla(int*t,int poczatek, int koniec)
if(koniec-poczatek<=3)return;
for(i:=poczatek to i=koniec)print(t[i]);
Bla(t,poczatek,koniec/3);
Bla(t,koniec/2,(2*koniec)/3);
}

Będę wdzięczna za pomoc

[bartek118]

A w czym konkretnie masz problem?

[ann_]

Tez zadania które wiem jak rozwiązać, zrobiłam tak, ale nie wiem czy są dobrze rozwiązane:
1)

Kod: Zaznacz cały

j=i;
while(j+i<=n)&&(T[j]<T[j+1]
j=j+1;
if(T[i]<T[j])
{
swap(T,i,j)
i=j;
j=2;
}
else
j=n+1;
}}

3)

Kod: Zaznacz cały

int liscie(node*elem)
{
int liczba_elem=1;
if (elem->left!=NULL)
{
liczba elem=liscie(elem->left);
}
else if(elem->right)+1;
}
return liczba_elem;
}