na codeforces sam radio jedan zadatak koji se resava preko nekog algoritma za sortiranje.
e sad, prvo sam sklepao onaj klasicni algoritam za taj zadatak i bubblesort, Medjutim u test primerima mi je pisalo da je prekoracio vremensko ogranicenje. zatim sam uradio u quicksortu, i opet mi je prekoracio vremensko. i tu sam ja gledao da nije u drugom delu koda. Medjutim posle sat vremena sam odustao i pogledao kako su drugi uradili. Bukvalno isti kod samo umesto quicksorta je stajala sort( ); funkcija i kad sam to ubacio, kod mi je bez poteskoca prosao.
pitanje je dakle, da li je dozvoljeno na petlja takmicenju koristiti ovu funkciju i da li ima neke mane u odnosu na standardne sort algoritme. i da li ima negde materijal da se procita nesto vise o njoj posto ja nisam nasao.
Hvala unapred.
Mislim da ovde mozes da pronadjes nesto korisno
https://en.cppreference.com/w/cpp/algorithm/sort
Naravno da je dozvoljeno koristiti je na petlji, nalazi se u #include<algorithm>
I sto se tice mana, slozenost je O(nlogn) td. je brza nego bilo koji sort koji bi sam iskucao (osim counting sort-a) i mnogo je lakse. A ako ti je bas bitna brzina i imas neka odredjena ogranicenja za elemente niza onda mozes sam da iskucas counting sort u O(n), https://www.geeksforgeeks.org/counting-sort/
I sort() funkcija je hibrid quicksort-a i jos nekih algoritama koji sortiraju male podnizove pri kraju quicksort-a.
1 Like
Slažem se sa svime što je FEDIKUS rekao, još samo jedna sitna napomena koja možda objašnjava što ti je korišćenje sort() promenilo rezultat:
Složenost “ručne” implementacije quicksort-a je u proseku ista kao i sort(), tj. \mathcal{O}(N \log N), ali je sa nepažljivom ili jednostavnom implementacijom lako naći ulaz za koji će quicksort imati složenost \mathcal{O}(N^2). Na primer, ako za pivot element uvek biraš prvi član niza, a ulaz je već sortiran (ili obrnuto sortiran) niz, u svakom koraku će biti eliminisan samo jedan element, tako da će složenost biti \mathcal{O}(N + (N-1) + (N-2) + \dots) = \mathcal{O}(N^2).
2 Likes
da da. pa i sam sam se zacudio otkud je moguce da je skoro 10 puta brzi. ima smisla… ali svakako je lakse iskucati sort(); nego ceo algoritam za quicksort. Hvala jos jednom.
