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 do you create a really large matrix (i.e. 3500x3500) in C without having the program crash? I can only reach up to 2500. It must have something to do with lack of memory. Please help!

1 Answers  

What is the match merge ? compare data step match merge with proc sql merge - how many types are there ? data step vs proc sql

0 Answers  

main() { int i=400,j=300; printf("%d..%d"); }

3 Answers  

Find your day from your DOB?

15 Answers   Accenture, Microsoft,

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.

9 Answers   Microsoft,

How to read a directory in a C program?

4 Answers  

main() { int i; clrscr(); printf("%d", &i)+1; scanf("%d", i)-1; } a. Runtime error. b. Runtime error. Access violation. c. Compile error. Illegal syntax d. None of the above

1 Answers   HCL,

&#8206;#define good bad main() { int good=1; int bad=0; printf ("good is:%d",good); }

2 Answers  

main() { int i = 3; for (;i++=0;) printf(“%d”,i); }

1 Answers   CSC,

main() { int c = 5; printf("%d", main||c); } a. 1 b. 5 c. 0 d. none of the above

2 Answers   HCL,

How to access command-line arguments?

4 Answers  

#include<stdio.h> main() { int i=1,j=2; switch(i) { case 1: printf("GOOD"); break; case j: printf("BAD"); break; } }

1 Answers