• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytm sortowania przez kopcowanie

Object Storage Arubacloud
0 głosów
193 wizyt
pytanie zadane 14 listopada 2022 w C i C++ przez MKolaj15 Bywalec (2,270 p.)

Cześć, chciałem zaimplementować algorytm sortowania przez kopcowanie i mam pewien problem, mianowicie program poprawnie sortuje większość elementów, oprócz tego, że po pierwszym "swapie" zawsze zostawia pierwszy element pierwotnej tablicy na końcu posortowanej tablicy i nie mam pojęcia, czemu tak się dzieje. Czy ktoś mógłby podpowiedzieć, z góry dzięki.

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 10;				// wielkosc tablicy

int d[N];

void max_heapify(int heap_size, int A[], int i){
	int l = (2*i) + 1;
	int r = (2*i) + 2;
	int largest;
	
	if(l <= heap_size && A[l] > A[i]){
		largest = l;
	} else {
		largest = i;
	}
	
	if(r <= heap_size && A[r] > A[largest]){
		largest = r;
	}
	
	if(largest != i){
		swap(A[i], A[largest]);
		max_heapify(heap_size, A, largest);
	}
	
}

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

void heap_sort(int heap_size, int A[]){
	build_max_heap(heap_size, A);
	
	for (int i = heap_size; i >= 1; i--){
		swap(A[0], A[i]);
		max_heapify(i-1, A, 0);
	}
}

int main(){
	
	srand((unsigned)time(NULL));		// konfigurowanie funkcji pseudolosującej z czasem reczywistym komputera
	int i; 
	 
	for(i = 0; i < N; i++){
		d[i] = rand() % 1000;			// 	wypełnienie tablicy liczbami z zakresu 0-999;
	}
	
	for(i = 0; i < N; i++){
		cout<<setw(4)<<d[i];			// wyswietlanie tablicy przed posortowaniem
	}
	cout<<endl;
	
	heap_sort(N-1, d);
	
	for(i = 0; i < N; i++) {			
		cout<<setw(4)<<d[i];			// wyswietlanie posortowanej tablicy
	}
	cout<<endl;
	
	return 0;
}

 

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 317 wizyt
pytanie zadane 15 maja 2016 w C i C++ przez krzych719 Nowicjusz (120 p.)
0 głosów
1 odpowiedź 767 wizyt
pytanie zadane 12 listopada 2016 w C i C++ przez ml333 Nowicjusz (120 p.)
0 głosów
0 odpowiedzi 167 wizyt

92,761 zapytań

141,685 odpowiedzi

320,482 komentarzy

62,105 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...