32 lines
1.5 KiB
Plaintext
32 lines
1.5 KiB
Plaintext
{{Sorting Algorithm}}
|
|
|
|
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 ([[#Figures: log2( time in microseconds ) vs. log2( sequence length )|example figures]]).
|
|
|
|
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}
|
|
:* shuffled range: sequence with elements randomly distributed. Example: {5, 3, 9, 6, 8}
|
|
|
|
|
|
Consider at least two different sorting functions (different algorithms or/and different implementation of the same algorithm).
|
|
|
|
For example, consider [[Bubble Sort]], [[Insertion sort]], [[Quicksort]] or/and implementations of Quicksort with different pivot selection mechanisms. Where possible, use existing implementations.
|
|
|
|
Preliminary subtask:
|
|
:* [[Bubble Sort]], [[Insertion sort]], [[Quicksort]], [[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?
|
|
<br><br>
|
|
|