Thread: Linked List Sorting

Sure his question is unclear, but I have clearly stated that I took his question to be about the difference between taking n items and inserting each one one at a time into a list in order, vs appending all items into an unsorted list and then sorting it.
Inserting in order as you go is O(n*n) because each of the n inserts will at worst require comparing against every item that has already been inserted. It's one of those sums 1 + 2 + 3 + 4 + 5 which comes out to n(n+1)/2 IIRC and so is N-squared, no doubt about it. Yes each insert is O(n), but in order to compare it to the sorting case, you have to consider all the big-Oh notation of all of the n inserts.

As for sorting the array afterwards, nothing can sort in faster than O(n), so the O(n) inserts into the list to begin with will be irrelevant in terms of Big-Oh notation. Therefore the only thing relevant there is the Big-Oh notation of sorting a list. Merge sort does this in O(n*logn), in fact that's both best and worst case. Bucket sort would likely be even better.

As for his last question, there is no correct answer due to lack of information. He hasn't defined what "efficient" means for starters. Memory efficient, time efficient? Some function of the two?

Originally Posted by rcgldr

There's a third sequence, receiving the numbers to be sorted one at a time, but not having to use the sorted data until all numbers have been received.

You're describing the same case as me, so if you consider that a third option, I don't know what you consider the second one is.

Originally Posted by phantomotap

O_o

No. You don't.

The situation plays out exactly as I've, twice, explained; as before, you are ignoring very real conditions and possibilities.

We do need to know N. Let's say we've got two algorithms, one the best common case, O(log N), and one the worst common case, O(2^N). Which one to choose?
It depends on N. Is N is 100, then there's no way the O(2^N) algorithm is going to be viable. But what if N ranges from 0-8?
log 8 is 3, 2^8 is 256. So the O(log N) algorithm will be about 100 times faster, in terms of operations. But what is the constant? It could well be about 100, if the O(2^N) operation is simply a memory write, the O(log N) operation involves allocating memory and freeing it - that will take 100 machine instructions or so.

Then you've also got to take in account ease of implementation. If you can write the O(2^N) method in five minutes, whilst the O(log N) method will take the whole day to get right and debug (this is quite common, generally high O algorithms are straightforwards), then you've got to save a whole day of computer time to repay the investment. If O(N^2) takes a tenth of a second, O(log N) a tenth of millisecond, the function has to be run 24*60*60*10 times, or 864,000 times, before you're recouped the development time. So what do you want the function for? Is it in a time critical part of the code, is it run just once on program startup or in an inner loop?

Originally Posted by Malcolm McLean

We do need to know N. Let's say we've got two algorithms, one the best common case, O(log N), and one the worst common case, O(2^N). Which one to choose?
It depends on N. Is N is 100, then there's no way the O(2^N) algorithm is going to be viable. But what if N ranges from 0-8?
log 8 is 3, 2^8 is 256. So the O(log N) algorithm will be about 100 times faster, in terms of operations. But what is the constant? It could well be about 100, if the O(2^N) operation is simply a memory write, the O(log N) operation involves allocating memory and freeing it - that will take 100 machine instructions or so.

Then you've also got to take in account ease of implementation. If you can write the O(2^N) method in five minutes, whilst the O(log N) method will take the whole day to get right and debug (this is quite common, generally high O algorithms are straightforwards), then you've got to save a whole day of computer time to repay the investment. If O(N^2) takes a tenth of a second, O(log N) a tenth of millisecond, the function has to be run 24*60*60*10 times, or 864,000 times, before you're recouped the development time. So what do you want the function for? Is it in a time critical part of the code, is it run just once on program startup or in an inner loop?

There are other examples, too. For example, one common problem I come across at work has two solutions - one an O(N) operation, the other an O(1). However, the O(1) has double the expected disk I/O of the O(N) operation, so for small N, the O(N) is actually more efficient even though it uses more CPU time and more memory reads, because the memory reads are much faster than the disk reads. Above a critical value of N, the O(1) operation becomes the most efficient. When making a choice between the two approaches, it's important to consider what values of N are expected.

Originally Posted by rcgldr

What I thought was the second option was receiving the numbers to be sorted one at a time, but also receiving numbers to search for in the current state of the sorted list, so there's a search requirement in addition to the sort requirement while the numbers are being received. (For example the data to sort on could be the "key" portion of some type of database like record).

Oh okay. Yeah for that case I'd simply go with option 1.

Originally Posted by Malcolm McLean

We do need to know N.

I think Phantomotap has more of a problem with your use of the word "need" there, rather than your argument in general. I can tell because I've made the same mistake before.
Yes sometimes it might be useful to know the typical or absolute range on N, but it is never actually necessary.

Originally Posted by MutantJohn

So, has a conclusive answer been posted yet?

Maybe for the first question, but the OP is two questions, and for the first question, it's not clear if all the data is available before putting it into a linked list, and it's not clear if the second question has implications for the first question, such as will the list be searched while it's also being created?

Originally Posted by acho.arnold

Is it more efficient to sort an linked list after the values have been inserted into the list OR to sort and item before inserting into the list so as to create an ordered list.

And also Please what is the most efficient data Structure to use for Random insertion and searching of unordered Data?

For the first question, assuming all the data is available from the start, it would be quicker to sort the data first, then create a linked list using the sorted data, as opposed to creating the linked list first and then sorting the linked list.

For the second question, it's not clear if the searching is supposed to take place at the same time that some type of data structure (like a list or tree) is being created.

The OP never posted again in this thread, so it's not clear if the OP was trying to solve a specific problem, or just asking generic questions.

Originally Posted by MutantJohn

No, it's just a lot of reading and what seems to be bickering and a lot of, "We don't have the specifics yet".

And you know, not every post has to being with O_o. It really just makes your head look like this: 8====D

Sounds like you didn't read my very specific answers yet then. I made what I believe is a very good assumption about what was being asked - the same assumption you made in fact. I then stated that that was the question I was answering, and answered it correctly.

You however have come to a different conclusion. Without other information, sorting afterwards can and very likely would, be more efficient. Read my answers and you will understand why. Sorting afterwards would be equally as efficient as inserting as you went, if the algorithm chosen for sorting were insertion sort. In fact the processes would then be practically identical. Thus one must only choose an algorithm better than insertion sort to beat it.

Yes Insertion Sort is about the most efficient algorithm for sorting an already sorted list (provided it checks against the last item first, as you say). But you failed in not stating that as an assumption, and in the absence of that assumption, the conclusion is in fact wrong.

Name calling (implicit or otherwise) is not welcome on this board.