Author:
Hjįlmtżr
|
[
Next Thread |
Previous Thread |
Next Message |
Previous Message
]
Date Posted: 00:31:54 04/29/04 Thu
In reply to:
Balli
's message, "Re: Quicksort - tengdir listar" on 17:35:01 04/28/04 Wed
>OK, ég hef veriš aš spį mikiš ķ žetta. Hvaš er
>vitlaust viš žetta hér aš nešan. Eša mundi mašur
>kanski undir flestum kringumstęšum dęla öllu inn ķ
>fylki first og žašan aftur inn ķ tengda listan?
>
>kv, Balli
>
Nei ekki endilega. Ég er bśinn aš laga forritiš sem žś settir inn. Ég myndi kannski ekki skrifa žetta svona
sjįlfur frį grunni, en ég reyndi aš laga bara forritiš žitt og gera žaš lķkara upphaflega Quicksort. Helstu vandamįliš
hjį žér voru smįruglingur į bendunum (einhver stašar Tail ķ staš head, o.s.frv.).
Ég held reyndar aš žaš sé hęgt aš gera žetta įn žess aš nota nśmer į hnśtana (žaš sem žś kallar count), en žaš
gęti flękt forritiš eitthvaš.
Auk žess get ég ekki ķmyndaš mér aš žetta sé hrašvirkara en upphaflega Quicksort, en žetta hentar ķ einhverjum kringumstęšum(?).
#include
#include
#include
using namespace std;
class node {
int item;
int count;
public:
node* next;
node* prev;
node(int i, int c) {
item = i;
count = c;
next = 0;
prev = 0;
}
node(int x, int c, node* p) {
item = x;
count = c;
next = 0;
prev = p;
}
~node(){}
void setNextNode(node *n) {
next = n;
}
void setCount(int nr) {
count = nr;
}
int getCount() {
return count;
}
int getItem() {
return item;
}
void inCount() {
count++;
}
void deCount() {
count--;
}
bool operator== (node n) const
{
if (count == n.getCount())
return true;
else
return false;
}
bool operator< (node n) const
{
if (count < n.getCount())
return true;
else
return false;
}
};
template
void exch(Item &a, Item &b)
{
int t1 = a->getCount();
int t2 = b->getCount();
a->setCount(t2);
b->setCount(t1);
}
template
void quicksort(Item *first, Item *last)
{
if( first == 0 || last == 0 )
return;
if((first->getItem()) >= (last->getItem()))
return;
Item *Current = last; // Žetta er eins og r
Item *Tail = last->prev; // Žetta er eins og j
Item *head = first; // Žetta er eins og i
for (;;)
{
while (head->getCount() < Current->getCount()) {
head = head->next;
}
while ((Current->getCount()) < (Tail->getCount())) {
if (Tail == first)
break;
Tail = Tail->prev;
}
if((head->getItem()) >= (Tail->getItem()))
break;
exch(head, Tail);
}
exch(Current, head);
quicksort(first, head->prev);
quicksort(head->next, last);
}
int main()
{
int i;
node *nNode = new node(1, rand()%1000);
node *tNode;
for(i = 0;i < 19; i++) {
int iTala = rand()%1000;
tNode = nNode;
nNode = new node(i + 2, iTala, tNode);
tNode->setNextNode(nNode);
}
tNode = nNode;
for(i = 0;i < 19; i++) {
cout << nNode->getCount() << " nr. " << nNode->getItem() << endl;
nNode = nNode->prev;
}
cout << nNode->getCount() << " nr. " << nNode->getItem() << endl;
quicksort(nNode, tNode);
cout << "Eftir Quicksort" << endl;
for(i = 0;i < 20; i++) {
cout << nNode->getCount() << " nr. " << nNode->getItem() << endl;
nNode = nNode->next;
}
char stop;
cin >> stop;
return 0;
}
[
Next Thread |
Previous Thread |
Next Message |
Previous Message
]
|
Feedback: 