Heapsort, prośba o weryfikację

Heapsort, prośba o weryfikację
CE
  • Rejestracja:prawie 12 lat
  • Ostatnio:ponad 7 lat
  • Postów:124
0

Witam. Na zajęciach stworzyliśmy algorytm jak poniżej. Prosiłbym o weryfikację, jako, że sortowanie jest błędne.

Kopiuj
void heapty (int tab[], int o, int heapsize) // o - ojciec, l - left, r- right
{
	int l = 2 * o;
	int r = (2 * o) + 1;
	int largest;

	if (l <= heapsize && tab[o] < tab[l])
		largest = l;
	else
		largest = o;

	if (r <= heapsize && tab[largest] < tab[r]) // wyznaczanie indeksu odnoszącego się do największego elementu tablicy
		largest = r;

	if (largest != o)
	{
		swap(tab[o], tab[largest]); // zamiana ojca z największym elementem
		heapty(tab, largest, heapsize); // rekurencja
	}
}

void build_heap(int tab[], int heapsize) // budowa kopca
{
	for (int i = heapsize/2; 0 <= i; i--) 
		heapty(tab, i, heapsize);
}

void heap_sort(int tab[], int size)
{
	int heapsize = size;
	build_heap(tab, heapsize); // budowa kopca

	do {
		swap(tab[0], tab[heapsize]); // zamieniamy największy z ostatnim
		heapsize--; // zmniejszamy rozmiar tablicy, największe elementy odkładają się na ostatnich indeksach tablicy
		heapty(tab, 0, heapsize);
	} while (heapsize > 0);
}

int main()
{
	const int d = 10;
	int tab2[d] = { 23, 45, 23, 11, 24, 65, 931, 11, 2, 40 };

	cout << "PRZED SORTOWANIEM:" << endl << endl;
	for (int i = 0; i < d; i++) // wypisanie posortowanej tablicy
		cout << "tab[" << i << "] = " << tab2[i] << endl;
	cout << endl;

	heap_sort(tab2, d);

	cout << "PO SORTOWANIU:" << endl << endl;
	for (int i = 0; i < d; i++) // wypisanie posortowanej tablicy
		cout << "tab[" << i << "] = " << tab2[i] << endl;

	system("pause");

	return 0;
} 
edytowany 2x, ostatnio: Ceplusplus
Wibowit
  • Rejestracja:prawie 20 lat
  • Ostatnio:około 2 godziny
1

Primo: wrzuć coś co się skompiluje na ideone.com
Secundo:
swap(tab[0], tab[heapsize]); // zamieniamy największy z ostatnim
Przy pierwszym wykonaniu tego kawałka kodu heapsize będzie wynosić 10, a więc będziesz wyjeżdżał poza tablicę (bo dozwolone indeksy to od 0 do 9).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
CE
  • Rejestracja:prawie 12 lat
  • Ostatnio:ponad 7 lat
  • Postów:124
0

http://ideone.com/UgH67W - przesyłam link. Całość przepisywałem z pseudokodu i tam pierwszy ojciec był mnożony jako jedynka - w naszych indeksach jest 0, co pewnie też psuje cały rezultat. Jakiś pomysł, jak to obejść?

Wibowit
  • Rejestracja:prawie 20 lat
  • Ostatnio:około 2 godziny
2

Rozrysuj sobie drzewko, a potem rozpisz sobie:

  • poziom 0,
  • ojciec 0 - dzieci 1 i 2,
  • poziom 1,
  • ojciec 1 - dzieci 3 i 4,
  • ojciec 2 - dzieci 5 i 6,
  • poziom 2,
  • ojciec 3 - dzieci 7 i 8,
    ...
  • ojciec 6 - dzieci 13 i 14,
  • poziom 3,
  • ojciec 7 - dzieci 15 i 16,
  • itd

Potem spróbuj dopasować wzory.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.