+Correction to the above post
This is not possible even with a counting sort because insertion still
takes O(n*n)
merge sort seems to be the best for it
On Jan 31, 6:23 pm, sankalp srivastava richi.sankalp1...@gmail.com
wrote:
@manoj
the great recursion problem has the time complexity as
Hi Guys..After a Good Discussion...I Found that we can sort the DLL
in O(n)..as most of you are saying that there is well known bound on
comparison sort (nlogn)
But still i have a doubt that we can sort the array,Singly Linked List
(SLL) in (nlogn) ..both single thing associated with it..array
@sankalp how will you solve using count sort . I would like to have your
solution :)
On Mon, Jan 31, 2011 at 6:53 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
@manoj
the great recursion problem has the time complexity as
tn=2(T(n/2))+O(1) . It is not linear .
ur algo is O(nlog
n be the minimum value in the list
m be the maximum value in the list
Have an array C[m-n]
Initialize C to zero.
now
Node *node=head;
while(node!=NULL)
{
C[node-info-n]++;
}
now using the array C,create a sorted list.
Since we are using doubly linked list,we might have some other
sorry in above solution add node=node-next in while loop
On Wed, Feb 2, 2011 at 1:05 AM, HARISH S.C s.c.har...@gmail.com wrote:
n be the minimum value in the list
m be the maximum value in the list
Have an array C[m-n]
Initialize C to zero.
now
Node *node=head;
while(node!=NULL)
{
Create BST of given list...
1. using extra space now you can create DLL and inorder traversal
2. Create sorted linked list from DLL, Great tree list recusion
(cslibrary.stanford.edu/109/TreeListRecursion.pdf)
On Jan 31, 12:11 am, bittu shashank7andr...@gmail.com wrote:
can u provide
@above Are you kidding? :) What is the complexity of your solution? And why
not simply use merge sort?!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this
@manoj
the great recursion problem has the time complexity as
tn=2(T(n/2))+O(1) . It is not linear .
ur algo is O(nlog n)
This can be possible using a counting sort (again , use Bitsets to
save ur space )
--
You received this message because you are subscribed to the Google Groups
Algorithm
It is not possible using comparison sort.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
cannot figure out..
On Sun, Jan 30, 2011 at 8:48 PM, juver++ avpostni...@gmail.com wrote:
It is not possible using comparison sort.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@above...
we have to sort the DLL ..so navies solution prduce the O(n^2)
solution using merger sort we can do it in (nlogn)...but using merger
we can also sortv the doubly linked list in (nlogn) then what is
benefit of having perv pointer in DLL ..so according to me we can do
it in O(n) because
There is a well-known bound for the comparison sort, O(nlogn).
If there is a way to sort doubly-linked list in a linear time, so we are
able to sort all sequencies in this time.
But it is impossible!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
O(n) is impossible even for an array where we can do random access.
On Sun, Jan 30, 2011 at 11:39 AM, juver++ avpostni...@gmail.com wrote:
There is a well-known bound for the comparison sort, O(nlogn).
If there is a way to sort doubly-linked list in a linear time, so we are
able to sort all
if we can do it for DLL using Comparison sort, then why not for array
make an DLL of elements of array, sort in DLL and put back in array.
not possible using Comparison sort.
i think interviewer asked this question to see your reasoning, how you
handle these type of question ?
--
You received
can u provide solution..nlogn or n^2 ..write algo..or exact working
code for this...
thanks
shashank
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this
15 matches
Mail list logo
