• 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,804 wizyt
pytanie zadane 15 kwietnia 2016 w Nasze poradniki przez Mirosław Zelent Nałogowiec (29,220 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 2017 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 2017 przez unknown Nałogowiec (39,260 p.)
Cześć po przecinku zostanie obcięta.
komentarz 3 września 2017 przez Danon99 Nowicjusz (140 p.)
Dzięki!
1
komentarz 3 września 2017 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ź 104 wizyt
+1 głos
1 odpowiedź 570 wizyt
+2 głosów
0 odpowiedzi 295 wizyt
Porady nie od parady
Wynikowy wygląd pytania, odpowiedzi czy komentarza, różni się od tego zaprezentowanego w edytorze postów. Stosuj więc funkcję Podgląd posta znajdującą się pod edytorem, aby upewnić się, czy na pewno ostateczny rezultat ci odpowiada.
Ciekawy innych porad? Odwiedź tę stronę!

45,516 zapytań

85,820 odpowiedzi

171,213 komentarzy

22,082 pasjonatów

Przeglądających: 119
Pasjonatów: 5 Gości: 114

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.

...