How do you sort a Linked List (singly connected) in O(n)
please mail to pawan.10k@gmail.com if u can find an
anser...i m desperate to knw...
Answers were Sorted based on User's Feedback
Answer / rashid akhtar
We cant sort a singly list list in O(n) that is sure.
We can sort an array in O(k+n) if k is order of n,otherwise
counting sort is also not of O(n).
So moral of story,nobody can sort a singly list in O(n)...
Is This Answer Correct ? | 4 Yes | 3 No |
Answer / alexht
Counting sort is a solution. Kormen 's book will help you.
Is This Answer Correct ? | 2 Yes | 4 No |
Answer / sunil gupta
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
typedef struct node
{
int info;
struct node *next;
}node;
node *temp,*ptr,*t=NULL,*end=NULL;
node *start=NULL;
void main()
{
int n,i,item;
clrscr();
i=0;
printf("enter num of node");
scanf("%d",&n);
while(n>0)
{
temp=(node*)malloc(sizeof(node));
temp->next=NULL;
printf("enter info");
scanf("%d",&item);
temp->info=item;
if(start==NULL)
{
start=temp;
}
else
{
ptr=start;
while(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->next=temp;
} //else
n--;
}
ptr=start;
while(ptr!=NULL)
{
printf("%d",ptr->info);
ptr=ptr->next;
}
t=start;
while(t!=NULL)
{
ptr=t->next;
while(ptr!=NULL)
{
if(t->info>ptr->info)
{
temp->info=t->info;
t->info=ptr->info;
ptr->info=temp->info;
}
ptr=ptr->next;
}
t=t->next;
}
ptr=start;
while(ptr!=NULL)
{
printf("\n%d",ptr->info);
ptr=ptr->next;
}
getch();
}
Is This Answer Correct ? | 1 Yes | 3 No |
Answer / hakr
Using Radix sort its the best solution it takes O(n).
typedef struct node *ptr;
struct node{
int element;
ptr next;
};
typedef ptr LIST;
typedef ptr POSITION;
int main()
{
.
.
.
.
for(i=0;i<10;i++)
{
p=A[i]->next;
while(A[i]->next!=NULL)
{
A[i]->next=p->next;
p->next=NULL;
digit=(p->element/pow(10,j))%10;
InsertLast(B[digit],p);//InsertLast is a function that
takes an int and position and then does as the name tells//
p=A[i]->next;
}
.
.
.
.
}
Is This Answer Correct ? | 0 Yes | 3 No |
Answer / abc
singly linked lists can be sorted in minimum of O(n2) [n
square] time.
Is This Answer Correct ? | 2 Yes | 10 No |
Answer / ajaay
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *uslist, *slist;
struct NODE *cur_us, *cur_s; /*pointers to surf the lists*/
main()
{
..
/*uslist and slist have been initialised here*/
/*uslist holds the list to be sorted*/
/*slist is initially empty as nothing is sorted*/
..
..
LLsort();
}
LLsort ( )
{
int delval;
struct NODE *temp;
slist->nodevalue = 0; /*sorted list will have 0 as its first
element initially*/
slist->next = NULL;
cur_us = uslist;
while( cur_us != NULL)
{
cur_s = slist;
while(cur_s != NULL)
{
if(cur_us->nodevalue < cur_s->nodevalue) /*step-1 of
the algo.*/
{
target = cur_s; /*step-2: make cur_s as your TARGET*/
delval = delnode(cur_us); /*deletion has to be done to
the UNSORTED list*/
addnode(delval, target); /*remember addition has to be
done to the SORTED list*/
}
else
if(cur_s->next == NULL) /*step-3:if cur_s is the last
element in the sorted list*/
{
delval = delnode(cur_us);
temp_us = (struct NODE *)malloc(sizeof(NODE));
temp_us ->nodevalue = delval;
cur_s->next = temp_us; /*step-3:append the
unsorted element to the sorted list*/
temp_us->next = NULL;
}
cur_s = cur_s->next;
}
cur_us = cur_us->next;
}
}
Is This Answer Correct ? | 3 Yes | 11 No |
write a program in c language to get the value of arroy keys pressed and display the message which arrow key is pressed?
why nlogn is the lower limit of any sort algorithm?
main() { int i=10,j=20; j = i, j?(i,j)?i:j:j; printf("%d %d",i,j); }
How we print the table of 3 using for loop in c programing?
#include <stdio.h> int main(void) { int a=4, b=2; a=b<<a+b>>2 ; printf("%d",a); return 0; }
how to return a multiple value from a function?
void main() { while(1){ if(printf("%d",printf("%d"))) break; else continue; } }
why do you use macros? Explain a situation where you had to incorporate macros in your proc report? use a simple instream data example with code ?
String copy logic in one line.
print a semicolon using Cprogram without using a semicolon any where in the C code in ur program!!
35 Answers Tata Elxsi, TCS, VI eTrans,
What is "far" and "near" pointers in "c"...?
main(){ char a[100]; a[0]='a';a[1]]='b';a[2]='c';a[4]='d'; abc(a); } abc(char a[]){ a++; printf("%c",*a); a++; printf("%c",*a); }