Algorithm choices - understanding which and why

Question

I am writing a document and was unsure of the following:

1. I am going to compare two algorithms that can perform on the same structure but we cant say one will always be faster than the other (and I will define circumstances in which a is better than b and vice versa); for this I was going to use quicksort and bubblesort. Is this a good choice?

2. Pick 2 algorithms that work on large datasets and define why one is significantly better than the other. For this I was going to use maybe linear search and binary chop search.

What are your opinions on the algorithms I have chosen to explain these points, do they seem appropriate?

Thanks, everyone!

Answer 1

No because quicksort is demonstrably better than a bubble sort in all but a very few set of circumstances involving extremely small datasets.

Quicksort is an O(n log n) algorithm. Bubble sort is an O(n²) algorithm.

Pick one of the other O(n log n) sorts like an merge sort or heap sort.

Or compare bubble sort to a selection sort or insertion sort, both O(n²).

Answer 2

1)

comparing quicksort and bubblesort is probably not a good idea. bubblesort even may not beat quicksort on small cases.

at least try quicksort and insertsort.

I would like to try Prim and Kruskal minimum spanning tree algorithms to show the strength and weakness of the two algorithms on dense and sparse graphs.

2) comparing binary search and linear search is a good example here.

Answer 3

This hugely depends on the exact assignment. Both cases you have presented seem too obvious.

The difference between a linear search and binary search is so large and obvious (on large datasets) that it does not require any discussion at all...unless this is a very basic course.

Answer 4

Study quicksort and bubble sort and find an answer - it might be that one is better than the other under certain circumstances.

Wikipedia has a lot of useful information on sorting algorithms, read and study it carefully.

The most important aspects to compare algorithms on are computational complexity and memory use; see also analysis of algorithms.

Answer 5

The common way to compare algorithms is by using the Big-O-notation (Landau Notation) to describe the limiting behaviour of a function.

Just in (very) brief:

Assume, you have a function that takes n elements (sorting algorithm: the size of your collection). Now we look at the algorithm and try to find out, which is the maximum number of 'steps' (related to n) it needs to terminate.

Some algorithms terminate in constant time (Hashtable read), which is O(1). If you have an algorithm, that has to 'look' at each element once, it is O(n) (linear), if you need to look at it twice, then it's O(2n) (still linear). The link I provided has more examples.

For common algorithms, the O-notations are well known. But it's not too difficult to analyze an existing algorithm. (The real challenge is to invent algorithm for a given problem that are faster then the already known ;))

Answer 6

Hi

Since this must be homework or something very similar I think you would be best advised to choose your own algorithms to compare as you have already. Your marks will depend much more on the quality of your analysis than on your selection of algorithms. There is already some good advice here on how to set about your task, I won't repeat or even add to it further.

Regards

Mark

Answer 7

For (1) I'd suggest a tree map with O(Log N) access to an Hashmap (O(1) access).

The basic "O" seems to clearly favorite hashmap, but then:

• tree is bound by log N, whereas the worst case for Hashmap is O(N) - when everything lands in one bucket
• tree organically grows to fit any number of elements. Hashmap gets inefficient with a bad ratio of nItems / nBuckets, in which case you have to rehash

There are a few other things xyou could figure out... :)