Ndihme per nje Algoritem

[Vito Corleone]

Pershendetje Forumi i Shkences,

Kam nevoje per pak ndihme. Me duhet te bej nje program ne C ose C++ qe te kryeje funksionin e Quicksort duke perdorur Linked Lists.

Funksioni duhet te kete domosdoshmerisht kete strukture:

struct listnode *quicksort(struct listnode *data, int length)

E cila merr si input nje linked list me integers, dhe gjatesine e listes. Pak a shume duhet te punoje si me poshte:

Quicksort merr listen dhe gjatesine si input

Zgjidhet nje numer cfaredo, rastesisht (duke perdorur funksionin int randomindex(int
k) { return (rand () % k); }

skanohet lista deri sa te shkohet tek elementi me ate numer qe u gjenerua me pare

ky element do jete "pivot", me te cilin do krahasohen te gjithe elementet e tjere te listes

Ndahet lista ne tre pjese : pjesa me elemente me te vegjel se Pivot, elementi Pivot, dhe pjesa me elemente me te medhenj se Pivot

Ndertohen dy lista te reja: ajo me elementet e vegjel dhe ajo me te medhenjte

Ne menyre rekursive, therritet funksioni quicksort per keto dy lista me te vogla

Se fundmi, behet bashkengjitja e dy listave, me pivot-in ne mes te tyre.

Si return kemi pointerin qe tregon elementin me te vogel (elementi i pare) te listes.

Ne kete menyre arrijme te renditim listen ne rendin rrites, duke perdorur linked list, quicksort, dhe rekursion (recursion).



Kjo eshte e gjitha. Faleminderit qe morret kohen ta lexonit. Kush ka ndonje ide konkrete per programin eshte i lutur te postoje dicka.

Me respekt,

Ardi

[Vito Corleone]

Ky eshte kodi me te cilin duhet te testohet programi. Kodi eshte dhene nga profesori.

#include
#include

struct listnode { struct listnode * next;
int value;
} ;

int main(void)
{ int i;
struct listnode *node, *tmpnode; node = NULL;
for( i=0; i <100000; i++)
{
tmpnode = node;
node = (struct listnode *) malloc( sizeof(struct listnode));
node->next = tmpnode; node->value = (29*i + 53124)%100000;
}
printf("\n sorting \n");
quicksort(node, 100000);
tmpnode = node; i=0;
while( tmpnode != NULL )
{ if (tmpnode->value != i )
{ printf("sorting failed at i=%d\n", i);
exit(0);
}
tmpnode = tmpnode->next; i = i+1;
}
printf("Sorting succeeded\n");
exit(0);
}