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 |
I need your help, i need a Turbo C code for this problem.. hope u'll help me guys.? Your program will have a 3x3 array. The user will input the sum of each row and each column. Then the user will input 3 values and store them anywhere, or any location or index, temporarily in the array. Your program will supply the remaining six (6) values and determine the exact location of each value in the array. Example: Input: Sum of row 1: 6 Sum of row 2: 15 Sum of row 3: 24 Sum of column 1: 12 Sum of column 2: 15 Sum of column 3: 18 Value 1: 3 Value 2: 5 Value 3: 6 Output: Sum of Row 1 2 3 6 4 5 6 15 7 8 9 24 Sum of Column 12 15 18 Note: Your program will not necessary sort the walues in the array Thanks..
What is the output of the program given below main() { signed char i=0; for(;i>=0;i++) ; printf("%d\n",i); }
main() { { unsigned int bit=256; printf("%d", bit); } { unsigned int bit=512; printf("%d", bit); } } a. 256, 256 b. 512, 512 c. 256, 512 d. Compile error
Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.
main(){ int a= 0;int b = 20;char x =1;char y =10; if(a,b,x,y) printf("hello"); }
main() { float f=5,g=10; enum{i=10,j=20,k=50}; printf("%d\n",++k); printf("%f\n",f<<2); printf("%lf\n",f%g); printf("%lf\n",fmod(f,g)); }
char *someFun() { char *temp = “string constant"; return temp; } int main() { puts(someFun()); }
void main() { int k=ret(sizeof(float)); printf("\n here value is %d",++k); } int ret(int ret) { ret += 2.5; return(ret); }
What is the match merge ? compare data step match merge with proc sql merge - how many types are there ? data step vs proc sql
Link list in reverse order.
Is the following code legal? typedef struct a aType; struct a { int x; aType *b; };
What is data _null_? ,Explain with code when u need to use it in data step programming ?