Optimalni algoritam?

[Todors]

Lol, pa ne baš previše, jer svaki niz već ima svoj index od 0 do n, samo to treba iskorisiš.

Kolko sam shvatio njemu treba najmanji broj koraka, a ne implementacija algoritma.

[Belphegor]

Netreba mu, ima bolje resenje:
@Geomaster citat

Hmm, ovo je rađeno u OGL-u, ali dao si mi ideju, skroz sam zaboravio da mogu da hookujem...

[Sun Tzu]

pivonroll kaže:

knjigu "Algoritmi" od Zivkovica.

Geomaster kaže:

Eh, kad bih mogao da tako 'skoknem' do MATF-a, gde bi mi kraj bio

http://poincare.matf.bg.ac.rs/~ezivkovm/nastava/algoritmi.pdf
Uživaj.

[Geomaster]

Todors kaže:

Ajde i ja malo da se umešam, mada nisam želeo . Kolko sam shvatio imaš dva niza i oćeš jedan da sortiraš prema drugom i da znaš koliko je najmanje koraka potrebno za tako nešto. Zar u tvom slučaju nije najoptimalnije da koristiš qucksort. Zna se da taj algoritam upravo u najmanje koraka sortira dati niz. Ako budeš budžio nešto ne verujem da ćes uspeti da ga sortiraš u manje koraka od qucksorta.

E hvala ti puno, skroz sam zaboravio na to
I hvala svima koji su pomogli
Mada hookovanje bi trebalo da pomogne.

[pyost]

Quicksort ne sortira niz u najmanjem broju koraka, daleko od toga, već ima najbolju vremensku složenost, nlogn.

[Todors]

Pa dobro, verovatno da nije, jer postoje i hibridni algoritmi. Ovo je najbrži za koji ja znam i koji se najviše koristi u te svrhe. Koji mu ti preporučuješ?

[Geomaster]

pyost kaže:

Quicksort ne sortira niz u najmanjem broju koraka, daleko od toga, već ima najbolju vremensku složenost, nlogn.

Ali koji onda algoritam može da nađe najmanji broj swapova?

[Belphegor]

Ali koji onda algoritam može da nađe najmanji broj swapova?

kako mslis da nadjes? Kao sto rece pyost, vremeska kompleksnost qsort-a je O(n log n).
http://en.wikipedia.org/wiki/Time_complexity

Msilim da je std::sort brzi od qsort.

[Geomaster]

Belphegor kaže:

kako mslis da nadjes? Kao sto rece pyost, vremeska kompleksnost qsort-a je O(n log n).
http://en.wikipedia.org/wiki/Time_complexity

Msilim da je std::sort brzi od qsort.

Pa da nađe, odnosno da sortira u najmanjem broju swapova (podrazumeva se da ja onda brojim koliko swapova sam iskoristio )
Vremenska kompleksnost ovde je broj upoređivanja, ne broj swapova (jedan element može da se swapuje više puta pre nego što zauzme svoju konačnu poziciju).
std::sort zavisi mnogo od implementacije, u standardu nije naveden koji tačno algoritam treba da se koristi, neke implementacije koriste quicksort, a neke introsort.

Btw, ne uspevam da hookujem OGL-ove funkcije, ili ne radi ili se program sruši

[Sass Drake]

http://en.wikipedia.org/wiki/Sorting_algorithm

Najbrži ili najbolji algoritam nepostoji. Svaki od njih ima svoje prednosti i mane u odnosu na druge u datim situacijama. Osim, vremesnke kompleksnoti bitna je i stabilnost algoritma i worst time.
Potražite ovu knjigu:
http://www.sk.rs/forum/showthread.php?t=33731

[Geomaster]

Sass Drake kaže:

http://en.wikipedia.org/wiki/Sorting_algorithm

Najbrži ili najbolji algoritam nepostoji. Svaki od njih ima svoje prednosti i mane u odnosu na druge u datim situacijama. Osim, vremesnke kompleksnoti bitna je i stabilnost algoritma i worst time.
Potražite ovu knjigu:
http://www.sk.rs/forum/showthread.php?t=33731

Ja ne tražim "najbrži" ili "najbolji" algoritam, ja tražim algoritam koji će da mi da koliko najmanje swapova trebam da napravim da bi od jednog niza dobio drugi. Uopšte nisam tražio sorting algoritam, ali Todors je predložio da se algoritam za sortiranje može iskoristiti uvođenjem smene.

[Todors]

Koristi ti qsort i uživaj, ne verujem da ćeš sam napraviti bolji algoritam. Pokušao sam da nađem na googlu algoritam koji najmanje swopuje ali izgleda da se ljudi nisu time mnogo bavili, već su to samo poređenja kompleksnoti.

[Ivan-94]

Pogledaj ovde, mada mislim da si vec gledao to.
Post 4 pa nadalje, i oni koriste optimizovan qsort.

[pyost]

Mislim da ljudi ovde pričaju o dve različite stvari. Jedno je brzina algoritma (odnosno vremenska složenost), a drugo minimalan broj zamena. Ako pričamo o prvom, Quicksort jeste među bržima. Međutim, ako modifikujemo algoritam tako da pamti broj zamena, videćemo na kraju da je taj broj veći od N, za određene test primere.

Sa druge strane, očigledno je da je u najgorem slučaju potrebno najviše N-1 zamena: prva zamena postavi prvi element na svoje mesto, druga drugi element itd. Kada postavimo pretposlednji element, automatski će nam biti postavljen i poslednji. U praksi, ovaj broj zamena je i manji.

Pritom, da bismo odredili broj zamena, uopšte nema potrebe da zapravo sortiramo taj niz, pre će biti da je tu u pitanju posmatranje niza kao graf.

Tačnije... http://online-judge.uva.es/board/vie...ba2ba4#p101543

[Geomaster]

pyost kaže:

Mislim da ljudi ovde pričaju o dve različite stvari. Jedno je brzina algoritma (odnosno vremenska složenost), a drugo minimalan broj zamena. Ako pričamo o prvom, Quicksort jeste među bržima. Međutim, ako modifikujemo algoritam tako da pamti broj zamena, videćemo na kraju da je taj broj veći od N, za određene test primere.

Sa druge strane, očigledno je da je u najgorem slučaju potrebno najviše N-1 zamena: prva zamena postavi prvi element na svoje mesto, druga drugi element itd. Kada postavimo pretposlednji element, automatski će nam biti postavljen i poslednji. U praksi, ovaj broj zamena je i manji.

Pritom, da bismo odredili broj zamena, uopšte nema potrebe da zapravo sortiramo taj niz, pre će biti da je tu u pitanju posmatranje niza kao graf.

Tačnije... http://online-judge.uva.es/board/vie...ba2ba4#p101543

Ovako nešto sam tražio
Iskopao sam ovo, a na linku piše da je ovo NP-hard problem.
Tačno kao što su na linku spomenuli, rešenje je očigledno kada su elementi jedinstveni, ali ja imam slučaj sa dosta ponavljanja.

[EclipsE]

Najmanji broj swapova je broj elemenata koji nisu na svom mestu - 1.

Primer:

1 3 2
2 i 3 nisu na svom mestu = 2 elementa = 2 - 1 = 1

1 4 2 3 5
4, 2 i 3 nisu na svom mestu = 3 elementa = 3 - 1 = 2 (recimo, zamenimo 4 i 2, pa 3 i 4 i imamo 1 2 3 4 5)

Valjda bi trebalo da radi za sve nizove

[chaami]

EclipsE kaže:

Najmanji broj swapova je broj elemenata koji nisu na svom mestu - 1.

Primer:

1 3 2
2 i 3 nisu na svom mestu = 2 elementa = 2 - 1 = 1

1 4 2 3 5
4, 2 i 3 nisu na svom mestu = 3 elementa = 3 - 1 = 2 (recimo, zamenimo 4 i 2, pa 3 i 4 i imamo 1 2 3 4 5)

Valjda bi trebalo da radi za sve nizove

Kako to sad.... ????????
Maksimalni broj swapova koji nam daje rešenje je broj elemenata koji nisu na svom mestu -1, ali ne i najmanji.
Uzmi na primer niz 1,3,4,2,6,7,5. Šest elemenata nije na svom mestu a treba nam samo četiri swapa (2,3)(3,4)(5,6)(6,7).