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)...

Answer / alexht

Counting sort is a solution. Kormen 's book will help you.

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();
}

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;
}
.
.
.
.
}

Answer / abc

singly linked lists can be sorted in minimum of O(n2) [n
square] time.

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;
}
}

How will you print % character? a. printf(“\%”) b. printf(“\\%”) c. printf(“%%”) d. printf(“\%%”)

4 Answers   HCL,

# include<stdio.h> aaa() { printf("hi"); } bbb(){ printf("hello"); } ccc(){ printf("bye"); } main() { int (*ptr[3])(); ptr[0]=aaa; ptr[1]=bbb; ptr[2]=ccc; ptr[2](); }

1 Answers  

how to check whether a linked list is circular.

11 Answers   Microsoft,

program to find the roots of a quadratic equation

14 Answers   College School Exams Tests, Engineering, HP, IIIT, Infosys, Rajiv Gandhi University of Knowledge Technologies RGUKT, SSC,

Given n nodes. Find the number of different structural binary trees that can be formed using the nodes.

16 Answers   Aricent, Cisco, Directi, Qualcomm,

how to concatenate the two strings

1 Answers  

Write a procedure to implement highlight as a blinking operation

2 Answers  

main() { char string[]="Hello World"; display(string); } void display(char *string) { printf("%s",string); }

2 Answers   Wipro,

write a program to count the number the same (letter/character foreg: 's') in a given sentence.

2 Answers  

int a = 10 + 10 .... ,... A = A * A What would be the value of A? The answer is 120!! Could anyone explain this to me.

2 Answers   Bosch, eInfochips, HCL, IHCL,

how can i search an element in an array

2 Answers   CTS, Microsoft, ViPrak,

Write a program to print a square of size 5 by using the character S.

6 Answers   Microsoft,