Hi!
I have 2 implementations of Quicksort algorithm in C# and C++:
#include <ctime>
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;
int read_data ( string filename, unsigned &N, int* &data )
{
FILE *fd;
size_t i;
fd = fopen ( filename.c_str(), "r" );
if ( !fd ) {
cerr << "Couldn't open file " << filename << endl;
}
fscanf ( fd, "%u", &N );
data = new int [ N ];
for ( i = 0; i < N; i++ )
fscanf ( fd, "%d", &data[i] );
fclose (fd);
return 0;
}
void quicksort (int* first, int* last )
{
int *k, *l;
int pivot;
int tmp;
if ( first >= last )
return;
pivot = *first;
k = first + 1;
l = last;
while ( ( *k <= pivot ) && ( k < last ) )
k++;
while ( *l > pivot )
l--;
while ( k < l ) {
//swap ( *k, *l );
tmp = *k;
*k = *l;
*l = tmp;
do k++; while ( *k <= pivot );
do l--; while ( *l > pivot );
}
//swap ( *first, *l );
tmp = *first;
*first = *l;
*l = tmp;
quicksort ( first, l - 1);
quicksort ( l + 1, last );
}
int main ( int argc, char* arv[] )
{
unsigned N;
int* data;
int ret;
clock_t t0, t1;
t0 = clock();
ret = read_data ( "InputData.in", N, data );
if ( ret ) {
return 1;
}
t1 = clock();
cout << "read_data " << (double)(t1 - t0)/CLOCKS_PER_SEC << endl;
t0 = clock();
quicksort ( data, data + N - 1 );
t1 = clock();
cout << "sort " << fixed << setprecision ( 10 ) << (double)(t1 -
t0)/CLOCKS_PER_SEC << endl;
delete[] data;
return 0;
}
using System;
using System.IO;
public class QuicksortSimple {
public static int[] x;
public static void Main ( String[] args ) {
int i;
FileStream fs = new FileStream ( "InputData.in", FileMode.Open,
FileAccess.Read );
StreamReader sr = new StreamReader ( fs );
int N = System.Convert.ToInt32 ( sr.ReadLine() );
Console.WriteLine ( "N = " + N );
x = new int [ N ];
DateTime dt1 = DateTime.Now;
for ( i = 0; i < N; i++ )
x [ i ] = System.Convert.ToInt32 ( sr.ReadLine() );
DateTime dt2 = DateTime.Now;
Console.WriteLine ( "read_data : " + (dt2-dt1).TotalSeconds );
sr.Close();
fs.Close();
dt1 = DateTime.Now;
local_quicksort ( 0, x.Length - 1 );
dt2 = DateTime.Now;
Console.WriteLine ( "sort time : " + (dt2-dt1).TotalSeconds );
}
public static void local_quicksort ( int first, int last ) {
int k, l;
int tmp;
if ( first >= last )
return;
int pivot = x [ first ];
k = 1;
l = last;
while ( x [ k ] <= pivot && k < last )
k++;
while ( x [ l ] > pivot )
l--;
while ( k < l ) {
tmp = x [ l ];
x [ l ] = x [ k ];
x [ k ] = tmp;
do k++;
while ( x [ k ] <= pivot );
do l--;
while ( x [ l ] > pivot );
}
tmp = x [ l ];
x [ l ] = x [ first ];
x [ first ] = tmp;
local_quicksort ( first, l - 1 );
local_quicksort ( l + 1, last );
}
}
<>
<>Running them gives:
[EMAIL PROTECTED] Quicksort]$ ./quicksort2
read_data 0.06
sort 0.0100000000
[EMAIL PROTECTED] Quicksort]$ mono QuicksortSimple.exe
N = 100000
Elapsed time : 20.815316
[EMAIL PROTECTED] Quicksort]$ mono -V
Mono JIT compiler version 1.2.6 (tarball)
Copyright (C) 2002-2007 Novell, Inc and Contributors. www.mono-project.com
TLS: __thread
GC: Included Boehm (with typed GC)
SIGSEGV: normal
Notifications: epoll
Architecture: x86
Disabled: none
Why?
A code to generate an input file for both programs is as following:
using System.IO;
using System;
public class FileWriter {
public static void Main ( String[] args ) {
int N = 100000;
FileStream fs = new FileStream ( "InputData.in", FileMode.Create,
FileAccess.Write );
StreamWriter sw = new StreamWriter ( fs );
Random rand = new Random();
sw.WriteLine ( N );
for ( int i = 0; i < N; i++ )
sw.WriteLine ( rand.Next( 10000 ) );
sw.Close();
fs.Close();
}
<>}
Thanks.
_______________________________________________
Mono-list maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-list
