Detyre ne Java

[interX]

Pershendetje!
Kam nje detyre ne Java per te realizuar algoritmet e renditjes
- inesrtion sort
- bubble sort
- marge sort
dhe me pas te shikoj se kush ben renditjen me shpejt prej ketyre tre algoritmave, duke vendosur per te renditur nje numer te madh numrash. Pasi per nje numer te vogel nuk vihet re diferenca ne kohe.
Dy te parat i kam realizuar, por nuk po arrij te realizoj "marge sort" dhe kjo e treta me intereson me shume pasi teorikisht kam mesuar se "marge sort" eshte me efektive kur behet fjale per nje numer shume te madh numrash.
A me jepni ndonje mendim ose ndonje adres webi ku mund te kerkoj ndonje ndihme?
Ju faleminderit.

[interX]

asnje pergjigje ne gjith keto dite?
S'ka problem... do ja gjej anen vet deri ne daten 5 qe me duhet.
Gjithsesi Faleminderit qe e keni lexuar problemin

[gimi_sky]

Ti me siguri mendon MergeSort:

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

per vizualizim mund te provosh kete java applet:

http://coderaptors.com/?MergeSort

[josif]

Ne fakt keto jane algoritma shume te thjeshta dhe ke me qindra burime ne rrjet se si mund ti realizosh.

Une po mundohem te te ndihmoj me idene se si funksionon "Merge Sort"

- Ta zeme se kemi nje liste fillestare me elemente per tu renditur.
- Zgjidh nje element cfaredo nga kjo liste. Le ta quajme elementi E. (Ne terminologjine e algoritmes ky element quhet pivot)
- Krijo dy nenlista ku tek njera vendos te gjithe elementet me te vegjel se E dhe tek tjetra te gjithe elementet me te medhenj se E.
- Thirr ne menyre rekursive algoritmen per dy nenlistat duke perftuar versionet e renditura te nenlistave.
- Bashko ne fund versionin e renditur te nenlistes me elemente me te vogel se E, ne mes elementin E, dhe me pas versionin e renditur te nenlistes me elemente me te medhenj se E.

Pra pseudokodi eshte:

mergesort(L)
{
nese L ka me pak se dy elemente kthe L

E = nje element i L, (p.sh E = L[0] )
L1 = { X nga L | ku X < E }, (L1 perfshin te gjithe elementet X te L me te vegjel se E )
L2 = { X nga L | ku X > E }, (L2 perfshin te gjithe elementet X te L me te medhenj se E )

L1_Renditur = mergesort(L1)
L2_Renditur = mergesort(L2)

L_Reditur = L1Renditur U {E} U L2_Renditur, (pra bashkimi i nenlistave dhe elementit pivot)

kthe L_Renditur
}


Meqe permende efikasitetin e algoritmes po permend se performanca e kesaj algoritme eshte si me poshte:

- Ne cdo hap lista ndahet ne dysh dhe me pas thirret algoritma ne nenlistat
- Ne rastin e pergjithshem mund te supozojme se elementi pivot e ndan listen ne nenlista me numer te barabarte
- Pra koha qe kjo algoritem kerkon per tu gjetur nje rezultat, nese lista ka n elemente eshte, (ne rastin e pergjithshem):

mergesort(n) = 2*mergesort(n/2) + c

- c eshte nje kohe konstante e bashkimit te nenlistave te renditura

Pra krijohet ekuacioni i diferences: f(n) - 2*f(n/2) = c

Nga ekuacioni i mesiperm e diferences ti mund te nxjerresh se mergesort(n) = O(nlgn)

[justdoit1980]

Ka shum info per keto algoritme, po te besh pak google.
Une po te jap nje link qe gjeta ne google dhe ka dhe source code:
http://www.cs.oswego.edu/~mohammad/c...t/Sort2-E.html
Pershedetje!!!

[josif]

Te kam thene gabimisht QuickSort me siper:

MergeSort eshte si me poshte:

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

[interX]

Ju falenderoj shume te gjithve.
Shume faleminderit!