Algoritmul QuickSort (nerecursiv) quick please

#1
driverx

Posted 18 July 2003 - 11:53

Senior Member

Grup: Senior Members
Posts: 3,083
Înscris: 22.07.2002

Hello everyone,

Am nevoie repede de Quciksort varianta nerecursiva. Cod Delphi, VB, VB.NET nu conteaza

10x

:cya:

Back to top

#2
bcata

Posted 18 July 2003 - 13:51

Moderator

Grup: Members
Posts: 265
Înscris: 04.06.2002

Nu poti elimina complet recursivitatea la Quicksort, va trebui sa simulezi tu stiva, ceea ce e doar un detaliu de implementare, algoritmul propriu-zis va ramane recursiv.

Poti in schimb sa elimini in general tail-recursion, adica poti elimina recursivitatea unei functii daca aceasta (apelul recursiv) se regaseste ca ultima instructiune a functiei.. Cum e de exemplu cazul factorialului, etc.

La quicksort in schimb ai doua apeluri recursive, pentru ca imparte problemain doua subprobleme mai mici), si eliminand tail-recursion nu scapi decat de un singur apel.. Pentru celalalt va trebui sa simulezi o stiva de parametri. Ceea ce nu e foarte greu.

Si, in final, daca vrei exemple de cod, cred ca sunt cu carul pe net, eu unul am gasit un exemplu in Pascal (nu stiu daca merge in Delphi or not): http://www.bsdg.org/...G/0034.PAS.html

Back to top

#3
driverx

Posted 18 July 2003 - 13:56

Senior Member

Grup: Senior Members
Posts: 3,083
Înscris: 22.07.2002

bcata,

Stiu ca tre sa imi fac o stiva, am ceva cod sursa gasit pe net dar e incomplet :) Ideea era ca imi trebuia repede fara sa gandesc eu algoritmu ca sa nu am overheat la creer :)

:cya:

Back to top

#4
bcata

Posted 18 July 2003 - 14:21

Moderator

Grup: Members
Posts: 265
Înscris: 04.06.2002

Daca tot iti trebuie atat de repede, nu inteleg de ce iti trebuie neaparat varianta nerecursiva? Teme, ceva? :)

Back to top

#5
driverx

Posted 18 July 2003 - 14:29

Senior Member

Grup: Senior Members
Posts: 3,083
Înscris: 22.07.2002

looool nu,

fac un prg in vb6 si saracu vb nu suporta recursivitate prea mare. Am mai auzit eu oameni care s-au plans ca le crapa programasele la recursivitate. Am mai patito si eu dar nu la quicksort. Risti mult la quicksort in vb daca ai liste mari

:cya:

Back to top

#6
bcata

Posted 18 July 2003 - 14:36

Moderator

Grup: Members
Posts: 265
Înscris: 04.06.2002

Alegand bine care dintre cele doua apeluri il pui pe stiva sau il executi ca "tail-recursion", poti limita dimensiunea stivei la sup(log(n)), unde n este numarul de elemente. Chestia asta se obtine daca pui intotdeauna pe stiva intervalul mai mic, si il executi direct pe cel mare. Astfel, pentru un milion de elemente, sa spunem, vei avea cel mult 20 de apeluri pe stiva, ceea ce e rezonabil...

In VB nu poti sa maresti in vreun fel stiva de apeluri? :) Vreo setare de compilare, ceva?

Back to top

Anunturi

Neurochirurgie minim invazivă

"Primum non nocere" este ideea ce a deschis drumul medicinei spre minim invaziv.

Avansul tehnologic extraordinar din ultimele decenii a permis dezvoltarea tuturor domeniilor medicinei. Microscopul operator, neuronavigația, tehnicile anestezice avansate permit intervenții chirurgicale tot mai precise, tot mai sigure. Neurochirurgia minim invazivă, sau prin "gaura cheii", oferă pacienților posibilitatea de a se opera cu riscuri minime, fie ele neurologice, infecțioase, medicale sau estetice.

www.neurohope.ro

Algoritmul QuickSort (nerecursiv) quick please

#1 driverx Posted 18 July 2003 - 11:53

#2 bcata Posted 18 July 2003 - 13:51

#3 driverx Posted 18 July 2003 - 13:56

#4 bcata Posted 18 July 2003 - 14:21

#5 driverx Posted 18 July 2003 - 14:29

#6 bcata Posted 18 July 2003 - 14:36

Anunturi

▶ 0 user(s) are reading this topic

Sign In

#1
driverx

Posted 18 July 2003 - 11:53

#2
bcata

Posted 18 July 2003 - 13:51

#3
driverx

Posted 18 July 2003 - 13:56

#4
bcata

Posted 18 July 2003 - 14:21

#5
driverx

Posted 18 July 2003 - 14:29

#6
bcata

Posted 18 July 2003 - 14:36