CODEWITHSUNDEEP
algorithmsorting
user360907
user360907

Reputation:

Relevance of Quicksort, Heapsort and Bubblesort

I'm currently enrolled on a 1 year masters course in Applied Computing that is intended to take people without a background in computing and give them a crash course in a software development and engineering and prepare us for a career in the technology industry. One of the classes on the course, Advanced Programming Techniques, covers a number of sorting algorithms implemented in C++, namely Quicksort, Heapsort and Bubblesort. However, a number of the undergraduates have told us that these algorithms are not relevant to industry and are not widely used. Is this true, and if so, what sorting algorithms should I be looking at?

Upvotes: 0

Views: 383

Answers (5)

Dario
Dario

Reputation: 49208

  • Bubblesort has an extremely bad performance and is probably just of educational value to demonstrate this.

  • Heapsort is a reliable and theoretically (i.e. from a complexity theory point of view) fast algorithm that - in practice - turns out to be slower than other algorithms with the same degree of complexity like quicksort.

  • Quicksort on the other hand is really fast but has a terrible worst-case for some unfortunate inputs.

In practice, you will implement neither of them but use existing, highly optimized sorting routines (maybe that's what they mean).

These will be combinations of many algorithms to counter the deficits each of them has. You might see Introsort which uses quicksort + heapsort to reduce the worst-case scenario or even an insertion sort for small inputs.

Upvotes: 3

JB King
JB King

Reputation: 11910

I've seen a few implementations of Quicksort though Bubblesort is rarely used except for teaching cases. Teaching someone why something is horrible can be useful which may be part of what you are missing here for why you should know a little about it. While some people may just go "Duh!" for why Bubblesort is awful there may be some that need to see better evidence of why other ways are better. Sorting is the kind of problem that has been well studied while other general problems may not be so quite well-studied,e.g. look at various algorithms to solve NP-complete problems like the traveling salesman problem.

Upvotes: 0

Artem Volkhin
Artem Volkhin

Reputation: 1372

Bubble sort is slow, O(n^2). The most commonly used is quicksort. Average time - O(n log n) but O(n^2) in worst case. Merge sort (heapsort) works O(n log n) in worst case, but it's a bit more difficult to implement than quicksort.

Upvotes: 0

dfb
dfb

Reputation: 13289

What these people most likely mean is - at work, I never have to reimplement a sorting routine, why should I learn something that's already written?

I'd say knowing these is useful for the foundations of what you will learn later. It's considered general computer science knowledge and learning any new algorithm will help you learn other concepts more thoroughly. Quicksort can teach you about how randomized algorithms can lead to better solutions. Merge sort is good for learning about recursion. Heapsort neatly demonstrates data structure time/space trade offs. etc. etc.

If nothing else, they are good to know for interviews.

Upvotes: 0

jason
jason

Reputation: 241611

Quicksort, Heapsort and Buublesort. However, a number of the undergraduates have told us that these algorithms are not relevant to industry and are not widely used.

This is patently false. You will see Quicksort in the wild and likely even heapsort.

Is this true, and if so, what sorting algorithms should I be looking at?

The point of learning these algorithms, even if they aren't necessarily used in industry, is to understand how algorithms are put together, how to analyze them (what is the worst case, what is the best case, what is the asymptotic behavior, etc.) and how to prove they are correct.

The point is to develop skills about how to reason and think about and understand algorithms, not necessarily to learn the algorithms you will see in industry.

So we use, say, calculating the Fibonacci numbers as an example of a recursive algorithm to learn the concept of recursion and not so much to learn how to compute the Fibonacci numbers. That's rarely needed in the wild (unless you're doing Project Euler problems). (And implementing Fibonacci via recursion is terrible anyway.)

Upvotes: 5

Related Questions