   Help choose the best sorting algorithm
  I have a problem with a homework assignment and I hope someone here can give me some hints.I'm given the following struct (this is in straight C):typedef struct Student_ {    char *name;    int average;} Student;A database of these structs is stored in a binary file. The file starts with the number of students, and for each student, it contains the name's length, the name and the average grade.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.The problem I have is that I am required to use the most efficient sorting algorithm possible. The ones we covered are:Bubble sortInsertion sortMerge sortQuicksortBucket sortTo make a long story slightly less long, I'm only familiar with the first four and my instructor told me that Bucket sort is the most efficient out of these.However, he said that I need to use the most efficient algorithm possible, which is different from just picking the one that is most efficient in general.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.I know that Merge sort is suitable for working with large files (when you can't hold all the data in memory at once), 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).I'm kind of lost here, so any hints you can offer me would be greatly appreciated.   
  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 bobofjoeAs 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_nAs 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).   