poziom początkujący - Sortowanie w C

0

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

}

0

int tablica[100000]; to jest alokowane na stosie.
Zrób dynamicznie przez new lub vector.

2

Sprawdzaj czy elementy jest mniejsze od sizeof(tablica) / sizeof(tablica[0])

1

Poza tym o czym mówi @vpiotr, to jeszcze masz błąd taki:
robisz

    while (tablica[j - 1] > x && j > 0) {

a miało być

    while (j > 0 && tablica[j - 1] > x) {

Poza tym, czytasz jakieś podrzędne podręczniki - skoro widzisz komunikat received SIGSEGV, Segmentation fault, to jesteś na Linuksie / macOS? Jeśli tak, to system("pause"); nie ma żadnego sensu, to zadziała tylko na Windowsie. Równie dobrze możesz to wywalić.

Poza tym, to co robisz dla każdego j w main zawiera zbędne powtórzenia (ciężko taki kod debugować).

poziom początkujący - Sortowanie w C

1 użytkowników online, w tym zalogowanych: 0, gości: 1

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami