• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem z programem porównującym 2 algorytmy sortujące tak zwany quick sort i algortym sortujący poprzez zliczanie

Object Storage Arubacloud
0 głosów
125 wizyt
pytanie zadane 5 lipca 2016 w C i C++ przez famousghost Początkujący (430 p.)
Mam problem nie wiem czemu te programy dla wartości 10 spokojnie sortują a jeżeli dam im na przykład 32 to nagle zaczynają wariować oczywiście mowie tutaj o rozmiarze tablicy nie wiem czemu ale jeżeli zmienię z tab[32] na tab[33] a wyśle i tak 32 liczby do funkcji to wtedy sortuje poprawnie oczywiście nie wiem tego dla wszystkich wartości jakie istnieją bo jest ich bardzo dużo.Z tego co liczyłem na kartce algorytm się sprawdza, lecz problem jest taki, iż nie wiem czy to co napisałem jest ok proszę o pomoc jeżeli ktoś jest w stanie mi tutaj ogarnąć czemu zmiana tak tablicy powoduję poprawne wykonywanie programu dla większych tablic.
#include <iostream>
#include <windows.h>
#include <time.h>
#include <conio.h>
#include <iomanip>

using namespace std;

int podzielic(int tab[],int lewa,int prawa);
void QSort(int tab[],int lewa,int prawa);
void SortowanieZliczanie(int tab[],int wynik[],int dlugosc_tablicy);
void losownie(int tab1[],int tab2[],int n);

clock_t start,stop;

int main()
{
    int tab1Q[32],tab2Q[64],tab3Q[128],tab4Q[256],tab5Q[512],tab6Q[1024];
    int tab1Z[32],tab2Z[64],tab3Z[128],tab4Z[256],tab5Z[512],tab6Z[1024];
    int tab1Zw[32],tab2Zw[64],tab3Zw[128],tab4Zw[256],tab5Zw[512],tab6Zw[1024];
    double czas,czasQ=0,czasZ=0,Srednia_Q,Srednia_Z;
    srand(time(NULL));

    for(int j=0;j<4;j++)
    {
        losownie(tab1Q,tab1Z,32);
        cout<<endl<<endl<<"tablica dla QuickSort'a:"<<endl;
        for(int i=0;i<32;i++)
        {
            cout<<tab1Q[i]<<", ";
        }
        cout<<endl<<endl<<endl<<"tablica dla Sortowania Przez Zliczanie:"<<endl;
        for(int i=0;i<32;i++)
        {
            cout<<tab1Z[i]<<", ";
        }
        cout<<endl<<endl;
        start = clock();
        QSort(tab1Q,0,32);
        stop = clock();
        czas = (double)(stop-start)/CLOCKS_PER_SEC;
        cout<<"wykonano quicksort w "<<setprecision(100)<<czas<<" s"<<endl<<endl<<endl;
        czasQ+=czas;
        for(int i=0;i<32;i++)
        {
            cout<<tab1Q[i]<<", ";
        }
        cout<<endl<<endl;
        start = clock();
        SortowanieZliczanie(tab1Z,tab1Zw,32);
        stop = clock();
        czas = (double)(stop-start)/CLOCKS_PER_SEC;
        cout<<"wykonano zliczanie w "<<setprecision(100)<<czas<<" s"<<endl<<endl<<endl;
        czasZ+=czas;
        for(int i=0;i<32;i++)
        {
            cout<<tab1Zw[i]<<", ";
        }
    }
    Srednia_Q=czasQ/4;
    Srednia_Z=czasZ/4;
    cout<<endl<<endl<<"Sredni czas liczenia dla tablicy 32 elementy QuickSort "<<Srednia_Q<<" s"<<endl<<endl;
    cout<<"Sredni czas liczenia dla tablicy 32 elementy Zliczanie "<<Srednia_Z<<" s"<<endl<<endl;
    system("pause");
    system("cls");
    return 0;
}

void losownie(int tab1[],int tab2[],int n)
{
    for(int i=0;i<32;i++)
    {
        tab1[i]=rand()%100+1;
    }
    for(int i=0;i<32;i++)
    {
        tab2[i]=tab1[i];
    }
}

int podzielic(int tab[],int lewa,int prawa)
{
    int x= tab[lewa];
    int i = lewa, j= prawa, w;// i oraz j to sa indeksy tablicy
    while(true)//petla nieskonczona - wychodzimy z nie tylko przez return j
    {
        while(tab[j]>x)
            j--;
        while(tab[i]<x)
            i++;
        if(i<j) // zamieniamy miejscami w przypadku gdy i mniejszy od j
        {
            w = tab[i];
            tab[i]= tab[j];
            tab[j]=w;
            i++;
            j--;
        }
        else
            return j;
    }
}
void QSort(int tab[],int lewa,int prawa)//sortowanie szybkie
{
int q;
    if(lewa < prawa)
    {
        q = podzielic(tab,lewa,prawa);
        QSort(tab,lewa,q);
        QSort(tab,q+1,prawa);
    }
}
void SortowanieZliczanie(int tab[],int wynik[],int dlugosc_tablicy)
{
    int wartosc_MAX_liczb=100;

    wynik[dlugosc_tablicy];

    int pomoc[wartosc_MAX_liczb];

    for(int i=0;i<wartosc_MAX_liczb;i++)
    {
        pomoc[i]=0;
    }

    for(int j=0;j<dlugosc_tablicy;j++)
    {
        pomoc[tab[j]]=pomoc[tab[j]]+1;
    }
    for(int i=1;i<wartosc_MAX_liczb;i++)
    {
        pomoc[i]=pomoc[i]+pomoc[i-1];
    }
    for(int j=dlugosc_tablicy-1;j>=0;j--)
    {
        wynik[pomoc[tab[j]]-1]=tab[j];
        pomoc[tab[j]]=pomoc[tab[j]]-1;
    }

}

Pozdrawiam famousghost

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
2 odpowiedzi 450 wizyt
pytanie zadane 6 kwietnia 2016 w C i C++ przez k171 Nowicjusz (120 p.)
0 głosów
0 odpowiedzi 194 wizyt
pytanie zadane 27 listopada 2017 w C i C++ przez barti22062 Początkujący (370 p.)
0 głosów
1 odpowiedź 132 wizyt

92,551 zapytań

141,399 odpowiedzi

319,529 komentarzy

61,937 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

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

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!

...