• 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

Object Storage Arubacloud
0 głosów
224 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 (195,220 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ź 530 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,608 wizyt
pytanie zadane 13 czerwca 2018 w C i C++ przez RedBull9k Nowicjusz (120 p.)
0 głosów
0 odpowiedzi 114 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!

...