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;
}