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

main ( ) { static char *s[ ] = {“black”, “white”, “yellow”, “violet”}; char **ptr[ ] = {s+3, s+2, s+1, s}, ***p; p = ptr; **++p; printf(“%s”,*--*++p + 3); }

1 Answers  

why is printf("%d %d %d",i++,--i,i--);

4 Answers   Apple, Cynity, TCS,

main() { unsigned int i=65000; while(i++!=0); printf("%d",i); }

1 Answers  

How to access command-line arguments?

4 Answers  

#if something == 0 int some=0; #endif main() { int thing = 0; printf("%d %d\n", some ,thing); }

1 Answers  

main() { int x=5; for(;x!=0;x--) { printf("x=%d\n", x--); } } a. 5, 4, 3, 2,1 b. 4, 3, 2, 1, 0 c. 5, 3, 1 d. none of the above

2 Answers   HCL,

int i; main(){ int t; for ( t=4;scanf("%d",&i)-t;printf("%d\n",i)) printf("%d--",t--); } // If the inputs are 0,1,2,3 find the o/p

2 Answers  

A program that will create a movie seat reservation. The program will display the summary seats and its status. The user will be ask what seat no. to be reserved, then it will go back again to the summary to display the updated seat status. If the seat no. is already reserved then it will prompt an error message. And also if the input seat no is out of range then it will also prompt an error message. The program is continuously running. Termination of the program will depends on how the programmer will apply. Sample output: Movie Seats Reservation Summary of Seats: Seat 1: Available Seat 2: Available Seat 3: Available Seat 4: Available Seat 5: Available Enter seat no. (Press 0 to terminate Or the assigned seat capacity) : 1 Movie Seats Reservation Summary of Seats: Seat 1: Reserve Seat 2: Available Seat 3: Available Seat 4: Available Seat 5: Available Enter seat no. (Press 0 to terminate Or the assigned seat capacity) : 6 The Seat no. is out of range! Movie Seats Reservation Summary of Seats: Seat 1: Reserve Seat 2: Available Seat 3: Available Seat 4: Available Seat 5: Available Enter seat no. (Press 0 to terminate Or the assigned seat capacity) : 1 The Seat no. is already reserved! Movie Seats Reservation Summary of Seats: Seat 1: Reserve Seat 2: Available Seat 3: Available Seat 4: Available Seat 5: Available Enter seat no. (Press 0 to terminate Or the assigned seat capacity) : 0 GoodBye... Thank You!!!

0 Answers  

Derive expression for converting RGB color parameters to HSV values

1 Answers  

main() { int i = 258; int *iPtr = &i; printf("%d %d", *((char*)iPtr), *((char*)iPtr+1) ); }

1 Answers  

int aaa() {printf(“Hi”);} int bbb(){printf(“hello”);} iny ccc(){printf(“bye”);} main() { int ( * ptr[3]) (); ptr[0] = aaa; ptr[1] = bbb; ptr[2] =ccc; ptr[2](); }

1 Answers  

void main() { static int i=5; if(--i){ main(); printf("%d ",i); } }

1 Answers