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.
Registrovani: 1 ( vjova )
QuckSort ali ne pomoću polja nego pomoću vezane liste.
Re: QuckSort ali ne pomoću polja nego pomoću vezane liste.