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

[CR] C++ (#14): Sortowanie. Złożoność algorytmów

+3 głosów
1,581 wizyt
pytanie zadane 15 kwietnia 2016 w Nasze poradniki przez Mirosław Zelent Nałogowiec (28,430 p.)

CR = Code Review. O co chodzi? Zajrzyj tutaj
Pełna lista wszystkich Code Review? Zajrzyj tutaj

https://www.youtube.com/watch?v=LKiaoV86iJo

Kod z odcinka:

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

using namespace std;

int ile;
clock_t start,stop;
double czas;

void sortowanie_babelkowe(int *tab, int n)
{
    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)
{
    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);
}

int main()
{
    cout << "Porownanie czasow sortowania v.1" << endl;

    cout<<"Ile losowych liczb w tablicy: ";
    cin>>ile;

    //dynamiczna alokacja tablicy
    int *tablica;
    tablica=new int [ile];

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

    //inicjowanie generatora
    srand(time(NULL));

    //wczytywanie losowych liczb do tablicy
    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];
    }

/*
        cout<<"Przed posortowaniem: "<<endl;
        for(int i=0; i<ile; i++)
        {
            cout<<tablica2[i]<<" ";
        }
*/
    cout<<"Sortuje teraz babelkowo. Prosze czekac!"<<endl;
    start = clock();
    sortowanie_babelkowe(tablica,ile);
    stop = clock();
    czas = (double)(stop-start) / CLOCKS_PER_SEC;
    cout<<endl<<"Czas sortowania babelkowego: "<<czas<<" s"<<endl;

    cout<<endl<<"Sortuje teraz algorytmem quicksort. Prosze czekac!"<<endl;
    start = clock();
    quicksort(tablica2, 0, ile-1);
    stop = clock();
    czas = (double)(stop-start) / CLOCKS_PER_SEC;
    cout<<endl<<"Czas sortowania quicksort: "<<czas<<" s"<<endl;

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

    delete [] tablica;
    delete [] tablica2;

    return 0;
}

Paczka z odcinka: POBIERZ​

1 odpowiedź

0 głosów
odpowiedź 3 września przez Danon99 Nowicjusz (140 p.)
Domyślam się, że to może być błachostka ale nie daje mi to spokoju.

Mam na myśli fragment kodu funkcji quicksort w którym obliczamy wartość "v":

int v=tablica[(lewy+prawy)/2];

A moje pytanie brzmi:

Co jeśli wartość (lewy+prawy) równać się będzie liczbie nieparzystej?

Wydaje mi się, że int nie przyjmie takiej liczby, ponieważ będzie z ułamkiem 0,5.

Po drugie w tablicy nie ma miejsc z indeksem 0,5.

Nasuwa mi się jedynie to, że w jakiś sposób liczba tutaj zaokrągla się w jedną albo drugą stronę. Byłbym wdzięczny gdyby ktoś mi to wyjaśnił. Dzięki!
komentarz 3 września przez unknown Nałogowiec (39,260 p.)
Cześć po przecinku zostanie obcięta.
komentarz 3 września przez Danon99 Nowicjusz (140 p.)
Dzięki!
1
komentarz 3 września przez Hipcio Nałogowiec (46,180 p.)

Dzielenie liczb całkowitych (np int) jest inne od zmiennoprzecinkowych. Przykład:

cout << 1/2 << "\n";
cout << 1.f/2.f << "\n";

Podobne pytania

0 głosów
1 odpowiedź 85 wizyt
+1 głos
1 odpowiedź 514 wizyt
+2 głosów
0 odpowiedzi 257 wizyt

42,445 zapytań

81,749 odpowiedzi

162,269 komentarzy

20,388 pasjonatów

Przeglądających: 102
Pasjonatów: 2 Gości: 100

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...