• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Studiu asupra QuickSort-ului, folosind diferiti pivoti

2
  • Publicat de Andrei Avădănei
  • în C/C++
  • — 11 iul., 2009 at 1:35 pm

M-am gandit sa ofer o mica idee pentru cei care folosesc tehnica standard de sortare pentru vectori de lungime medie spre ridicat : QuickSort.

Voi aborda 3 situatii,toate 3 bazandu-se doar pe o modalitate diferita de obtinere a pivotului. Mentionez ca in acest articol nu voi sta sa explic implementarea QuickSortului, acest lucru il voi considera ca este stiut de dumneavoastra.Toate cele 3 situatii vor fi exemplificate corect prin ajutorul unei probleme de pe infoarena ce mi-a oferit posibilitatea sa studiez toate cele 3 implementari pentru a vedea care este cea mai eficienta din punct de vedere al vitezei.

Cele 3 situatii sunt urmatoarele :
1. Pivotul reprezinta valoarea medie din intervalul [st,dr] 2. Pivotul reprezinta valoarea din mijlocul intervalului [st,dr] 3. Pivotul reprezinta valoarea aleasa random din intervalul [st,dr]

1. Pivotul reprezinta valoarea medie din intervalul [st,dr]

Pentru a calcula valoarea medie din intervalul [st,dr] evident trebuie calculata suma valorilor din acest interval dupa care sa se faca o normalizare in functie de numarul de valori din vectorul citit.

     mijl = 0;
      for(int i = st; i < = dr; i++)
      mijl+=tablou[i];
      mijl = mijl/(dr-st+1);

Rezultatul acestei "optimizari" este un nefavorabil si incetineste radical rezultatele asupra testului :
Rezultatul optimizarii 1

2. Pivotul reprezinta valoarea din mijlocul intervalului [st,dr]

mijl = tablou[(st+dr)/2];

Aceasta rezolvare ne ofera rezultate imbucuratoare si se observa ca solutia clasica este una din cele mai bune,pana in acest moment.Timpii de executie sunt vizibil imbunatatiti iar TLE`urile lipsesc !
Rezultatul optimizarii 2

3. Pivotul reprezinta valoarea aleasa random din intervalul [st,dr]

Pentru ca toate valorile cuprinse in intervalul [st,dr] sa aiba aceeasi probabilitate de a fi pivotul trebuie ca acesta sa fie ales random.Bineinteles ca in aceasta situatie la fiecare evaluare rezultatele pot fi diferite in bine sau in rau insa in majoritatea situatiilor rezultatele vor fi ceva mai bune. O analiza draguta puteti gasi in "Introducere in algoritmi", de Thomas H. Cormen 😀

mijl = tablou[(int)(st + (std::rand()%(dr-st)))];

Rezultatele sunt putin mai imbunatatatite ca cele de la pivotul la mijloc.Observam o imbunatatire de cateva zecimi pe testele mai mari.
Insa ma repet ca aceste rezultate evaluate de cateva ori pot oferi rezultate mai bune sau mai proaste,datorita faptului ca pivotul nu este tot timpul acelasi.

Rezultatul

Ca o concluzie putem spune ca ultimile doua solutii sunt cele mai bune,ultima dintre acestea oferind rezultatele cele mai bune.Personal folosesc varianta cu pivotul la mijloc prin simplu fapt ca nu exista riscul de a avea o situatie "random" mai nefavorabila.

Cele 3 surse :
Pivot ales folosind media numerelor
Pivot ales la mijlocul intervalului
Pivot ales random

Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!

Etichete: pivor randompivot normalpivot relativQuick Sort

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior De astazi ne gasiti si pe Twitter
  • Articolul următor Back home

2 Comentarii

  1. Andrei Misarca spune:
    iulie 14, 2009 la 10:31 pm

    http://www.youtube.com/watch?v=JPyuH4qXLZ0 in una dintre lectii (nu mai stiu exact care) prezinta diverse aspecte ale qsortului. Solutia cu pivotul din mijlocul intervalului poate fi destul de inceata in unele cazuri, de aceea cea mai eficienta este cea cu pivotul random(eficienta consta chiar in acest random).

  2. Avadanei Andrei spune:
    iulie 14, 2009 la 10:54 pm

    Eficienta este data de faptul ca oricare din valorile cuprinse in intervalul [st,dr] are aceeasi probabilitate de a fi un pivot si acest lucru elimina situatiile si problemele ce apar in anumite situatii : vector sortat opus fata de cum avem nevoie,respectiv situatiile cand valorile sunt practic „puse” cu mana 🙂

    Multumesc de completare 🙂


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    • imacoolat-curat.ro
      | Published: februarie 3, 2020 - 2:00 am
    • hotel-palace.ro
      | Published: februarie 2, 2020 - 2:00 am
    • www.tahometru.ro
      | Published: februarie 1, 2020 - 2:00 am
    • alexisart.ro
      | Published: ianuarie 30, 2020 - 2:00 am
    • justshop.ro
      | Published: ianuarie 29, 2020 - 2:00 am
    RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • ianuarie 2021
    L Ma Mi J V S D
    « dec.    
     123
    45678910
    11121314151617
    18192021222324
    25262728293031
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Studiu asupra QuickSort-ului, folosind diferiti pivoti
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons

Multumim foarte mult ca ne-ai raportat greseala! O vom remedia in cel mai scurt timp posibil.