Anonymous user
Compare sorting algorithms' performance: Difference between revisions
Compare sorting algorithms' performance (view source)
Revision as of 13:31, 5 April 2013
, 11 years agono edit summary
No edit summary |
|||
Line 784:
* [http://i43.tinypic.com/2nqrzfs.png reversed range]
* [http://i41.tinypic.com/24q8hmg.png shuffled range]
=={{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>
=={{header|J}}==
| |||