Implementacja algorytmu sortowania przez scalanie sprawia problemy – dlaczego?

0

Witam mam taki problem z implementacja Algorytmu sortowania przez scalanie. Otóż piszę program przyrównujący czas sortowania wybranych przeze mnie algorytmów sortowania dla identycznej liczby n wszystko działa fajnie do momentu przyłączenia się do tego programu algorytmu sortowania przez scalanie .

UWAGA KOD JEST DŁUGI

#include <iostream>
using namespace std;
#include <time.h>
#include <windows.h>
#include <iomanip> 
int ile;
clock_t start,stop;
double czas;
void sortowanie_babelkowe(int *tab,int n)  //ok
{
  for(int i=1;i<n;i++)
    {
        for(int j=n-1;j>=1;j--)
        {
            if(tab[j]>tab[j-1])
            {
                int bufor;
                bufor=tab[j-1];
                tab[j-1]=tab[j];
                tab[j]=bufor;

            }
        }
    }

}

void quicksort(int *tablica, int lewy, int prawy) //ok
{
    int v=tablica[(lewy+prawy)/2];
    int i,j,x;
    i=lewy;
    j=prawy;
    do{
        while (tablica[i]>v) i++;
        while (tablica[j]<v) j--;
        if (i<=j){
            x=tablica[i];
            tablica[i]=tablica[j];
            tablica[j]=x;
            i++; j--;
        }
    }while (i<=j);
    if (j>lewy) quicksort(tablica,lewy, j);
    if (i<prawy) quicksort(tablica, i, prawy);
}

void Selection( int *tablica11, int size ) //ok
{
    int k;
    for( int i = 0; i < size; i++ )
    {
        k = i;
        for( int j = i + 1; j < size; j++ )
        if( tablica11[ j ] > tablica11[ k ] )
             k = j;

        swap( tablica11[ k ], tablica11[ i ] );
    }
}

void Insertion( int *tablica111, int size ) //ok
{
    int temp, j;

    for( int i = 1; i < size; i++ )
    {
        temp = tablica111[ i ];

        for( j = i - 1; j >= 0 && tablica111[ j ] < temp; j-- )
             tablica111[ j + 1 ] = tablica111[ j ];

        tablica111[ j + 1 ] = temp;
    }
}

int *pom; //tablica pomocnicza, potrzebna przy scalaniu

//scalenie posortowanych podtablic
void scal(int *tablica555, int lewy, int srodek, int prawy) 
{
    int i = lewy, j = srodek + 1;

  //kopiujemy lewą i prawą część tablicy do tablicy pomocniczej
  for(int i = lewy;i<=prawy; i++) 
    pom[i] = tablica555[i];  

  //scalenie dwóch podtablic pomocniczych i zapisanie ich 
  //we własciwej tablicy
  for(int k=lewy;k<=prawy;k++) 
  if(i<=srodek)
    if(j <= prawy)
         if(pom[j]<pom[i])
             tablica555[k] = pom[j++];
         else
             tablica555[k] = pom[i++];
    else
        tablica555[k] = pom[i++];
  else
      tablica555[k] = pom[j++];
}

void sortowanie_przez_scalanie(int *tablica666,int lewy, int prawy)
{
    //gdy mamy jeden element, to jest on już posortowany
    if(prawy<=lewy) return; 

    //znajdujemy srodek podtablicy
    int srodek = (prawy+lewy)/2;

    //dzielimy tablice na częsć lewą i prawa
    sortowanie_przez_scalanie(tablica666, lewy, srodek); 
    sortowanie_przez_scalanie(tablica666, srodek+1, prawy);

    //scalamy dwie już posortowane tablice
    scal(tablica666, lewy, srodek, prawy);
}

int main()
{
   cout<<"Porownanie czasow sortowanie"<<endl;
       cout<<"ile losobywch liczb w tablicy";
       cin>>ile;
       //dynamiczne alokowanie tablicy

       int*tablica;
       tablica=new int[ile];

        int*tablica2;
       tablica2=new int[ile];

       int *tablica3;
       tablica3=new int[ile];

       int *tablica4;
       tablica4=new int[ile];

       int *tablica5;
       tablica5=new int[ile];

       int *tablica6;
          tablica6=new int [ile];

       //genetator
       srand(time(NULL));

       //wczytywanie generatora
        for(int i=0;i<ile;i++)
       {
           tablica[i]=rand()%100000+1;

       }

        //przepisanie tablicy do tablicy2

        for(int i=0;i<ile;i++)
       {
           tablica2[i]=tablica[i];

       }

        for(int i=0;i<ile;i++)
       {
           tablica3[i]=tablica[i];

       }

            for(int i=0;i<ile;i++)
       {
           tablica4[i]=tablica[i];

       }

            for(int i=0;i<ile;i++)
       {
           tablica5[i]=tablica[i];

       }

                    for(int i=0;i<ile;i++)
       {
           tablica6[i]=tablica[i];

       }

        /*
       cout<<"PRZED SORTOWANIEM:"<<endl;
       for(int i=0;i<ile;i++)
        {
        cout<<tablica[i]<<" ";

       }
        */

    cout<<"sortuje teraz Algorytmem babelkowym czekac!"<<endl;
       start=clock();
       sortowanie_babelkowe(tablica,ile);
       stop=clock();
       cout<< setprecision(2);
       czas=(double)(stop-start)/CLOCKS_PER_SEC;
        /*
       cout<<"Po SORTOWANIU:"<<endl;
       for(int i=0;i<ile;i++)
        {
        cout<<tablica[i]<<" ";

       }
        */
      cout<<"CZAS SORTOWANIA algorytmu babelkowego:"<<czas<<"s"<<endl;

      /* cout<<"PRZED SORTOWANIEM:"<<endl;
       for(int i=0;i<ile;i++)
        {
        cout<<tablica2[i]<<" ";

       }
    */  

    cout<<"sortuje teraz algorytmem QuickSort czekac!"<<endl;
       start=clock();
       quicksort(tablica2,0,ile-1);
       stop=clock();
        cout<< setprecision(2);
       czas=(double)(stop-start)/CLOCKS_PER_SEC;
       /*     
       cout<<"PO SORTOWANIU:"<<endl;
        for(int i=0;i<ile;i++)
        {
          cout<<tablica2[i]<<" ";

        }

     */
       cout<<"CZAS SORTOWANIA algorytmu QUICKSORT:"<<czas<<"s"<<endl;

    /* cout<<"PRZED SORTOWANIEM:"<<endl;
    for(int i=0;i<ile;i++)
    {
    cout<<tablica3[i]<<" ";
    }
    */  

    cout<<"sortuje teraz algorytmem SELECTION czekac!"<<endl;
    start=clock();
    Selection(tablica3,ile);
     stop=clock();
    cout<< setprecision(2);
       czas=(double)(stop-start)/CLOCKS_PER_SEC;
       /*     
       cout<<"PO SORTOWANIU:"<<endl;
        for(int i=0;i<ile;i++)
        {
          cout<<tablica3[i]<<" ";

        }

     */

        cout<<"CZAS SORTOWANIA algorytmu SELECTION:"<<czas<<"s"<<endl;

       /* cout<<"PRZED SORTOWANIEM:"<<endl;
       for(int i=0;i<ile;i++)
        {
        cout<<tablica4[i]<<" ";

       }
    */  

    cout<<"sortuje teraz algorytmem INSERTION czekac!"<<endl;
       start=clock();
       Insertion(tablica4,ile);
       stop=clock();
        cout<< setprecision(2);
       czas=(double)(stop-start)/CLOCKS_PER_SEC;
       /*     
       cout<<"PO SORTOWANIU:"<<endl;
        for(int i=0;i<ile;i++)
        {
          cout<<tablica4[i]<<" ";

        }

     */
       cout<<"CZAS SORTOWANIA algorytmu INSERTION:"<<czas<<"s"<<endl;

       /*
       cout<<"PRZED SORTOWANIEM:"<<endl;
       for(int i=0;i<ile;i++)
        {
        cout<<tablica[i]<<" ";

       }
        */

    cout<<"sortuje teraz Algorytmem SCALANIA czekac!"<<endl;
       start=clock();
       sortowanie_przez_scalanie(tablica6,0,ile-1);
       stop=clock();
       cout<< setprecision(2);
       czas=(double)(stop-start)/CLOCKS_PER_SEC;
        /*
       cout<<"Po SORTOWANIU:"<<endl;
       for(int i=0;i<ile;i++)
        {
        cout<<tablica[i]<<" ";

       }
        */
      cout<<"CZAS SORTOWANIA algorytmu SCALANIA:"<<czas<<"s"<<endl;

        delete[] tablica;
        delete[] tablica2;
        delete[] tablica3;
        delete[] tablica4;
        delete[] tablica5;

        system("pause");
return 0;   
}
2
Cisi204 napisał(a):

Otóż piszę program przyrównujący czas sortowania wybranych przeze mnie algorytmów sortowania dla identycznej liczby n wszystko działa fajnie do momentu przyłączenia się do tego programu algorytmu sortowania przez scalanie .

No to fajnie – a teraz napisz konkretnie w czym jest problem.

0

Mój problem polega na tym jak przyłączyć do tego kodu algorytm sortowania przez scalanie aby całość kodu wykonywała się bez żadnego problemu.

2

Najlepiej to stwórz sobie oddzielny, mały projekt i tam twórz oraz testuj funkcję sortującą.Jak już będzie działać dobrze to przenosisz do tego projektu - sam tak postępuję.

1
Cisi204 napisał(a):

Mój problem polega na tym jak przyłączyć do tego kodu algorytm sortowania przez scalanie aby całość kodu wykonywała się bez żadnego problemu.

Na czym polega problem? Masz crasha? Coś się nie kompiluje? Coś się nie linkuje? Program się wiesza?
To że masz problem to wiemy choćby po tym, że założyłeś watek.


Dobra już widzę. Używasz zmiennej globalnej pom, która jest wskaźnikiem nie wskazującym na cokolwiek (jako zmienna globalna jest zainicjalizowana do NULL), a używasz jej tak, jakby pokazywała na coś sensownego, więc kończy się SEG FAULT.

Po pozbyciu się zmiennych globalnych, kompilator nawet zrzędzi, że coś jest chyba nie tak: https://wandbox.org/permlink/gsnSprj6Upb8RlK9

Jeszcze koniecznie przeczytaj to: https://dsp.krzaq.cc/post/176[...]xx-kiedy-uzywac-new-i-delete/

Po kiego grzyba robisz nazwy argumentów funkcji tablica666 tablica555 itp? Lubisz sobie życie utrudniać?

0

Czy te rozwiązanie jest prawidłowe ?

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

using namespace std;

//scalenie posortowanych podtablic
void scal(int* tablica555, int lewy, int srodek, int prawy)
{
    int*pom=tablica555; //tablica pomocnicza, potrzebna przy scalaniu
    int i = lewy, j = srodek + 1;

    //kopiujemy lewą i prawą część tablicy do tablicy pomocniczej
    for (int i = lewy; i <= prawy; i++)
        pom[i] = tablica555[i];

    //scalenie dwóch podtablic pomocniczych i zapisanie ich
    //we własciwej tablicy
    for (int k = lewy; k <= prawy; k++)
        if (i <= srodek)
            if (j <= prawy)
                if (pom[j] < pom[i])
                    tablica555[k] = pom[j++];
                else
                    tablica555[k] = pom[i++];
            else
                tablica555[k] = pom[i++];
        else
            tablica555[k] = pom[j++];
}

void sortowanie_przez_scalanie(int* tablica555, int lewy, int prawy)
{
    //gdy mamy jeden element, to jest on już posortowany
    if (prawy <= lewy)
        return;

    //znajdujemy srodek podtablicy
    int srodek = (prawy + lewy) / 2;

    //dzielimy tablice na częsć lewą i prawa
    sortowanie_przez_scalanie(tablica555, lewy, srodek);
    sortowanie_przez_scalanie(tablica555, srodek + 1, prawy);

    //scalamy dwie już posortowane tablice
    scal(tablica555, lewy, srodek, prawy);
}

int main()
{
    int ile;
    clock_t start, stop;
    double czas;

    cout << "Porownanie czasow sortowanie" << endl;
    cout << "ile losobywch liczb w tablicy";
    cin >> ile;
    //dynamiczne alokowanie tablicy

    int* tablica;
    tablica = new int[ile];

    int* tablica2;
    tablica2 = new int[ile];

    int* tablica3;
    tablica3 = new int[ile];

    int* tablica4;
    tablica4 = new int[ile];

    int* tablica5;
    tablica5 = new int[ile];

    int* pom;
    pom = new int[ile];

    //genetator
    srand(time(NULL));

    //wczytywanie generatora
    for (int i = 0; i < ile; i++) {
        tablica[i] = rand() % 100000 + 1;
    }

    //przepisanie tablicy do tablicy2

    for (int i = 0; i < ile; i++) {
        tablica2[i] = tablica[i];
    }

    for (int i = 0; i < ile; i++) {
        tablica3[i] = tablica[i];
    }

    for (int i = 0; i < ile; i++) {
        tablica4[i] = tablica[i];
    }

    for (int i = 0; i < ile; i++) {
        tablica5[i] = tablica[i];
    }

    for (int i = 0; i < ile; i++) {
        pom[i] = tablica[i];
    }

    cout << "sortuje teraz Algorytmem SCALANIA czekac!" << endl;
    start = clock();
    sortowanie_przez_scalanie(tablica5, 0, ile - 1);
    stop = clock();
    cout << setprecision(2);
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    /*
       cout<<"Po SORTOWANIU:"<<endl;
       for(int i=0;i<ile;i++)
        {
        cout<<tablica[i]<<" ";

       }
        */
    cout << "CZAS SORTOWANIA algorytmu SCALANIA:" << czas << "s" << endl;

    delete[] tablica;
    delete[] tablica2;
    delete[] tablica3;
    delete[] tablica4;
    delete[] tablica5;
    delete[] pom;

    system("pause");
    return 0;
}
1

NIE!
Napisz sobie test do weryfikowania czy sortowanie działa poprawnie.

0

Odpalam programik i nie ma żadnych bugów

1
Cisi204 napisał(a):

Odpalam programik i nie ma żadnych bugów

Nie o to chodziło. Tworzysz sobie tablicę 5 liczb {1,5,4,3,2} i sprawdzasz, czy posortowało dobrze. Jak tak, to na drugi ogień tablica 100 liczb losowych, w tym ujemnych, i patrzysz, czy sortowanie działa. Jeśli odpowiedź będzie twierdząca wtedy można uznać, że algorytm jest zaimplementowany poprawnie.

1

dopsiz sobie cos takiego:

bool testSortowania(const std::string& nazwa, void(*sortuj)(int *, int ), const std::vector<int>& daneTestowe)
{
     auto doPosortowania = daneTestowe;
     auto oczekiwane = daneTestowe;
     std::sort(oczekiwane.begin(), oczekiwane.end());

     sortuj(doPosortowania.data(), doPosortowania.size());

     std::cout << "\n[ Start ]: " << nazwa;
     if (std::equal(oczekiwane.begin(), oczekiwane.end(), doPosortowania.begin())) {
         std::cout << "\n[ Passed ]: " << nazwa << '\n';
         return true;
     }
     std::cout << "\n[ FAILED ]: " << nazwa << '\n';
     return false;
}

int testujSortowanie(const std::string& nazwa, void(*sortuj)(int *data, int size))
{
      int liczbaBledow = 
      (testSortowania(nazwa + " puste dane", sortuj, {}) ? 0 : 1) +
      (testSortowania(nazwa + " jedna wartosc", sortuj, { 1 }) ? 0 : 1) +
      (testSortowania(nazwa + " dwie wartosci posrotowane", sortuj, { 1, 2 }) ? 0 : 1) +
      (testSortowania(nazwa + " dwie wartosci odwrotnie posrotowane", sortuj, { 2,1 }) ? 0 : 1) +
      (testSortowania(nazwa + " 5 wartości", sortuj, { 2,1, 4, 0, 3 }) ? 0 : 1);

      if (liczbaBledow == 0) {
           cout << "\n[" << nazwa << "] Brak bledów.\n";
      } else {
           cout << "\n[" << nazwa << "] Liczba bledów." <<  liczbaBledow <<" !!!\n";
      }
      return liczbaBledow;
}

liczbaBledow = 
     testujSortowanie("sortowanie_babelkowe", sortowanie_babelkowe) +
     testujSortowanie("Selection", Selection);
.....

Albo poczytaj sobie o gtest.

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