How do you sort a Linked List (singly connected) in O(n)
How do you sort a Linked List (singly connected) in O(n)?
This is not a place to post assignment. I am sick of people posting their assignment and hoping someone to answer it. No one's gonna solve your problem while you're in a job interview. Study hard keeping that in mind. This thing will only make you lazy and degrade your learning habbit. Try to learn from books and google it yourself. I'm sure there must be hundreds of solutions for this in google as this is a pretty popular problem.
FYI..this is not an assignment and I am not a college guy. I know how to sort in O(n^2) andO(nlogn), Just didn't know how to sort in O(n) and thought somebody could help me here in sajha..!!
If u don't know anything....just keep quite..I posted this question assuming somebody will provide the algorithms steps and we can discuss on it...didn't know moron like you would come in between!!
No, you can not sort in O(n) time. Sorting requires comparison and reinsertion of items, so it is almost impossible to do it in O(n) time unless you are starting off with empty or already sorted array.
is O(n) worst case? if it is you might wanna try radix sort, counting sort or some other non-comparison based sorting technique.
i am confused now. O(n) is just a reference to time?? or is it the number of objects required??
O(n) is the asymptotic upper bound of algorithm, the best case is known as big Sigma(n), and the average case is known as big Theta(n). O(n) is usually considered as it represents the worst case of an algorithm. There are notation such as small o(n) and small omega(n) which are upper and lower case but are not asymptotically bounded.
In the simplest word, O(n) is the worst case running time of an algorithm.
Most of the non comparison based sorting techniques are either unstable or assume that the number of items to be sorted is much less than 2^k (k is the size of each key). Counting sort is exponential in runtime cost in worst case. The only sorting algorithm that is stable and can be implemented fairly easily is LSD radix sort, but getting n much less than 2^k is very hard. (See
wikipedia)
I think here is a confusion
I was referring O(n) as Computational complexity.
O(n) is not the worst case running time.
The complexity order is { O(n^2), O(nlogn), O(n), O(logn)} worst case to best case respectively.
See the Order
here
My answer for a simple explanation for big O notation was for 1987 AD.
Wai_wai,
Computational complexity is measured either in running time or memory usage. If you read further in the link you have provided, it clearly says that big O only provides upper bound. Sorry, if I am making it confusing here, but whatever I wrote in my previous post is true. Big O(n) only gives the upper bound.
hmmm.. still confuses me, but what worries me is that i am a cs major and i have never heard about these logarithmic terms before. i know i have to take some more classes related to logarithms, but just so that i get an idea, at what level do we need to know all these?
i am technically 3rd year (recently transferred), but from looking at my required classes, it will still take me about 3 more to graduate.(BSc in CS)
i do understand the assymptotic behaviour and all, but from the maths classes i have taken, so i am guessing the term means the same.
, @ Gajedi: O(n) doesn't always mean worst-case its just the upper bound. Worst case means what is the maximum running time the sorting algorithm can take if the input is arranged in the worst order for that particular algorithm. For example, look at the table in http://en.wikipedia.org/wiki/Sorting_algorithm
@1987 AD: I studied this in my "Data Structures and Algorithms" class. It was a 300-level course @ my univ where courses are upto 400-level max in undergrad. It is very important for programming and other applications. The saying goes like, " You can either program for 10 years and be a good programmer, or your can take an alogrithms class and be one in 3 :)"
Sarkar123,
First and foremost, wikipedia is not a credible source. Read my previous reply about O and other notations. O is the upper bound which in fact defines the worst case behavior of an algorithm.
If you read the book "Introduction to Algorithm" and specially "Growth of functions", you will understand the concept clearly. The growth of a function is defined in terms of big Omega, Theta, and O notation (if tightly bound) which are nothing less than best, average, and worst case running time of an algorithm.
@Gajedi: Notations (sigma, O, theta) and cases (worst, average, best) are different things.
http://lcm.csa.iisc.ernet.in/dsa/node9.html
http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html
@wai wai: I think the sorting you wanna do is Bucket sort. Though I am not very familiar with that one!
http://www.cs.cmu.edu/~pattis/15-1XX/15-200/lectures/listprocessing/index.html
Sarkar, Are you sure they are different than the notations? Please read the whole thing in the link you have provided and not just one page talking about big O.
@Wai_Wai
What type of value does the List contains. If it's an integer then what will be the range??
As someone previously suggested, the sorting algorithm will depend on the type of value in the List.
There are couple of options:
1. Use a Heap (min heap). First insert all, then remove one by one. -- o(nlogn)
2. Use a lookup array. i.e. something like bucket sort. O(n + m) where n is the size of the list and m is the size of the lookup array
3. Insert all and remove all from a BST. -- O(nlogn)
For the requirement of O(n) I would rather go for bucket sort like algorithm:
First determine the range of values in the list.
And sort it based on the value or alternatively create a new List with those values.
@ Gajedi: They might look alike but they are different. Big-O doesn't HAVE to be a worst case. How would you then explain the best case running time of an insertion sort to be O(n), average case to be O(n2) and worst case be O(n2)? A worst case running time could have a Theta(n) or a Omega(n) notation (sorry in the previous thread I wrote sigma for omega). It all depends. Normally for sorting we use big-O in ALL cases (be it worst, average or best). But for other things, for eg. the worst case running time of inserting or finding a key in a hash table is always Theta(n).
I have the following lecture from UCBerkeley that might make it clear for you. The link to this lecture is http://www.eecs.berkeley.edu/~jrs/61b/lec/21 . Scroll down the paragraph before the title "ALGORITHMIC ANALYSIS"
"Remember that the choice of O, Omega, or Theta is _independent_ of whether
we're talking about worst-case running time, best-case running time,
average-case running time, memory use, annual beer consumption as a function of
population, or some other function. The function has to be specified.
"Big-Oh" is NOT a synonym for "worst-case running time," and Omega is not a
synonym for "best-case running time."
Please log in to reply to this post
You can also log in using your Facebook
