Rosetta Code

Compare sorting algorithms' performance: Difference between revisions

Page Discussion

Compare sorting algorithms' performance (view source)

Revision as of 17:35, 5 April 2013

268 bytes removed ,  11 years ago
Debugged and updated D entry: heapfy is not a heapSort.
No edit summary
(Debugged and updated D entry: heapfy is not a heapSort.)
Line 787:
 
=={{header|D}}==
<lang d>import std.stdio, std.algorithm, std.container, std.datetime,
<lang d>
std.random, std.typetuple;
import std.algorithm;
import std.container;
import std.datetime;
import std.random;
import std.stdio;
 
immutable size_tint[] arrSizeallOnes, =sortedData, 10000randomData;
immutable int[arrSize] allOnes = 1;
immutable int[arrSize] sortedData = genSorted();
static int[arrSize] randomData;
 
static this() { // Initialize global Arrays.
int[arrSize] genSorted()
immutable size_t arraySize = 10_000;
{
int[arrSize] data;
for (int i = 0; i < data.length; i++)
{
data[i] = i+1;
}
return data;
}
 
allOnes = new int[arraySize];
int[arrSize] genRandom()
//allOnes[] = 1;
{
foreach (ref d; allOnes)
int[arrSize] data;
Random gen d = Random(unpredictableSeed)1;
for (int i = 0; i < data.length; i++)
{
data[i] = gen.front;
gen.popFront;
}
return data;
}
 
sortedData = new int[arraySize];
void main()
foreach (immutable i, ref d; sortedData)
{
randomData d = genRandom()i;
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));
 
randomData = new int[arraySize];
writeln("\nTesting against sorted data.");
foreach (ref d; randomData)
r = benchmark!(sortedBubble, sortedInsertion, sortedBuiltIn, sortedHeap)(100);
writefln("Bubble Sort:\t%10d", r[0].to! d = uniform("usecs"0, int).max);
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));
}
 
// BubbleSort:
void bubbleSort(T)(T[] list)
 
{
void bubbleSort(T)(T[] list) {
for (int i = list.length-1; i > 0; i--)
for (int i = list.length - 1; i > 0; i--)
{
for (int j = i -1; j >= 0; j--)
{
if (list[i] < list[j])
{ swap(list[i], list[j]);
T temp = list[j];
list[j] = list[i];
list[i] = temp;
}
}
}
}
 
void allOnesBubble() {
auto data = allOnes.dup;
{
int[] data = allOnes.dupbubbleSort;
bubbleSortassert(data.isSorted);
}
 
void sortedBubble() {
auto data = sortedData.dup;
{
int[] data = sortedData.dupbubbleSort;
bubbleSortassert(data.isSorted);
}
 
void randomBubble() {
auto data = randomData.dup;
{
int[] data = randomData.dupbubbleSort;
bubbleSortassert(data.isSorted);
}
 
// InsertionSort:
unittest
{
int[5] list = [2,5,8,3,1];
bubbleSort(list);
assert(isSorted(list.dup));
}
 
void insertionSort(T)(T[] list) {
foreach (immutable i, currElem; 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] = list[j-1];
}
list[j] = currElem;
}
}
 
void allOnesInsertion() {
auto data = allOnes.dup;
{
int[] data = allOnes.dupinsertionSort;
insertionSortassert(data.isSorted);
}
 
void sortedInsertion() {
auto data = sortedData.dup;
{
int[] data = sortedData.dupinsertionSort;
insertionSortassert(data.isSorted);
}
 
void randomInsertion() {
auto data = randomData.dup;
{
int[] data = randomData.dupinsertionSort;
insertionSortassert(data.isSorted);
}
 
// HeapSort:
unittest
 
{
void heapSort(T)(T[] data) {
int[5] list = [2,5,8,3,1];
auto h = data.heapify;
insertionSort(list);
assertwhile (isSorted(list!h.dup)empty);
h.removeFront;
}
 
void allOnesBuiltInallOnesHeap() {
auto data = allOnes.dup;
{
int[] data = allOnes.dupheapSort;
sort!("a < b")assert(data.isSorted);
}
 
void sortedBuiltInsortedHeap() {
auto data = sortedData.dup;
{
int[] data = sortedData.dupheapSort;
sort!("a < b")assert(data.isSorted);
}
 
void randomBuiltInrandomHeap() {
auto data = randomData.dup;
{
int[] data = randomData.dupheapSort;
sort!("a < b")assert(data.isSorted);
}
 
// Built-in sort:
void allOnesHeap()
 
{
void allOnesBuiltIn() {
int[] data = allOnes.dup;
auto heapdata = BinaryHeap!(int[], "a > b")(data)allOnes.dup;
data.sort!q{a < b};
assert(data.isSorted);
}
 
void sortedHeapsortedBuiltIn() {
auto data = sortedData.dup;
{
int[] data.sort!q{a =< sortedData.dupb};
assert(data.isSorted);
auto heap = BinaryHeap!(int[], "a > b")(data);
}
 
void randomHeaprandomBuiltIn() {
auto data = randomData.dup;
{
int[] data.sort!q{a =< randomData.dupb};
assert(data.isSorted);
auto heap = BinaryHeap!(int[], "a > b")(data);
}
</lang>
 
static void show(in TickDuration[4u] r) {
Timings from my VM with 10,000 elements in each array:
alias args = TypeTuple!("usecs", int);
<pre>
writefln(" Bubble Sort: %10d", r[0].to!args);
Testing against all ones.
writefln(" Insertion Sort: %10d", r[1].to!args);
Bubble Sort: 15746446
Insertion writefln(" Heap Sort: %10d", 6415r[3].to!args);
writefln(" Built-in Sort: %10d", 110079r[2].to!args);
}
Heap Sort: 23997
 
void main() {
enum nRuns = 100;
writeln("Timings in microseconds:");
 
writeln(" Testing against all ones:");
nRuns.benchmark!(allOnesBubble, allOnesInsertion,
allOnesHeap, allOnesBuiltIn).show;
 
writeln("\n Testing against sorted data.");
nRuns.benchmark!(sortedBubble, sortedInsertion,
sortedHeap, sortedBuiltIn).show;
 
writeln("\n Testing against random data.");
nRuns.benchmark!(randomBubble, randomInsertion,
randomHeap, randomBuiltIn).show;
}</lang>
{{out}}
<pre>Timings in microseconds:
Testing against all ones:
Bubble Sort: 7377065
Insertion Sort: 5868
Heap Sort: 25173
Built-in Sort: 34538
 
Testing against sorted data.
Bubble Sort: 14770093 7370520
Insertion Sort: 68896006
Built-in Heap Sort: 55631 18127
Heap Sort: Built-in Sort: 21959176235
 
Testing against random data.
Bubble Sort: 4057552627293705
Insertion Sort: 90220293762374
Built-in Heap Sort: 177563 85053
Heap Sort: Built-in Sort: 48902218268</pre>
(With 10,000 elements in each array. A naive HeapSort seems faster than the built-in sort in all three cases.)
</pre>
 
=={{header|J}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/53701"