Compare sorting algorithms' performance
Compare sorting algorithms' performance
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
Measure a relative performance of sorting algorithms implementations.
Plot execution time vs. input sequence length dependencies for various implementation of sorting algorithm and different input sequence types.
Consider three type of input sequences:
- ones: sequence of all 1's. Example: {1, 1, 1, 1, 1}
- range: ascending sequence, i.e. already sorted. Example: {1, 2, 3, 10, 15}
- shuffledrange: sequence with elements randomly distributed. Example: {5, 3, 9, 6, 8}
Consider at least two different sorting function (different algorithms or/and different implementation of the same algorithm). For example, consider Bubble Sort, Insertion Sort, Quick Sort or/and implementations of Quick Sort with different pivot selection mechanisms. Where possible, use existing implementations.
Preliminary subtask:
- Bubble Sort, Insertion Sort, Quick Sort, Radix Sort, Shell Sort
- Query Performance
- Write float arrays to a text file
- Plot x, y arrays
- Polynomial Fitting
General steps:
- Define sorting routines to be considered.
- Define appropriate sequence generators and write timings.
- Plot timings.
- What conclusions about relative performance of the sorting routines could be made based on the plots?