/sorting-networks-test

Three implementations of quicksort, one of them using sorting networks for testing.

Primary LanguageC

This repository contains three implementations of the Quick Sort algorithm,
meant to be compared for their running speeds on various input sizes and types.

The first implementation, in textbook.c, is the simplest and most commonly found
on textbooks.

The second, in insertion.c, uses insertion sort for small arrays.

The third, in network.c, uses sorting networks for small arrays.

All three implementations are designed to sort integers and use the same
simple partitioning algorithm, which can be found in partition.c.

In order to run the tests, just compile:

$ make

And then run the desired test specifying type and size of input:

$ ./network a 1024

The available types of input are:
(a)scending - an already sorted array of integers;
(d)escending - an array of integers sorted in reverse;
(e)quals - an array of zeroes;
(r)andom - an array of random integers.

The results/ directory contains the raw data for my test results.

Its two subdirectories correspond to the compiler optimization flags used for
the code on each run, -O1 and -O2.

Inside each of these you will find several files, each of the form

<sorting-method>.<input-size>.<input-type>

containing the times for the five runs I averaged in my tests.

For more information, please see:
http://guilherme-pg.com/2011/09/02/Fun-with-sorting-networks.html
http://guilherme-pg.com/2012/03/27/Sorting-networks-revisited.html