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

Process exited after 51.84 seconds with return value 3221225725

VPS Starter Arubacloud
0 głosów
198 wizyt
pytanie zadane 15 listopada 2022 w C i C++ przez MKolaj15 Bywalec (2,270 p.)

Cześć, mam 3 programy i w każdym z nich 3 takie same algorytmy sortujące: Quick-sort, Heap-sort, Bubble-sort. W pierwszym programie każdy z algorytmów ma posortować tablice z takimi samymi, losowo wygenerowanymi wartościami i wyświetlić czas w jakim tego dokonał. Drugi program robi to samo, ale dla już posortowanej tablicy, a trzeci dla odwrotnie-posortowanej. Domyślnie ustawiam dla każdej tablicy wielkość po 100000 elementów. Pierwszy program działa poprawnie i wyświetla czas posortowania dla każdego algorytmu, a w dwóch pozostałych programach zostaje wyświetlony tylko pierwszy wynik (dla Bubble-sort) i po chwili program się kończy z rezultatem " Process exited after 51.84 seconds with return value 3221225725" bez wyświetlania wyników dla quick-sort i heap-sort. Domyślam się że ta wartość zwracana może oznaczać stack overflow, ale czemu tak się dzieje? Jeżeli ktoś mógłby pomóc z tym problemem, to byłbym bardzo wdzięczny.

Pierwszy program (wartości losowe):

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

using namespace std;

const int N = 100000;				// wielkosc tablicy

int d[N];
int f[N];
int g[N];


//************
// Quick Sort*
//************

int partition(int A[], int p, int r){		//funkcja dzieląca tablice na mniejsze
	
	int pivot = A[r];
	int smaller = p;
	
	for(int i = p; i <= r-1; i++){
		if(A[i] <= pivot){
			swap(A[smaller], A[i]);
			smaller += 1;
		}
	}
	
	swap(A[smaller], A[r]);
	
	return smaller;
}

void quick_sort(int A[], int p, int r){		//funkcja sortująca elementy tablicy
	
	int q;
	
	if(p < r){
		q = partition(A, p, r);
		quick_sort(A, p, q-1);
		quick_sort(A, q+1, r);
	}
}



//***********
// Heap Sort*
//***********

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 > 0; i--){
		swap(A[0], A[i]); 
		max_heapify(i-1, A, 0);
	}
}



//*************
// Bubble Sort*
//*************

void bubble_sort(int size, int A[]){
	for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size-1; j++ )
        {
            if(A[j] > A[j+1] ){
                 swap( A[j], A[j+1]);
    		}
		}
    }
}

int main()
{
	srand((unsigned)time(NULL));		// konfigurowanie funkcji pseudolosującej z czasem reczywistym komputera
	 
	for(int i = 0; i < N; i++){
		d[i] = rand() % 1000;			// 	wypełnienie tablicy liczbami z zakresu 0-999;
	}
	
	for (int i = 0; i < N; i++) {
        f[i] = d[i];
        g[i] = d[i];
        }
   
	
	time_t czasStart = time( NULL );
	
	bubble_sort(N, d);			
	
	time_t czasStop = time( NULL );
	
	printf( "Bubble Sort - Uplynelo %.4fsek.\n", difftime( czasStop, czasStart ) );
	
	
	czasStart = time( NULL );
	
	quick_sort(f, 0, N-1);				
	
	czasStop = time( NULL );
	
	printf( "Quick Sort - Uplynelo %.4fsek.\n", difftime( czasStop, czasStart ) );
	
	
	
	czasStart = time( NULL );
	
        heap_sort(N, g);			
	
	czasStop = time( NULL );
	
	printf( "Heap Sort - Uplynelo %.4fsek.\n", difftime( czasStop, czasStart ) );
	
	
    return 0;
}

 

Drugi (posortowane):

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

using namespace std;

const int N = 100000;				// wielkosc tablicy

int d[N];
int f[N];
int g[N];


//************
// Quick Sort*
//************

int partition(int A[], int p, int r){		//funkcja dzieląca tablice na mniejsze
	
	int pivot = A[r];
	int smaller = p;
	
	for(int i = p; i <= r-1; i++){
		if(A[i] <= pivot){
			swap(A[smaller], A[i]);
			smaller += 1;
		}
	}
	
	swap(A[smaller], A[r]);
	
	return smaller;
}

void quick_sort(int A[], int p, int r){		//funkcja sortująca elementy tablicy
	
	int q;
	
	if(p < r){
		q = partition(A, p, r);
		quick_sort(A, p, q-1);
		quick_sort(A, q+1, r);
	}
}



//***********
// Heap Sort*
//***********

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 > 0; i--){
		swap(A[0], A[i]); 
		max_heapify(i-1, A, 0);
	}
}



//*************
// Bubble Sort*
//*************

void bubble_sort(int size, int A[]){
	for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size-1; j++ )
        {
            if(A[j] > A[j+1] ){
                 swap( A[j], A[j+1]);
    		}
		}
    }
}



int main(){
	
	
	for (int i = 0; i < N; i++) {
                d[i] = i;
		f[i] = i;
                g[i] = i;
       }

	
	cout<<"POSOROTWANE:"<<endl;
	
	time_t czasStart = time( NULL );
	
	bubble_sort(N, d);			
	
	time_t czasStop = time( NULL );
	
	printf( "Bubble Sort - Uplynelo %.4fsek.\n", difftime( czasStop, czasStart ) );
	

	czasStart = time( NULL );
	
	quick_sort(f, 0, N-1);				
	
	czasStop = time( NULL );
	
	printf( "Quick Sort - Uplynelo %.4fsek.\n", difftime( czasStop, czasStart ) );
	
	
	czasStart = time( NULL );
	
        heap_sort(N, g);			
	
	czasStop = time( NULL );
	
	printf( "Heap Sort - Uplynelo %.4fsek.\n", difftime( czasStop, czasStart ) );
	
	
	
    return 0;
}

 

Trzeci (odwrotnie posortowane):

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

using namespace std;

const int N = 100000;				// wielkosc tablicy

int d[N];
int f[N];
int g[N];


//************
// Quick Sort*
//************

int partition(int A[], int p, int r){		//funkcja dzieląca tablice na mniejsze
	
	int pivot = A[r];
	int smaller = p;
	
	for(int i = p; i <= r-1; i++){
		if(A[i] <= pivot){
			swap(A[smaller], A[i]);
			smaller += 1;
		}
	}
	
	swap(A[smaller], A[r]);
	
	return smaller;
}

void quick_sort(int A[], int p, int r){		//funkcja sortująca elementy tablicy
	
	int q;
	
	if(p < r){
		q = partition(A, p, r);
		quick_sort(A, p, q-1);
		quick_sort(A, q+1, r);
	}
}



//***********
// Heap Sort*
//***********

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 > 0; i--){
		swap(A[0], A[i]); 
		max_heapify(i-1, A, 0);
	}
}



//*************
// Bubble Sort*
//*************

void bubble_sort(int size, int A[]){
	for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size-1; j++ )
        {
            if(A[j] > A[j+1] ){
                 swap( A[j], A[j+1]);
    		}
		}
    }
}



int main(){
	
	
	for (int i = 0; i < N; i++) {
               d[i] = N-i;
		f[i] = N-i;
               g[i] = N-i;
      }

	
	cout<<"ODWROTNIE-POSOROTWANE:"<<endl;
	
	time_t czasStart = time( NULL );
	
	bubble_sort(N, d);			
	
	time_t czasStop = time( NULL );
	
	printf( "Bubble Sort - Uplynelo %.4fsek.\n", difftime( czasStop, czasStart ) );
	
	
	czasStart = time( NULL );
	
	quick_sort(f, 0, N-1);				
	
	czasStop = time( NULL );
	
	printf( "Quick Sort - Uplynelo %.4fsek.\n", difftime( czasStop, czasStart ) );
	

	
	czasStart = time( NULL );
	
        heap_sort(N, g);			
	
	czasStop = time( NULL );
	
	printf( "Heap Sort - Uplynelo %.4fsek.\n", difftime( czasStop, czasStart ) );
	
	
    return 0;
}

 

1 odpowiedź

+1 głos
odpowiedź 16 listopada 2022 przez j23 Mędrzec (194,920 p.)

Zgaduję, że w przypadku zbiorów uporządkowanych partition dzieli zbiór tak, że jest zbiór jednoelementowy i zbiór z pozostałymi elementami (lub na odwrót), co powoduje głęboką rekurencję i w konsekwencji przepełnienie stosu (podobny problem jest z drzewami binarnym nierównoważonymi, gdy dodaje się elementy uporządkowane - powstaje de facto lista).

Przerwij rekurencję, jeśli partition wykaże, że zbiór jest uporządkowany.

komentarz 16 listopada 2022 przez MKolaj15 Bywalec (2,270 p.)
Super, dzięki za radę!

Podobne pytania

0 głosów
1 odpowiedź 481 wizyt
pytanie zadane 17 października 2021 w C i C++ przez Xodi Początkujący (260 p.)
0 głosów
1 odpowiedź 4,419 wizyt
pytanie zadane 13 czerwca 2018 w C i C++ przez RedBull9k Nowicjusz (120 p.)
+1 głos
1 odpowiedź 193 wizyt

92,454 zapytań

141,262 odpowiedzi

319,089 komentarzy

61,854 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

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

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!

...