|This week we were to implement several
different sorting algorithms: Bubble Sort, Selection Sort,
Insertion Sort, Merge Sort, and Quick Sort with three
different pivot strategies: last element, random element,
and median of first, middle, and last elements.
I tested the algorithms with three different arrays each of integers of 10, 100, 1000, 10,000, 100,000, and 1,000,000 elements: random, sorted, and reverse sorted. The following chart shows my results.
With the unsorted arrays, all of the algorithms performed well until around 100,000 elements, when Selection Sort, Insertion Sort, and especially Bubble Sort slowed down drastically.
With the sorted arrays, they all performed well, except Selection Sort slowed way down at 100,000 elements.
With the reverse sorted arrays, Bubble Sort slowed way down at 100,000 along with Selection Sort and Insertion Sort.
Interestingly, Quick Sort with the pivot as the last element started slowing down at 100,000. This implementation also crashed with a StackOverflow exception when using a sorted array. I have no idea why.
NOTE: I have removed the data for QuickSortLast reverse sorted 1,000,000 in order to see the rest of the data better.
Getting more in detail with the four faster algorithms, it is apparent that Quick Sort with the last element pivot is not a very good strategy. As the size increases, it gets much slower.
Choosing a random pivot seems to yield slightly better results than the median-of-three.
Merge Sort appears to be a little slower than Quick Sort once the size gets large, although it does a little better when size is 10,000.