I'm working on my final thesis for a CS grade course and I want to use a common sorting algorithm (quicksort for the curious ones). Do I need to include a reference to this algorithm (cite or quote)? Or it is so common that I don't need to? Take into accout that it was first published on 1961 and it is extremely used and known by almost anyone in the CS world.
-
1It is really up to you (and your advisor perhaps). In any case, chasing down the reference for quicksort, and even some of the quite voluminous bibliography on it's analysis, isn't that much work, and a handful of references will hardly lead to overrunning any maximal page count...– vonbrandAug 12, 2019 at 14:25
-
2What does "use" mean in this context? Are you writing a program, or just describing the algorithm itself?– pip install frisbeeAug 12, 2019 at 17:32
-
10Does it matter what particular algorithm is used, or is the important point the fact that your data gets sorted somehow?– jamesqfAug 13, 2019 at 4:41
-
3If you need to cite a specific thing (e.g. a lemma used in the original proof of correctness/complexity for example) then definitely cite it no matter how well known it is. If you are simply defining a new algorithm and one step is "sort this array using quicksort" then a citation may not be needed (in fact at this point you may consider just saying something like "sort the array using any O(n logn) algorithm" if you don't have more specific requirements about the sorting algorithm).– Giacomo AlzettaAug 13, 2019 at 9:30
-
4Whatever you decide, make sure you cite this stackexchange article for justification ;)– shanebAug 13, 2019 at 22:57
|
Show 3 more comments
7 Answers
Do I have to cite common CS algorithms?
No.
The fact that it was first published [in] 1961 isn't relevant, you needn't cite it because it is [widely] used and [well-]known by almost anyone in the CS world.
That said, although a citation isn't necessary, you can provide one at your discretion. Such a citation is probably more important for a final thesis than for an academic publication, since it may be considered important for students to demonstrate they can cite.
Beyond citing the original source, you may like to cite your favourite textbook(s) on the topic (rather than citing the entire volume, reference a particular section, e.g., \cite[Chapter 4.3]{Textbook} in LaTeX).
-
1I was told that citing a textbook is "unprofessonal", that a "professional" article should always cite a research article or a monograph. Not sure I buy that, but at the time I had to change the citation.– sdsAug 13, 2019 at 15:59
-
13@sds Eh. I think one should look at the purpose of the citation. I don't think there's anything wrong with citing textbooks from other fields (e.g., I'm a computer scientist and have cited textbooks from mathematics), or where you need some obscure detail that's presented in one (I've cited Knuth for a specific fact about the performance of hash tables). The problem comes when you're citing a textbook for something that's common knowledge and, there, the problem is more that you're citing at all, rather than that you're citing a textbook. Aug 13, 2019 at 16:53
-
6@sds Following the previous comment one should look at the purpose of the citation: Sources beyond the original manuscript can offer additional insights which are useful to the reader. You may even choose to signpost such sources, e.g., "Knuth summarises topic X and provides a detailed performance analysis."– user2768Aug 13, 2019 at 17:01
-
2@Basile What's the point of such a citation? I mean every self respecting computer scientist will have read CLRS and have a copy in reach, so what value is it adding to the paper? If you can point to any specific detail that's important, sure, but just a "hey I used quicksort and as everyone here knows you can look it up in that book" seems unnecessary.– VooAug 13, 2019 at 22:05
-
2@sds I have cited textbooks in a paper and the paper got in to a good conference. None of the reviewers said anything. That's just one data point, but citing a textbook when required is definitely not unprofessional.– xuq01Aug 14, 2019 at 0:37
If the specific use of the algorithm is important to the work, then you should cite what specifically you used or implemented, and also citing the broadest/oldest class of algorithms would be strictly optional. Using the example of quicksort, there are many dozens of varieties of it that have the same general idea but have different characteristics and performance. If you used the 1961 paper as a reference for your implementation, then of course you would cite it. If you used the Java or C++ sort function (which are different and have changed between versions - mergesort, timsort, hybrid, etc.), you would just say so and don't need to hunt down what that was based on.
On the other hand, if sorting is not an important part of the work (it matters only that it was sorted, not how you sorted it), it is common and accepted not to bother citing every last little detail like this. In most cases how something was sorted is so unimportant that it isn't even mentioned in text at all, but of course if your work is on sorting algorithms (and in a thesis) you should be more detailed and cite liberally.
As this is not for a conference but for a thesis, and possibly part of a graded course, you should probably just cite it anyway, possibly both the original and whatever source you actually used for reference (textbook, code library, whatever). Especially at the less-than-PhD level, instructors are much more likely to prefer heavy use of citations, and I've known many professors to ding for lack of citation of things that one would not bother to mention or cite in an actual paper.
-
5Cool answer also. I understood that this topic is a lot about context, nature and audience of the publication. Aug 12, 2019 at 14:55
-
1This is the best answer I've seen. Regarding the second paragraph, I think omitting any citation when you only care that something is sorted (or analogous other outputs) is reasonable insomuch as it's obvious that sorting is possible. If it's not obvious that a particular arrangement you need can be obtained from an arbitrary input, you should cite the result that proved that it is possible. Aug 14, 2019 at 21:32
-
Note: Java's standard sorting implementation used by most of its sorting methods is timsort since Java 7. Before that, it used to be mergesort. Aug 15, 2019 at 10:21
-
@VictorStafusa Ah, mergesort, my memory failed me, thanks for the correction!– BrianHAug 15, 2019 at 12:21
"Quicksort" today rarely refers to the 1961 version; the algorithm has been improved since then. If you're going to cite, you should of course cite something that's relevant to your thesis. As others stated, if you just needed an algorithm to get things sorted, that doesn't need citing. But if your thesis did depend on the details of sorting, then is suddenly becomes important to cite, and cite right.
I'll take what appears to be a surprisingly contrarian position on this:
Yes, you need to cite the implementation you used, in a scientific paper.
It is far too common that scientists working elsewhere trying to reproduce results fail to do so, and waste a lot of time trying to make sure their setups and steps are just the same as what they're trying to replicate. Too often, the issue comes down to a particular bug in a software package that one lab or the other is using, or a different choice in an implementation detail nobody knew mattered. By citing the specific implementation you used, including the version number of packages where available, you can eliminate a potential source of frustration (and/or false fraud accusations!), at relatively little additional cost when writing. (Note that sometimes, that "other lab" may be a future you!)
If you are using a quick implementation found online, citation may also be required by the license on the source. For example, you could say "I used the Java implementation of Quicksort found at https://en.wikibooks.org/w/index.php?title=Algorithm_Implementation/Sorting/Quicksort&oldid=3562350#Java" (note use of the "oldid" parameter to tie to a specific version; click View History and then the latest date to get that in the URL). That attribution is arguably required by the license; similar story for what you find on Stack Overflow.
This also provides a means of credit for those who may have spent a lot of time (that they could have spent on something else) writing a software package that is useful for the broader community. The credit aspect is probably more important for academic developers than commercial ones. In those cases, there may be a paper announcing or describing the package, which you can and should cite for this purpose.
No, if the algorithm has a well-known name that means that it is assumed that you are not the author and that readers can get familiar by using that name as a reference. In a similar way when you are writing a math paper, you don't need to create a reference every time you use terms like Hamel basis, Lagrangian, Gaussian distribution, Fourier transform, etc., because it is well known like QuickSort, TimSort, simplex method... using a specific name is enough reference for the reader.
-
I was just thinking about this the other day. What one person considers "well-known" or common knowledge, isn't so for another person. QuickSort is a great example. Most people who have studied any computer science would know it. However, the average person on the street wouldn't. For example the person at the grocery store checkout probably wouldn't. So when deciding to cite something as a reference, does it come down to if it's considered "common knowledge" given the topic of the work? Aug 14, 2019 at 10:15
-
"Every time"? No, just the first time. Certainly in a thesis. See my answer. Aug 14, 2019 at 14:28
-
1Isn't the name itself a reference? If I say Fourier Transform everyone would know that I don't get a credit for that and the name is a reference to the formula/work that everyone can find out easily (even more than having a link to a paper from 1800s) Aug 14, 2019 at 16:41
-
@Celeritas "common knowledge" within the target audience of the paper. Whether an academic paper is properly cited for, or even meaningful to, most grocery store checkout staff is not an interesting question. Aug 15, 2019 at 9:56
Do I have to cite common CS algorithms?
Generally, and in a thesis, yes.
Why?
- You may consider it common, others may not; not everyone is in the same sub-field of Computer Science.
- You may be using a variant of the algorithm which is less ubiquitous; or a specific implementation, as @WBT suggests.
- If you're using terms from the definition or specification of the algorithm, it may be useful for the reader to have access to some textbook for reference/inspiration/whatever.
- Actually, it's rarely a bad idea to find an excuse to refer to a nice textbook. Pick a good one!
- It's a thesis, it's not as though your pressed for space or anything.
- Better to err on the side of caution with citations.
Specifically for quicksort - mmm, maybe not, can't say for sure; depends on the specifics.
answered Aug 14, 2019 at 14:24
If your results depend on some property of the quicksort algorithm, for example on its typical or worst-case performance, then you should cite a paper that demonstrates that the algorithm has those properties. For example if you deliberately chose an algorithm that works well when the data is already sorted, it might be best to cite some paper that compares sorting algorithms and demonstrates that quicksort is a good choice in this scenario. (I don't recall whether that's actually true, it's just an example).
If any sorting algorithm would do, then you don't really need to justify your choice; indeed, you don't really need to say what algorithm you chose.
Personally I don't think you need to cite a paper that explains what QuickSort is; it's more relevant to cite something that explains why it was the right choice for your particular application.
-
In case of quicksort, everything depends on how the pivot is choosen. Most of the implementations I've saw have some pathological cases that makes it vulnerable to O(n^2) behaviour. A frequent case of those is when the list is already sorted. A simple case that defeats many of the naiver defenses against O(n^2) is when the list consists solely of a bunch of repetitions of a single element. Aug 15, 2019 at 10:27