Interview Questions And Answers 
-
Implement an algorithm to sort a linked list.
6,037 Views |
(6 votes, avg: 3.67)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Implement an algorithm to sort a linked list.
6,037 Views | (6 votes, avg: 3.67)
Loading ...
Use Mergesort.
node * insert(node * to_insert,node * sorted) {
if (to_insert->value<sorted->value){
to_insert->next=sorted;
return to_insert;
}
node * temp = sorted;
while((temp->next!=null) && (to_insert->value>=temp->next->value)
temp=temp->next;
if (temp->next==null) {
temp->next=to_insert;
return sorted;
}
to_insert->next=temp->next;
temp->next=to_insert;
return sorted;
}
node * sort(node * list) {
node * sorted=list;
list=list->next;
sorted->next=null;
while (list!=null) {
temp=list;
list=list->next;
temp->next=null;
sorted=insert(temp,sorted);
}
return sorted;
}
sorting in descending order
struct node{
int value;
node* NEXT;
}
Assume HEAD pointer denotes the first element in the linked list
Sort()
{
node* first,second,temp;
first=HEAD;
while(first!=null)
{
second=first->NEXT;
while(second!=null)
{
if(first->value<second->value)
{
temp=new node();
temp->value=first->value;
first->value=second->value;
second->value=temp->value;
delete temp;
}
second=second->NEXT;
}
first=first->NEXT;
}
}
Simple linked list in COBOL using relative record setup.
Call me a bit ignorant of newer, memory saving logics, but here we go.
With a one dimensional, multiple field table (rel #, link, data) i would read the used pointer which points to the first record.
Do this in a PERFORM VARYING Table-Sub Rel-Key FROM
1 BY 1 UNTIL Finished-Flag. And increment Link from 2 by 1 within PERFORM.
Insert the first record into the table, follow the link so on…
When done PERFORM, Re-Write records back into Link-List-File.
This is assuming that you want the record based on primary acsending key and links going from:
Rel - 1, Link - 2
Rel - 2, Link - 3
…
No matter how I look at it, it will take a big chunk of memory to acomplish this on a huge database.
void sort_list(NODEPTR *q)
{
NODEPTR r, s, t, u;
s = NULL;
while (s != (*q)->next)
{
r = t = *q;
r = t->next;
while (t != s)
{
if (t->info > r->info)
{
if (t == *q)
{
t->next = r->next;
r->next = t;
*q = r;
u = r;
}
else
{
t->next = r->next;
r->next = t;
u->next = r;
u = r;
}
}
else
{
u = t;
t = t->next;
}
r = t->next;
if (r == s)
s = t;
}
}
}
One of the easy was to sort is:
sort_list(NODE **nPtr)
{
NODE *x,*y,*z;
if ( *nPtr == NULL ) return;
x = *nPtr;
y = NULL;
while( temp != NULL )
{
z = y;
y = x;
x = x->link;
y = z->link;
}
*nPtr = y;
}
The merge sort algorithm
merge(node *p,node *q)
{
The merge sort algorithm
typedef struct node
{
int key;
struct node *next;
}node;
node *head;
node * merge(node *p,node *q)
{
node *temp;
node *r;
if(p->key < q->key)
{
temp=p;
p=p->next;
}
else
{
temp=q;
q=q->next;
}
r=temp;
while(p&&q)
{
if(p->key<q->key)
{
r->next=p;
r=r->next;
p=p->next;
}
else
{
r->next=q;
r=r->next;
q=q->next;
}
if(p)
r->next=p;
if(q)
r->next=q;
}
node * find(node *a)
{
node *p;
node *r;
p=a;
r=a->next->next;
while(r)
{
p=p->next;
int merge_sort(node *a)
{
node *p;
if(a && a->next)
{
p = find(a);
merge_sort(a);
merge_sort(p);
merge(a,p);
}
return a;
}
The merge sort algorithm
typedef struct node
{
int key;
struct node *next;
}node;
node *head;
node * merge(node *p,node *q)
{
node *temp;
node *r;
if(p->key < q->key)
{
temp=p;
p=p->next;
}
else
{
temp=q;
q=q->next;
}
r=temp;
while(p&&q)
{
if(p->key<q->key)
{
r->next=p;
r=r->next;
p=p->next;
}
else
{
r->next=q;
r=r->next;
q=q->next;
}
if(p)
r->next=p;
if(q)
r->next=q;
}
node * find(node *a)
{
node *p;
node *r;
p=a;
r=a->next->next;
while(r)
{
r=r->next;
p=p->next;
if(r)
r=r->next;
}
r=p->next;
p->next=null;
return r;
}
int merge_sort(node *a)
{
node *p;
if(a && a->next)
{
p = find(a);
merge_sort(a);
merge_sort(p);
merge(a,p);
}
return a;
}
void LBucketSort(PNODE phead)
{
PNODE pstep, pnode;
int t;
pnode = phead;
while (pnode)
{
pstep = pnode->next;
while (pstep)
{
if (pnode->d > pstep->d)
{
t = pnode->d;
pnode->d = pstep->d;
pstep->d = t;
}
pstep = pstep->next;
}
pnode = pnode->next;
}
}
@Sharath
That algorithm is for REVERSING a linked list-not for sorting it.
Leave an Answer/Comment