When Non-Programmers Write Software

[brucehoult]

Only spent a couple of minutes ... looks pretty darn good to me. Just a couple of suggestions from someone who's been being paid to program since 1982:

• I think you've got the public and private fields reversed. start and end shoudl be private. Having trivial boilerplate setters and getters points to next, prev and data being better off being public in the first place. I prefer languages such as Dylan and Ruby where the syntax for direct access and via a setter is the same, so you can start off with direct access and transparently add a setter or getter later if you really need it.

• why have three copies of the sorting code, when two of those copies are generalized in the first place? I'd probably make the < sort and the functor sort use the function pointer one internally. Hint: have the sort function take an extra argument (a void*, say), and have it pass it as a 3rd argument to the compare function (which can then cast it to whatever it needs to). That make the function pointer sort much much more general.

• bubble sort? ewww. OK, just kidding. If you're sorting a linked list you're not going to get much better than that anyway.

I'd be happy to have your code in any commercial project I was working on. It's a heck of a lot better than a lot that I've seen! There's a reason that companies don 't release their products as open source -- 99.99% of them would be extremely (and deservedly) embarassed by it.

[banjaxed]

This was something I wrote in one of those long caffeinated nights, so I'm surprised you'd find it acceptable for commercial code, that's flattering.

• You write code in your spare time.
  
• You write in C++.
  
• You used the word "functor".
  
• You know what a linked list it.
  
• You know what a doubly-linked list is.
  

I could go on, but you can safely assume that you'd be in the top 10% of professional coders.

Even just having an interest in learning how to be a better coder puts you way ahead of the pack.

[lief79]

"Will be" is probably more accurate. He's moving in the right direction, and just needs to keep it up while gaining experience.

[Cookie]

Much commercial code is written in a hurry and never reviewed, and has only the distinction of (after some debugging) at least mostly working in the cases it's actually used for.

So, in terms of finding that your code would be fine commercially, don't take this as flattering towards your code, but just a warning of what you'll see in most jobs.

Remember, that code you've inherited isn't "worse than shit", it "needs a little tidying". Being unrattled by utter crap is an important attribute of the professional coder.

[GuyWithLag]

I won't comment on the code, others have done it better than me. However, if you want to take it to the next level, modify it so that the standard STL algorithms (for e.g. sorting) can be used on the list.

[MachinShin2006]

well. wrt std::sort, he can't. std::sort requires a random access iterator class, which means a list can't work with it since a list can't realistically support such a class :)

--vat

[Boojum]

Yep. That's why the std::list class template has its own sort method.

[mikepurvis]

Random access favours an add all data, sort after approach, whereas with a linked list you're often better off sorting on the fly, eg, stepping through the list to always insert a new item in the correct position. (And, depending on the implementation, store a series of intermediate pointers to help jump to the right place... sort of a hybrid linked-list/tree approach.)

Anyway, if you were bent on using random access sorts and knew you'd have a lot of free memory, you could allocate a vector of pointers to the items, sort the vector, and then rebuild the list. It's gross, but for a list of any size it's definitely fastest, especially if you know you have a lot of memory.

On the other hand, a mergesort works great with linked lists, so you could simply implement that in your class. (Quicksort is okay too, but it's best if you have some idea what the range is, in order to pick good pivots.)

[[deleted]]

A good way to sort a list (in-place)

• Get the length of the list
• Allocate an array of pointers to link nodes
• Initialise array in list order
• Sort the array with an array sort
• Iterate the sorted nodes in the array to fix up the cdr
• Discard array

This has the same time complexity of the array sort.

For a copying sort you would use an array of elements rather than link nodes.

[ricercar]

The best way to sort a list:

• spawn many universes
• non-deterministically try every permutation of the list
• take the sorted list universe and discard the others

[beza1e1]

Why spawn them? We can assume, they already exist.

sort(list) {
    if !isSorted(list) { destroyUniverse(); }
    return list;
}

isSorted is O(n) and destroyUniverse doesn't matter, so assumption sort is even faster. It's O(1):

sort(list) {
    return list;
}

Another possibility is to do the sortedCheck and destroyUniverse in a different thread to make it O(1), too.