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

[ maximus_1 @ 08.11.2006. 18:51 ] @

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.

[ cassey @ 08.11.2006. 22:19 ] @

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...

[ maximus_1 @ 09.11.2006. 00:06 ] @

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...

[ qdot @ 09.11.2006. 10:53 ] @

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 n²log 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.

[ FuzzyCreation @ 09.11.2006. 13:59 ] @

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

[ qdot @ 09.11.2006. 15:40 ] @

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 :)

[ maximus_1 @ 09.11.2006. 18:34 ] @

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)?!

[ FuzzyCreation @ 10.11.2006. 12:33 ] @

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...

[ emiraga @ 11.11.2006. 09:54 ] @

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.

[ explorer-1 @ 12.11.2006. 09:44 ] @

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

[ emiraga @ 12.11.2006. 12:50 ] @

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.

[ explorer-1 @ 12.11.2006. 14:19 ] @

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.

[ explorer-1 @ 12.11.2006. 14:36 ] @

Pa brže je...

[ genuine @ 12.11.2006. 15:50 ] @

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.. :)

[ explorer-1 @ 12.11.2006. 16:37 ] @

A kako bi koristio hash tabelu o ovom slučaju ?
... hmm... svakak s složenosti nlogn, prelazim u n...

[ emiraga @ 12.11.2006. 19:33 ] @

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]}