Help choose the best sorting algorithm

As a general rule, unless there is a very outstanding reason to use otherwise, a hybrid approach using quicksort -> heapsort is optimal for most situations. If you don't want to implemlent the hybrid, quicksort will be the fastest algorithm in most cases as well.

So, the question is: Is there any reason not to use quicksort?

Quote:

Original post by bobofjoe As a general rule, unless there is a very outstanding reason to use otherwise, a hybrid approach using quicksort -> heapsort is optimal for most situations. If you don't want to implemlent the hybrid, quicksort will be the fastest algorithm in most cases as well.

First, we didn't cover heapsort so that's out.

Second, according to my instructor, Bucket sort is the most efficient out of the ones I listed, so I guess that's the best choice in general.

Quote:

So, the question is: Is there any reason not to use quicksort?

Well that's kind of what I'm asking. Is there something about this problem that makes it different than a general sorting problem?

The fact that the instructor emphasized the difference between the most efficient algorithm in general and the most efficient one possible in this case makes me think that there is.

Do several ones, and test their efficiency with a sample set of data. choose the one that appears the most efficient.

Quote:

I couldn't get him to clarify this much, but basically it seems like one of the other algorithms might be more suitable in this particular case. But I don't see what makes this problem any different than a general sorting problem.

Your first four algorithms are comparison sorts; this means that, to sort a set of items, they only need a comparison function that can decide whether one item is smaller than another.

It can be (and has been ;) proven that comparison-based sorts have an O(nlog(n)) lower bound on time complexity; this means that a sorting algorithm that uses only comparisons cannot be asymptotically faster than O(nlog(n)) on the size of the input.

In fact, insertion sort and bubble sort have expected O(n^2) running times. Quicksort has expected O(nlog(n)) but worst-case O(n^2) running time (careful; if you don't protect against it it can leave you open to attack). Merge sort has worst-case O(nlog(n)) running time.

Bucket sort is a different sort of beast; it is not a comparison sort. It has an additional requirement on the items it can be applied to: in addition to needing comparison function, the items the algorithm can sort must be taken from a finite range. Radix sort is a close cousin, for another example.

So it is less general than a comparison-based sort; it doesn't work in every case where a comparison sort works. BUT, if your input set is taken from a finite range (your items fall between a "minimum" possible item and a "maximum" possible item conceptually) it can break the O(nlog(n)) lower bound of a comparison sort and sort in linear time, that is, O(n).

Your example is interesting for the following reason: at first glance, names can be any length, so it seems you have to use a comparison sort; this means that building the offset file will take O(nlog(n)) asymptotic time.

On a closer look; the file is immutable. This means you can find the length of the longest name in a linear O(n) pass through the file. This means you can bound the domain of your sort function and thus apply a linear time bucket sort instead of a comparison sort. Using this technique, you can reduce the asymtotic complexity of the problem from O(nlog(n)) to O(n), a strictly faster algorithm (in the theoretical sense; practical considerations may apply). Linear pass to determine range + bucket sort beats naive comparison sort asymptotically.

Anonymous P: Thank you, that was a great explanation.

So it seems like Bucket sort is indeed the most efficient algorithm to use here. Unfortunately the deadline on this assignment is nearing and I'm not sure if I'll have enough time to learn how it works, but I'll try.

Thanks everyone for their help.

Quote:

Second, according to my instructor, Bucket sort is the most efficient out of the ones I listed, so I guess that's the best choice in general.

Hehe, no it's not. It's the best choice in particular, when your problem fits its constraints. It's less general than the other methods.

Quote:

Do several ones, and test their efficiency with a sample set of data. choose the one that appears the most efficient.

I beg your pardon? I'd assume he's studying to become a computer scientist, not a medieval alchemist.

This sort of approach is what keeps software crappy. Take a well-understood problem like sorting, one of the (sadly) few programming problems whose complexity can be unambiguously bounded and guaranteed.

Speciesunknown comes along; "instead of doing the math, test on some sample and pick the best for that particular sample you pulled out of your rear end. Never mind that optimal bounds are known; who needs them?"

Someone builds an application on top of this algorithm. Because it was picked based on its performance on some particular samples, it has worst case O(n^2) complexity. A happy hacker who DID pay attention in college builds worst-case input and brings down your system. Even more banally, my mom happens to provide worst-case input and brings it down. This has actually happened because people used naive quicksort when they weren't supposed to.

So in general it's best tro iterate through the sample to find the max and min sizes, and use bucket short rather than a straight comparison sort?

As the bucket sort approach has a complexity of O(n) and the comparision sort of O(n * log(n)), there should be a n where the bucket sort is faster for n or more students in your file.

As the O-Notation doesn't consider constants, it could be that the comparision sort is faster up to a specific n. For example for just 10 students it might be faster, but for 20 or more the bucket sort might be faster.

Quote:

Original post by joachim_n As the bucket sort approach has a complexity of O(n) and the comparision sort of O(n * log(n)), there should be a n where the bucket sort is faster for n or more students in your file.

It would be more accurate to say that bucket sort has complexity O(n plus m)where m is the distance between the smallest and the largest elements; in case of sorting a list of strings, you have to look at the range of the mapping from string to index of the bucket table.
If m is greater than n*log(n) bucket is not optimal, not even asymptotically (m may depend on n and grow faster): so you should carefully choose your mapping function (e.g. avoid to concat all the chars of the filenames in a long long long int).
Bucket sort require (in general) much more memory than the other sorting algorithms (again, this depends on the mapping function and the value of the elements).

Do you HAVE to implement the sort yourself? Can't you just use qsort (C) or std::sort (C++)?

Quote:

but I don't think it applies here because I can just use the offsets to fetch each name only when I need it (and this is a constant time operation).

Really? (let's forget the fact that disk access goes through about 8 levels of cache on today's computers).

Disk has 7200 rpm, 120 rps. Worst-case scenario is that you need to always fetch the record you just passed. You will be able to access 120 records per second.

Now, sector holds 512 bytes, there's some 200 sectors per track, resulting in 100kb of data per track that can be read per revolution. If average length of name is 20 characters, it means you can read about 5000 names per second if you access them sequentially.

Consider quick-sort, which by definition traverses records in the opposite direction half of the time vs. merge sort which can be made to work fully sequentially.

Unfortunately, Turing machine is great for algorithms, but doesn't work well in practice. Reading a name is sequential operation which requires two reads (first the length n, then reading n bytes). This requires 2 revolutions for every name that has to be read (disk keeps on spinning after reading n and CPU cannot respond fast enough to issue another read), resulting in 60 names per second at most.

And since comparison requires two names, we end up with 30 comparisons per second.

Ouch...

Long story short - cache characteristics will determine run-time performance. Regardless of which algorithm you choose, the efficiency will be increased by a factor of 100-100000 by keeping part of data in memory. Note that today's OS does this for you and uses tens to hundreds of megabytes of RAM for this very purpose. So simply saying "my algorithm uses no extra memory" is not accurate.

Disks really are horribly painfully slow devices. It's the cache that makes them behave almost like random access media.

BTW: this is why data locality is preferred to mandatory pointer references where applicable. Each dereference can be seen as disk seek (a slow operation). While often not a problem in practice, if one is confronted with extreme run-time requirements, locality of data becomes huge issue. It's also one of the few real limiting factors when using managed memory, which, regardless of capabilities of virtual machines, imposes run-time performance limits.

Conclusion for theoretical case: algorithm with least of comparisons will win (absolute number, not necessarily O(n) notation). We don't require swaps for generating offset list, or at very least, we don't need to access record name for it.

For practical case, profile, store in memory, buy faster RAID disk, use cloud computing, use SQL, etc....

Quote:

Original post by DevFred Do you HAVE to implement the sort yourself? Can't you just use qsort (C) or std::sort (C++)?

It sounds like it's the point of the assignment, yes. It seems that it's still believed that the best way to learn this stuff is to actually do it, instead of just thinking about it in depth and then moving on to more practical tasks.

I was just wondering because this

Quote:

Original post by Gage64 I need to write a program that takes such a file and creates an offset file for it, that is, a file containing offsets into the database such that each offset "points" to a student. The offsets have to be laid out such that if you go through them in order, you'll get the students sorted by name.

made me think it was already "hard" enough to do this with library functions, i.e. what do you pass to qsort? Because what you sort is not the data itself but an indirection. Try to get those void pointers and casts right the first time ;)

Bucket sort is another name for a radix sort correct?

Its a very efficient sort for simple lexicographical sorting from what i gather, but i think it has some caveats with large data sets wrt memory use.

If i were you id use std sort and comment that premature optimisation is the root of all evil, if it works it works. better to complete the task with an inefficient algorithm than hand it in 3 weeks late with a perfect solution.

Quote:

It would be more accurate to say that bucket sort has complexity O(n plus m)where m is the distance between the smallest and the largest elements; in case of sorting a list of strings, you have to look at the range of the mapping from string to index of the bucket table. If m is greater than n*log(n) bucket is not optimal, not even asymptotically (m may depend on n and grow faster): so you should carefully choose your mapping function (e.g. avoid to concat all the chars of the filenames in a long long long int). Bucket sort require (in general) much more memory than the other sorting algorithms (again, this depends on the mapping function and the value of the elements).

That's true for pigeonhole sort, a close cousin of bucket sort, but thankfully bucket sort's different: its worst case is the same as comparison sort if the number of buckets is chosen appropriately.

I'll apologize for having been less than clear about this aspect in my previous explanation, and it does sound like I'm claiming bucket sort will always be linear for problems like the above, which I'm definitely not. I'll take another stab at a better explanation.

So: bucket sort (as long as the number of buckets is chosen appropriately) is optimal for this problem; it'll always asymptotically perform at least as well as a comparison sort, and will sometimes (depending on the ranges of the keys) be asymptotically faster.

1) Why is bucket sort not O(n + m) complex, where m is the cardinality of its domain,as claimed above?

That's the complexity of pigeonhole sort, where each bucket holds only one element in the range.

We can choose the number of buckets in bucket sort, and we can choose the sorting function that sorts each bucket.

It turns out that, given n things to sort, if the number of buckets we choose is a linear function of n and the sort we choose for the buckets is a comparison sort, the worst-case asymptotic complexity of bucket sort is that of the comparison sort it uses, and the best case is linear.

Why?

The time complexity of bucket sort is the time it takes to traverse each bucket, O(m), times the time it takes to sort each bucket.

If we choose the number of buckets m to be a linear function of n (for example, the number of buckets is the number of elements to be sorted), the complexity of traversing the buckets is O(n), linear in the input size; so we're left with the complexity of sorting each bucket.

Now the performance depends on the range of values that the input can take and on the input's distribution over that range:

In the worst case, range is large and all elements are in one bucket; in that case, the complexity of the bucket sort is the complexity of the comparison it uses to sort the bucket.

So the worst case complexity of bucket sort with number of buckets proportional to input set size and an optimal comparison sort is O(nlog(n)): it is asymptotically equivalent to the comparison sort, which makes sense. So it will always perform at least as well as a comparison-based sort (asymptotically; practically is another matter).

Can it sometimes do better?

In the best case, the range is equal to the number of elements n and the comparison sort is never applied (one element per bucket). In that case, the asymptotic complexity of the bucket sort is O(n), strictly faster than a comparison-based sort.

The intuition to take away is that, given a fixed domain for the input range, the more elements we need to sort, the faster bucket sort gets compared to comparison sort, and if we choose a number of buckets proportional to the input size n, we're guaranteed asymptotic complexity equal to that of comparison sort.

It's really an underconstrained problem if there is no stated
maximum number of students and configuration of the system
to do the sorting. Suppose the number of students was 6 billion,
and your pc had only 1mb of memory available.

Quote:

Original post by Zahlman Quote: Original post by DevFred Do you HAVE to implement the sort yourself? Can't you just use qsort (C) or std::sort (C++)? It sounds like it's the point of the assignment, yes. It seems that it's still believed that the best way to learn this stuff is to actually do it, instead of just thinking about it in depth and then moving on to more practical tasks.

I sort of agree though. I found heaps of my fellow classmates able to describe the algorithm on a whiteboard, but were never able to use it in programming even when they didn't have to implement the sort themselves. They kept trying to apply sorts to data sets that would not behave optimally. Once we got around to implementing the algorithms, and they had to write the damn things themselves (and thus head-butt the constraints on particular algorithms), they suddenly learnt more about the algorithms than just the conceptual view.

Quote:

Original post by DevFred Do you HAVE to implement the sort yourself?

Yes.

Quote:

Original post by Antheus Consider quick-sort, which by definition traverses records in the opposite direction half of the time vs. merge sort which can be made to work fully sequentially.

But here I'm required to sort the offset file (or rather, create a sorted offset file), not the students file, and when comparing two offsets, I have to retrieve the names to which they refer. So it seems to me that merge sort's advantage is lost here because the students file will not be accessed sequentially.

Or am I looking at this the wrong way?

Quote:

Original post by Anonymous P choose the number of buckets m to be a linear function of n

In fact that's a good idea.

Quote:

Original post by Anonymous P Quote: Do several ones, and test their efficiency with a sample set of data. choose the one that appears the most efficient. I beg your pardon? I'd assume he's studying to become a computer scientist, not a medieval alchemist.

True, but since this is homework and the op showed to be interested in the matter, why not implement them all and then who cares which one is shown to the professor? (Show him them all to get the best grade!)