mgs
/
median-comparison
2
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
40 Commits
1 Branch
0 Tags
9.8 MiB
 
 
 
Branch: main
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'main'
${ noResults }
 ZIP  TAR.GZ
karl 4d752627f2
Add complexity text to README 		3 years ago
.gitignore ignore specific vs build files 3 years ago
LICENSE Initial commit 3 years ago
Makefile Set O3 optimization flag 3 years ago
MedianOfMedians.h removed some comments and newlines 3 years ago
MedianQuicksort.h moved partition function into common; combined partition magic and fixed randomizedSelect for HoarePartitioning 3 years ago
README.md Add complexity text to README 3 years ago
RandomizedSelect.h moved partition function into common; combined partition magic and fixed randomizedSelect for HoarePartitioning 3 years ago
Timing.cpp removed test code 3 years ago
Timing.h basic project setup 3 years ago
Wirth.h using custom swap instead of std::swap 3 years ago
common.h moved partition function into common; combined partition magic and fixed randomizedSelect for HoarePartitioning 3 years ago
fileHandler.h beautify output 3 years ago
generate_testfiles.py Generate even number of test numbers 3 years ago
main.cpp Separate approx. MoM and exact with quickselect 3 years ago
testdata Generate even number of test numbers 3 years ago

README.md

median-comparison

Building

Run make in the project root directory.

Usage

First, generate test data:

python3 generate_testfiles.py

(The amount of numbers to generate can be modified in that script.)

Then, run the program:

./mc

Example output is shown below.

Example Output

calculating median on index 499999 of 999999 elems...
quicksort median                                2149523045
array quicksort                                 2149523045
array std sort                                  2149523045
randomized select                               2149523045
vector median of medians only (approximative)   2149866506
vector median of medians + quickselect (exact)  2149523045
wirth kth element                               2149523045
nth element                                     2149523045
--------------------
Results: 
--------------------
array quicksort                                 :   112.1097ms
array std sort                                  :    59.8321ms
init                                            :    67.5942ms
nth element                                     :     5.7105ms
quicksort median                                :    76.1378ms
randomized select                               :     8.8619ms
vector median of medians + quickselect (exact)  :    22.3934ms
vector median of medians only (approximative)   :    11.3237ms
wirth kth element                               :     8.5368ms
--------------------

Complexity

The algorithms which fully sort the array (quicksort median, array quicksort, array std sort) have an average complexity of O(N logN). All 'proper' median algorithms (randomized select, vector median of medians, wirth kth element, nth element) have an average complexity of O(N). The difference is well visible in the results above.