Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

QuckSort ali ne pomoću polja nego pomoću vezane liste.

[es] :: Art of Programming :: QuckSort ali ne pomoću polja nego pomoću vezane liste.

[ Pregleda: 4823 | Odgovora: 15 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

maximus_1
Max Maximus

Član broj: 46848
Poruke: 277
193.198.27.*



Profil

icon QuckSort ali ne pomoću polja nego pomoću vezane liste.08.11.2006. u 18:51 - pre 189 meseci
Ovako, trebao bi mi algoritam za QuickSort ali ne onaj koji je realiziran pomoću polja nego pomoću vezane liste. Dakle, ja mu uputim glavu vezane liste i on sortira sve elemente liste.
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.0.*



+1 Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.08.11.2006. u 22:19 - pre 189 meseci
Nikad to nisam kucao (ne znam ni sta ce ti), ali moglo bi ovako. Prvo, lista mora da bude dvostruko povezana. Proceduru ces pozivati sa dva parametra, adresom prvog (F) i adresom zadnjeg (L) elementa u listi. Zatim da bi odredio pivot (onaj element na osnovu koga ces da ih delis) moras da odes do srednjeg elementa u listi. Zatim redom (kao i kod nizova) trazis prvi koji je manji, tj. zadnji koji je veci. Zamenis ih, a potom pozoves proceduru kao i kod nizova, s stim sto kad zavrsis ono rekuzivno pozivanje, moras da prespojis te liste...
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

maximus_1
Max Maximus

Član broj: 46848
Poruke: 277
193.198.27.*



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.09.11.2006. u 00:06 - pre 189 meseci
Ok, mislim da ipak ne treba dvostruko vezana lista, jer uvijek do prethodnog mogu doc tako da krenem od pocetka, tj. od glave. Pronasao sam neki kod i cini se da radi. Inace, moram napraviti quicksort preko polja i preko vezanih listi. Polje je ok, ali liste je malo teže pronaći. Ipak, uspio sam. Trebam samo jos pronaci nekakv "efikasniji quck sort" koji radi sa vezanim listama...
 
Odgovor na temu

qdot
Mladen Srdic
Nova Pazova

Član broj: 51019
Poruke: 25
217.24.20.*



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.09.11.2006. u 10:53 - pre 189 meseci
Efikasniji algoritam necesh pronaci,jer quicksort nema garantovano vreme od n log n,ali u 95% sluchajeva ima.Shto se tiche sortiranja lista(i kolekcija uopshte),vreme koje je potrebno za sortiranje nad njom samom je n2log n(zbog sekvencijalnog pristupa elementu u listi),tako da ti je efikasnije da kreirash jedan niz od kljuchnih poja i da sortirash niz,a zatim i preuredish listu na osnovu toga.Pogledaj ovde kako bi to trebalo da uradish.

http://java.sun.com/j2se/1.4.2...tions.html#sort(java.util.List)

Ako ti nije potrebna brzina izvrshavanja,onda imash svu slobodu da projektujesh algoritam kako god hocesh.

Mladen.
 
Odgovor na temu

FuzzyCreation

Član broj: 112586
Poruke: 33
*.eunet.yu.



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.09.11.2006. u 13:59 - pre 189 meseci

Ne treba ti quick sort, nego merge sort, on je nlogn algoritam za SORTIRANJE LISTA (kako god povezanih)...
 
Odgovor na temu

qdot
Mladen Srdic
Nova Pazova

Član broj: 51019
Poruke: 25
217.24.20.*



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.09.11.2006. u 15:40 - pre 189 meseci
Citat:
FuzzyCreation: Ne treba ti quick sort, nego merge sort, on je nlogn algoritam za SORTIRANJE LISTA (kako god povezanih)...


Citat:
maximus_1: Ovako, trebao bi mi algoritam za QuickSort ali ne onaj koji je realiziran pomoću polja nego pomoću vezane liste. Dakle, ja mu uputim glavu vezane liste i on sortira sve elemente liste.


Mislim da mu ipak treba quicksort :)
 
Odgovor na temu

maximus_1
Max Maximus

Član broj: 46848
Poruke: 277
193.198.27.*



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.09.11.2006. u 18:34 - pre 189 meseci
Da, treba mi bas QuickSort. Koliko sam skužio postoji više načina rada quick sorta. E sad bi meni trebala dva od kojih je jedan efikasniji, moguće je da jedan realiziram tako da prilikom mijenjanja mjesta prilikom sortiranja preusmjerim pokazivače a drugi način da ime samo zamijenim vrijednosti a to i dalje ostanu isti elemeni. Samo, nisam siguran koliko je to efikasnije (brže recimo kad bih sortirao 10000+ elemenata i mjerio sistemsko vrijeme)?!
 
Odgovor na temu

FuzzyCreation

Član broj: 112586
Poruke: 33
*.eunet.yu.



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.10.11.2006. u 12:33 - pre 189 meseci

Merge sort ima istu filozofiju kao quick sort, deljenje onoga sto treba da se sortira na dva, potom rekurzivan poziv za delove, te pri povratku rekurzije spajanje sortiranih podlista, pri cemu se rekurzija zavrsava na jedno elementnim listama koje su po defaultu vec sortirane. Merge sort je moguce realizovati in-place bez raznih kopiranja sadrzaja koji je bitan za uredjenje (a i onog ostalog) samo se treba malo poigrati sa pointerskom aritmetikom...
 
Odgovor na temu

emiraga

Član broj: 54285
Poruke: 32
60.51.180.*



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.11.11.2006. u 09:54 - pre 189 meseci
evo mog rjesenja sto sam ga nekada davno napisao,
ima manu sto za pivota bira samo prvog :)
jednostruko vezana lista, i generalno je sporiji,
ali je brz onoliko koliko mi to algoritam qsort i
struktura podataka linked list dozvoljava.
I jos nesto, funkcije za init i input su malo ruzne,
ali ih mozes zamjeniti sa svojima :)

Code:
#include <stdio.h>
#include <stdlib.h>

struct llist {
    int broj;
    struct llist *next;
};

struct llist *l_init(void) {
    struct llist *tmp;
    tmp = malloc(  sizeof(struct llist)   );
    tmp->next = (struct llist*)NULL;
    return tmp;
}

struct llist * l_input(void) {
    struct llist *s=NULL, *p;
    int tmp;
    while(1) {
        scanf("%d",&tmp);
        if(feof(stdin))
            break;
        if(s==NULL) {
            s = p = l_init();
        } else {
            p->next = l_init();
            p = p->next;
        }
        p->broj = tmp;
    }
    return s;
}

void l_print(struct llist *p) {
    for(;p;p=p->next)
        printf("%d\n",p->broj);
}

struct llist *lqsort(struct llist *p,struct llist *append) {
    int pivot;

    struct llist *lcur, *lstart;
    struct llist *gcur, *gstart;
    struct llist *t;

    if(p == NULL)
        return append;

    pivot = p->broj;
    t = p->next;
    lstart = lcur = gstart = gcur = NULL;
    while(t) {
        if(t->broj < pivot) {
            // put all numbers that are less than pivot
            if(lstart == NULL) {
                lstart = t;
                lcur = t;
            } else {
                lcur->next = t;
                lcur = t;
            }
        } else {
            // put all numbers that are greater than pivot
            if(gstart == NULL) {
                gstart = t;
                gcur = t;
            } else {
                gcur->next = t;
                gcur = t;
            }
        }
        t=t->next;
    }
    if(lstart)
        lcur->next = NULL;
    if(gstart)
        gcur->next = NULL;

    lstart = lqsort(lstart,p);
    gstart = lqsort(gstart,append);

    p->next = gstart;
    return lstart;
}

struct llist *l_sort(struct llist *p) {
    return lqsort(p,NULL);
}

int main() {
    struct llist *p;
    p = l_input();
    p = l_sort(p);
    l_print(p);
    return 0;
}
/* Alternate way: 
int main2() {
    l_print(l_sort(l_input()));
    return 0;
}
*/


btw. mergesort sa linkanim listama ima nezibjezivu manu to da moras proci bez veze kroz pola liste samo da bi je prerezao, znaci (bespotrebnih) koraka.
 
Odgovor na temu

explorer-1

Član broj: 98573
Poruke: 102
*.adsl.net.t-com.hr.



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.12.11.2006. u 09:44 - pre 189 meseci
Hmmm... zanimljivo, a čemu ti služi ovo:

Code:

    if(lstart)
        lcur->next = NULL;
    if(gstart)
        gcur->next = NULL;


... ovo me podsjeća malo na merge sort
 
Odgovor na temu

emiraga

Član broj: 54285
Poruke: 32
*.cache.telstra.net.



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.12.11.2006. u 12:50 - pre 189 meseci
Citat:
explorer-1: Hmmm... zanimljivo, a čemu ti služi ovo:

Code:

    if(lstart)
        lcur->next = NULL;
    if(gstart)
        gcur->next = NULL;
ja pravim dvije liste, jedna lista (lstart) pokazuje na pocetak liste u kojoj se nalaze elementi sa brojem manjim od PIVOT-a, a u drugoj (gstart) pokazuje na listu u kojoj se nalaze elementi sa brojem veci od PIVOT-a. Ako neka lista nije prazna lcur i gcur u tom trenutku pokazuju na kraj te dvije liste respektivno.

(Odgovor na pitanje.) Sada u slucaju da bilo koja od njih nije prazna treba ih terminirati NULL pokazivacem koji znaci da je to kraj te liste.
Code:
#define NULL (void *)0

Citat:
explorer-1:
... ovo me podsjeća malo na merge sort

Ja ne vidim razloga da bi se to desavalo.
 
Odgovor na temu

explorer-1

Član broj: 98573
Poruke: 102
*.adsl.net.t-com.hr.



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.12.11.2006. u 14:19 - pre 189 meseci
Ok, super, skužil sam sad, raspisal sam si listu i mogu ti priznati da je ovo genijalno, ali sporo. Kak bi se to malo ubrzalo ? Problem nastaje ako imam 10ak k elemenata.
Ideja da se prepiše u polje pa natrag u listu.
 
Odgovor na temu

explorer-1

Član broj: 98573
Poruke: 102
*.adsl.net.t-com.hr.



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.12.11.2006. u 14:36 - pre 189 meseci
Pa brže je...
 
Odgovor na temu

genuine
Dragisa Jankovic
Beograd

Član broj: 101510
Poruke: 33
*.dial.b92.net.



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.12.11.2006. u 15:50 - pre 189 meseci
Sta god da radite pazite... nije toliko bitno za sam algoritam ali je bitno za nacin implementiranja istog.... svaka povezana lista pati od sledece boljke

node = new Node(root,value2);
root = node;

pa nesto radim
pa opet

node = new Node(root,value2);
root = node;

dakle problem je sa new.. ko zna koju ce adresu da dodeli (ako ne gledamo konkretnu implementaciju malloc-a ) posto su obicno cvorovi liste reda 8 bajta (4 za pokazivac na sledeci cvor i 4 za vrednost ili pokazivac na podatak) ne bi bilo lose da tacno 8 nodova stane u jedan kes blok i tako uvek....
dakle alokacija cvorova liste ne ide preko new ili malloc nego pravite sami tabelu slobodnih cvorova tako da sto manje blokova zauzmu... posebne performanse dobijate kada pretrazujete listu jer ima manje promasaja zbog manjeg broja blokova ( radnih stranica i sl )... tako mozete da dobijete nesto po performansama brze od liste ali opet sporije od niza....

sada kada sam procitao ovo mislim da mozete kompletno da ga ignorisete.. :)
Necu vise da radim ,bre !
 
Odgovor na temu

explorer-1

Član broj: 98573
Poruke: 102
*.adsl.net.t-com.hr.



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.12.11.2006. u 16:37 - pre 189 meseci
A kako bi koristio hash tabelu o ovom slučaju ?
... hmm... svakak s složenosti nlogn, prelazim u n...
 
Odgovor na temu

emiraga

Član broj: 54285
Poruke: 32
60.51.180.*



Profil

icon Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.12.11.2006. u 19:33 - pre 189 meseci
evo sam nesto malo pokusao da sredim, moze ovo jos bolje, ali evo proba
Code:
int pivot; /*izvan funkcije*/
struct llist *t, *gstart, *gcur; 

struct llist *lqsort(struct llist *p,struct llist *append) {
    struct llist *lstart, *lcur;
    pivot = p->broj;
    t = p->next;
    lstart = gstart = NULL;
    while(t) {
        if(t->broj < pivot) {
            if(lstart) lcur->next = t; else lstart = t; 
            lcur = t;
        } else {
            if(gstart) gcur->next = t; else gstart = t; 
            gcur = t;
        }
        t=t->next;
    }
    if(gstart){
        gcur->next = NULL;
        p->next = lqsort(gstart,append);
    } else {
        p->next = append;
    }
    if(lstart){
        lcur->next = NULL;
        return lqsort(lstart,p);
    } else {
        return p;
    }
}

struct llist *l_sort(struct llist *p) {
    if(p == NULL)
        return NULL;
    else
        return lqsort(p,NULL);
}
... malo ili nimalo se dobije na performansama.

Ali mi 10K brojeva i stara verzija sortira za 0.019s.

[Ovu poruku je menjao emiraga dana 12.11.2006. u 21:21 GMT+1]
 
Odgovor na temu

[es] :: Art of Programming :: QuckSort ali ne pomoću polja nego pomoću vezane liste.

[ Pregleda: 4823 | Odgovora: 15 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.