1

I need to write different sort algorithms such as

  • bubbleSort

  • insertionSort

  • selectionSort

  • quickSort

  • mergeSort

And measure how many average comparison does each one for N number (averaging between N! tests). But I need some final results to compare my program results.

Is there any table giving the average of comparisons of these algorithms for a few N numbers?

This is what I have got for average of array length 10:

    Selection sort: 63
    Bubble sort: 49.4144
    Insertion sort: 31.5
    Merge sort: 31.6667
    Quick sort: 30.7706
  • 3
    Have you tried writing them and logging calls to compare()? You may find that things like sorting already sorted data for bubble sort vs quicksort may have surprising values if you just go for pre-printed table. – user40980 Apr 23 '15 at 22:25
  • @MichaelT updated – zahmati Apr 23 '15 at 22:30
  • You can easily google the average time complexity of all of these algorithms. O(n^2) may not be a hard number, but if you test at multiple input sizes (the one test you posted is meaningless by itself) it should be fairly obvious whether your results are following an n^2-like curve or an n-like curve or a log(n)-like curve. – Ixrec Apr 23 '15 at 22:30
  • @Ixrec i dont want their ratio. I want their exact number. The ration does not distinguish a wrong coefficient. What if I do the comparison counting two times more as much I had to do? – zahmati Apr 23 '15 at 22:37
  • 1
    Your question has more value than others give you credit for. Most comparisons of sort algorithms assume that you want to know what is best for large numbers of items, but there are applications where the number of items is relatively small but each comparison is very expensive. In these cases it can be very important to have an algorithm with the least comparisons even for small input sets. I voted your question up for that reason. – Harvey Mar 7 '16 at 5:06
0

Is there any table giving the average of comparisons of these algorithms for a few N numbers

The exact number of comparisons needed may depend on the specific implementation of the algorithm, not on the algorithm itself, and so will the average number. So even if you find something like what you requested, I find it very unlikely that you can compare it directly to your implementation of the algorithms.

3

One great resource: http://bigocheatsheet.com/

I can tell you right off the bat that:

  • Bubble Sort is in worst case, O(N2)
  • Insertion Sort is in worst case, O(N2)
  • Selection Sort is in worst case, O(N2)
  • Quick Sort is in worst case, O(N2), yet is typically O(n log n)
  • Merge Sort is in worst case, O(n log n)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.