• 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

VPS Starter Arubacloud
+3 głosów
9,509 wizyt
pytanie zadane 15 kwietnia 2016 w Nasze poradniki przez Mirosław Zelent Nałogowiec (34,750 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​

2 odpowiedzi

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,560 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 niezalogowany

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

cout << 1/2 << "\n";
cout << 1.f/2.f << "\n";
0 głosów
odpowiedź 24 marca 2018 przez startCoding Obywatel (1,210 p.)
edycja 24 marca 2018 przez startCoding
W minucie 5:57 jest według mnie błąd, bo nie będziemy powtarzać procesu sortowania "tyle razy ile jest liczb w tablicy" tylko o jeden mniej niż tych liczb jest, chyba, że się mylę? Bo przecież w najgorszym przypadku sortowania przed przebiegiem n-tego sortowania, gdzie mamy n liczb w tabeli już wszystkie pary liczb muszą być posortowane, więc ten przebieg nie ma sensu.

Dodatkowo nie wiem dlaczego nie zostało wspomniane o optymalizacji sortowania bąbelkowego poprzez nie wykonywanie dalszego sortowania jeśli dana iteracja nie zawierała sortowań, co oznacza, że np. dla n-4 przebiegu jeśli okazuje się, że nie było już zamian to za pomocą np. zmiennej boolean ustawionej na false (w wyniku braku zamiany) nie uruchamiamy kolejnej iteracji sortowania. Kolejną prostą opcją optymalizacji byłoby nieporównywanie liczby z inną liczbą która już została posortowana (kolejnym minimum każdej iteracji).

Podobne pytania

0 głosów
1 odpowiedź 817 wizyt
+4 głosów
1 odpowiedź 2,242 wizyt
+3 głosów
0 odpowiedzi 1,657 wizyt

92,452 zapytań

141,262 odpowiedzi

319,078 komentarzy

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

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 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!

...