Compare sorting algorithms' performance: Difference between revisions

=={{header|D}}==

<lang d>

import std.algorithm;

import std.container;

import std.datetime;

import std.random;

import std.stdio;

immutable size_t arrSize = 10000;

immutable int[arrSize] allOnes = 1;

immutable int[arrSize] sortedData = genSorted();

static int[arrSize] randomData;

int[arrSize] genSorted()

{

int[arrSize] data;

for (int i = 0; i < data.length; i++)

{

data[i] = i+1;

}

return data;

}

int[arrSize] genRandom()

{

int[arrSize] data;

Random gen = Random(unpredictableSeed);

for (int i = 0; i < data.length; i++)

{

data[i] = gen.front;

gen.popFront;

}

return data;

}

void main()

{

randomData = genRandom();

writeln("Testing against all ones.");

auto r = benchmark!(allOnesBubble, allOnesInsertion, allOnesBuiltIn,

allOnesHeap)(100);

writefln("Bubble Sort:\t%10d", r[0].to!("usecs", int));

writefln("Insertion Sort:\t%10d", r[1].to!("usecs", int));

writefln("Built-in Sort:\t%10d", r[2].to!("usecs", int));

writefln("Heap Sort:\t%10d", r[3].to!("usecs", int));

writeln("\nTesting against sorted data.");

r = benchmark!(sortedBubble, sortedInsertion, sortedBuiltIn, sortedHeap)(100);

writefln("Bubble Sort:\t%10d", r[0].to!("usecs", int));

writefln("Insertion Sort:\t%10d", r[1].to!("usecs", int));

writefln("Built-in Sort:\t%10d", r[2].to!("usecs", int));

writefln("Heap Sort:\t%10d", r[3].to!("usecs", int));

writeln("\nTesting against random data.");

r = benchmark!(randomBubble, randomInsertion, randomBuiltIn, randomHeap)(100);

writefln("Bubble Sort:\t%10d", r[0].to!("usecs", int));

writefln("Insertion Sort:\t%10d", r[1].to!("usecs", int));

writefln("Built-in Sort:\t%10d", r[2].to!("usecs", int));

writefln("Heap Sort:\t%10d", r[3].to!("usecs", int));

}

void bubbleSort(T)(T[] list)

{

for (int i = list.length-1; i > 0; i--)

{

for (int j = i -1; j >= 0; j--)

{

if (list[i] < list[j])

{

T temp = list[j];

list[j] = list[i];

list[i] = temp;

}

}

}

}

void allOnesBubble()

{

int[] data = allOnes.dup;

bubbleSort(data);

}

void sortedBubble()

{

int[] data = sortedData.dup;

bubbleSort(data);

}

void randomBubble()

{

int[] data = randomData.dup;

bubbleSort(data);

}

unittest

{

int[5] list = [2,5,8,3,1];

bubbleSort(list);

assert(isSorted(list.dup));

}

void insertionSort(T)(T[] list)

{

foreach (i; 1..list.length)

{

T currElem = list[i];

size_t j = i;

for (; j > 0 && currElem < list[j-1]; j--)

{

list[j] = list[j-1];

}

list[j] = currElem;

}

}

void allOnesInsertion()

{

int[] data = allOnes.dup;

insertionSort(data);

}

void sortedInsertion()

{

int[] data = sortedData.dup;

insertionSort(data);

}

void randomInsertion()

{

int[] data = randomData.dup;

insertionSort(data);

}

unittest

{

int[5] list = [2,5,8,3,1];

insertionSort(list);

assert(isSorted(list.dup));

}

void allOnesBuiltIn()

{

int[] data = allOnes.dup;

sort!("a < b")(data);

}

void sortedBuiltIn()

{

int[] data = sortedData.dup;

sort!("a < b")(data);

}

void randomBuiltIn()

{

int[] data = randomData.dup;

sort!("a < b")(data);

}

void allOnesHeap()

{

int[] data = allOnes.dup;

auto heap = BinaryHeap!(int[], "a > b")(data);

}

void sortedHeap()

{

int[] data = sortedData.dup;

auto heap = BinaryHeap!(int[], "a > b")(data);

}

void randomHeap()

{

int[] data = randomData.dup;

auto heap = BinaryHeap!(int[], "a > b")(data);

}

</lang>

Timings from my VM with 10,000 elements in each array:

<pre>

Testing against all ones.

Bubble Sort: 15746446

Insertion Sort: 6415

Built-in Sort: 110079

Heap Sort: 23997

Testing against sorted data.

Bubble Sort: 14770093

Insertion Sort: 6889

Built-in Sort: 55631

Heap Sort: 21959

Testing against random data.

Bubble Sort: 40575526

Insertion Sort: 9022029

Built-in Sort: 177563

Heap Sort: 48902

</pre>