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
11
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.
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)
1