Mam pytanie: chcę posortować ilość elementów w tablicy, jednak dostaję informację o błędzie w randzie ( tablica[i] = (rand() % 201) - 100;) - program received SIGSEGV, Segmentation fault. Nie bardzo wiem, jak to naprawić. Program działa dla wartośći 50000, 75000, 100000. Powyżej 100000 nic nie działa. Nie wiem, jak mam to naprawić.
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <cstdlib>
#include<iostream>
void funkcja(int tablica[], int a)
{
int i;
for (i = 0; i < a; i++)
{
tablica[i] = (rand() % 201) - 100;
}
}
void bubblesort(int tablica[], int b)
{
int x;
for (int i = 0; i < b; i++)
{
for (int j = b - 1; j > i; j--)
if (tablica[j] < tablica[j - 1])
{
x = tablica[j - 1];
tablica[j - 1] = tablica[j];
tablica[j] = x;
}
}
}
void shell(int tablica[], int b)
{
int i, j, y, z;
for (z = 1; z < b; z = 3 * z + 1);
z = z/9;
if (!z) z++;
while (z)
{
for (j = b - z - 1; j >= 0; j--)
{
y = tablica[j];
i = j + z;
while ((i < b) && (y > tablica[i]))
{
tablica[i - z] = tablica[i];
i = i+z;
}
tablica[i - z] = y;
}
z = z/3;
}
}
void quick(int tablica[], int c)
{
int i, j, x, wybrany;
i = c; j = 0;
wybrany = tablica[rand() % (c - j) + c];
while (i < j)
{
while (tablica[i] < wybrany) i++;
while (tablica[j] > wybrany) j--;
if (i <= j)
{
x = tablica[i]; tablica[i] = tablica[j]; tablica[j] = x;
i++; j--;
}
}
if (i < 0) { quick(tablica, i); }
if (c < j) { quick(tablica, c); }
}
void heapify(int tablica[], int n)
{
int i;
int maxymalny = n;
int swap;
int lewy = 2 * i + 1;
int prawy = 2 * i + 2;
if (lewy < n && tablica[lewy] > tablica[maxymalny])
maxymalny = lewy;
if (prawy < n && tablica[prawy] > tablica[maxymalny])
maxymalny = prawy;
if (maxymalny != i)
{
std::swap(tablica[i], tablica[maxymalny]);
heapify(tablica, n);
}
}
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapsort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void insertion(int tablica[], int b)
{
int j, x;
for (int i = 1; i < b; i++)
{
j = i; x = tablica[j];
while (tablica[j - 1] > x && j > 0)
{
tablica[j] = tablica[j - 1];
j--;
}
tablica[j] = x;
}
}
void selection(int tablica[], int b)
{
int k, x;
for (int i = 0; i < b - 1; i++)
{
k = i; x = tablica[i];
for (int j = i + 1; j < b; j++)
if (tablica[j] < x)
{
k = j; x = tablica[j];
}
if (k != i) { tablica[k] = tablica[i]; tablica[i] = x; }
}
}
void inverted(int tablica[], int a)
{
int i, temporary;
for (int i = 0; i < a / 2; i++) {
temporary = tablica[a - i - 1];
tablica[a - i - 1] = tablica[i];
tablica[i] = temporary;
}
}
void randomArray(int tablica[],int count)
{
for(int i=0;i<count;++i) tablica[i]=(rand()%201)-100;
}
typedef void anysort(int *tab,int n);
struct NamedCall { const char *name; anysort *fun; };
struct NamedCall sorts[]=
{
{ "bąbelkowe", &bubblesort },
{ "heap", &heapsort },
{ "shell", &shell },
{ "szybkie", &quick },
};
struct NamedCall prepares[]=
{
{ "losowa", &randomArray },
{ "odwrotna", &inverted },
};
int main()
{
{
int i, j, elementy;
int tablica[100000];
clock_t start, end;
double diff;
srand(time(NULL));
printf("Ile elementow w tablicy chcesz posortowac?: \n");
scanf("%d", &elementy);
for (j = 1; j < 7; j++)
{
funkcja(tablica, elementy);
if (j == 1)
{
for(int i = 0; i<elementy;i++)
{
tablica[i] = -100 + rand() % (100 - (-100) + 1);
}
start = clock();
bubblesort(tablica, elementy);
end = clock();
diff = difftime(end , start)/CLOCKS_PER_SEC;
printf("\nbubblesort losowo: %f sec\n", diff / 10);
start = clock();
bubblesort(tablica, elementy);
end = clock();
diff = difftime(end , start)/CLOCKS_PER_SEC;
printf("\nw gore: %f sec\n", diff / 10);
inverted(tablica, elementy);
start = clock();
bubblesort(tablica, elementy);
end = clock();
diff = difftime(end , start)/CLOCKS_PER_SEC;
printf("\nodwrotnie: %f sec\n", diff / 10);
printf(" \n \n");
}
if (j == 2)
{
for(int i = 0; i<elementy;i++)
{
tablica[i] = -100 + rand() % (100 - (-100) + 1);
}
start = clock();
insertion(tablica, elementy);
end = clock();
diff = difftime(end, start)/CLOCKS_PER_SEC;
printf("\ninsertionsort losowo: %f sec\n", diff);
start = clock();
insertion(tablica, elementy);
end = clock();
diff = difftime(end, start)/CLOCKS_PER_SEC;
printf("\nw gore: %f sec\n", diff);
insertion(tablica, elementy);
start = clock();
insertion(tablica, elementy);
end = clock();
diff = difftime(end, start)/CLOCKS_PER_SEC;
printf("\nw dol: %f sec\n", diff);
printf(" \n \n");
}
if (j == 3)
{
for(int i = 0; i<elementy;i++)
{
tablica[i] = -100 + rand() % (100 - (-100) + 1);
}
start = clock();
selection(tablica, elementy);
end = clock();
diff = difftime(end, start)/CLOCKS_PER_SEC;
printf("\nselectionsort losowo: %f sec\n", diff);
start = clock();
selection(tablica, elementy);
end = clock();
diff = difftime(end, start)/CLOCKS_PER_SEC;
printf("\nw gore: %f sec\n", diff);
inverted(tablica, elementy);
start = clock();
selection(tablica, elementy);
end = clock();
diff = difftime(end, start)/CLOCKS_PER_SEC;
printf("\nw dol: %f sec\n", diff);
printf(" \n \n");
}
if (j == 4)
{
for(int i = 0; i<elementy;i++)
{
tablica[i] = -100 + rand() % (100 - (-100) + 1);
}
start = clock();
heapsort(tablica, elementy);
end = clock();
diff = difftime(end, start)/CLOCKS_PER_SEC;
printf("\nheapsort losowo: %f sec\n", diff);
start = clock();
heapsort(tablica, elementy);
end = clock();
diff = difftime(end, start)/CLOCKS_PER_SEC;
printf("\nw gore: %f sec\n", diff);
inverted(tablica, elementy);
start = clock();
heapsort(tablica, elementy);
end = clock();
diff = difftime(end, start)/CLOCKS_PER_SEC;
printf("\nw dol: %f sec\n", diff);
printf(" \n \n");
}
if (j == 5)
{
for(int i = 0; i<elementy;i++)
{
tablica[i] = -100 + rand() % (100 - (-100) + 1);
}
start = clock();
quick(tablica, elementy - 1);
end = clock();
diff = difftime(end, start);
printf("\nquicksort losowo: %f sec\n", diff/CLOCKS_PER_SEC);
start = clock();
quick(tablica, elementy - 1);
end = clock();
diff = difftime(end, start);
printf("\nw gore: %f sec\n", diff/CLOCKS_PER_SEC);
inverted(tablica, elementy);
start = clock();
quick(tablica, elementy - 1);
end = clock();
diff = difftime(end, start);
printf("\nw dol %f sec\n", diff/CLOCKS_PER_SEC);
printf(" \n \n");
}
if (j == 6)
{
for(int i = 0; i<elementy;i++)
{
tablica[i] = -100 + rand() % (100 - (-100) + 1);
}
start = clock();
shell(tablica, elementy);
end = clock();
diff = difftime(end, start);
printf("\nshellsort losowo: %f sec\n", diff/CLOCKS_PER_SEC);
start = clock();
shell(tablica, elementy);
end = clock();
diff = difftime(end, start);
printf("\nw gore: %f sec\n", diff/CLOCKS_PER_SEC);
inverted(tablica, elementy);
start = clock();
shell(tablica, elementy);
end = clock();
diff = difftime(end, start);
printf("\nw dol: %f sec\n", diff/CLOCKS_PER_SEC);
printf(" \n \n");
}
}
system("pause");
}
}