2

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
Improve this question
11
  • 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, 2015 at 22:25
  • 1
    @MichaelT updated
    – zahmati
    Apr 23, 2015 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, 2015 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, 2015 at 22:37
  • 2
    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, 2016 at 5:06

2 Answers 2

Reset to default
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.

Improve this answer
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)
Improve this answer
1
  • The OP is looking for a table of numbers so that he can verify his results. All your formulas are off by a constant factor and useless for his application.
    – Navin
    Sep 2, 2021 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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