<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
  <title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
&nbsp;&nbsp;<span>
<p align="left"><font face="Arial" size="2">Hi!</font></p>
<p align="left">I have 2 implementations of Quicksort algorithm in C#
and C++:</p>
<p align="left">&nbsp;</p>
<p align="left">
</p>
<div class="codeseg">
<div class="codecontent">
<div class="codesniptitle"><span style="width: 100%;"><br>
</span></div>
<p align="left">#include &lt;ctime&gt;<br>
#include &lt;string&gt;<br>
#include &lt;iostream&gt;<br>
#include &lt;iomanip&gt;<br>
</p>
<p align="left">using namespace std;</p>
<p align="left">int read_data ( string filename, unsigned &amp;N, int*
&amp;data )<br>
{<br>
&nbsp;FILE&nbsp;&nbsp;&nbsp; *fd;<br>
&nbsp;size_t&nbsp; i;</p>
<p align="left">&nbsp;fd = fopen ( filename.c_str(), "r" );<br>
&nbsp;if ( !fd ) {<br>
&nbsp; cerr &lt;&lt; "Couldn't open file " &lt;&lt; filename &lt;&lt; endl;<br>
&nbsp;}</p>
<p align="left">&nbsp;fscanf ( fd, "%u", &amp;N );<br>
&nbsp;data = new int [ N ];</p>
<p align="left">&nbsp;for ( i = 0; i &lt; N; i++ )<br>
&nbsp; fscanf ( fd, "%d", &amp;data[i] );</p>
<p align="left">&nbsp;fclose (fd);</p>
<p align="left">&nbsp;return 0;<br>
}</p>
<p align="left">void quicksort (int* first, int* last )<br>
{<br>
&nbsp;int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *k, *l;<br>
&nbsp;int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; pivot;<br>
&nbsp;int tmp;</p>
<p align="left">&nbsp;if ( first &gt;= last )<br>
&nbsp; return;</p>
<p align="left">&nbsp; pivot&nbsp;&nbsp;&nbsp;&nbsp; = *first;</p>
<p align="left">&nbsp; k&nbsp; = first + 1;<br>
&nbsp; l&nbsp; = last;</p>
<p align="left">&nbsp; while ( ( *k &lt;= pivot ) &amp;&amp; ( k &lt; last )
)<br>
&nbsp;&nbsp; k++;<br>
&nbsp; while ( *l &gt; pivot )<br>
&nbsp;&nbsp; l--;</p>
<p align="left">&nbsp; while ( k &lt; l ) {<br>
&nbsp;&nbsp; //swap ( *k, *l );<br>
&nbsp;&nbsp; tmp = *k;<br>
&nbsp;&nbsp; *k&nbsp; = *l;<br>
&nbsp;&nbsp; *l&nbsp; = tmp;</p>
<p align="left">&nbsp;&nbsp; do k++; while ( *k &lt;= pivot );<br>
&nbsp;&nbsp; do l--; while ( *l &gt; pivot );<br>
&nbsp; }</p>
<p align="left">&nbsp; //swap ( *first, *l );<br>
&nbsp; tmp&nbsp;&nbsp;&nbsp;&nbsp; = *first;<br>
&nbsp; *first&nbsp; = *l;<br>
&nbsp; *l&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = tmp;</p>
<p align="left">&nbsp; quicksort ( first, l - 1);<br>
&nbsp; quicksort ( l + 1, last );</p>
<p align="left">}</p>
<p align="left">int main ( int argc, char* arv[] )<br>
{<br>
&nbsp; unsigned&nbsp;&nbsp; N;<br>
&nbsp; int*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; data;<br>
&nbsp; int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ret;</p>
<p align="left">&nbsp; clock_t&nbsp;&nbsp;&nbsp; t0, t1;</p>
<p align="left">&nbsp; t0 = clock();<br>
&nbsp; ret = read_data ( "InputData.in", N, data );<br>
&nbsp; if ( ret ) {<br>
&nbsp;&nbsp; return 1;<br>
&nbsp; }<br>
&nbsp; t1 = clock();<br>
&nbsp; cout &lt;&lt; "read_data " &lt;&lt; (double)(t1 - t0)/CLOCKS_PER_SEC
&lt;&lt; endl;</p>
<p align="left">&nbsp; t0 = clock();<br>
&nbsp; quicksort ( data, data + N - 1 );<br>
&nbsp; t1 = clock();<br>
&nbsp; cout &lt;&lt; "sort " &lt;&lt; fixed &lt;&lt; setprecision ( 10 )
&lt;&lt; (double)(t1 - t0)/CLOCKS_PER_SEC &lt;&lt; endl;</p>
<p align="left">&nbsp; delete[] data;</p>
<p align="left">&nbsp; return 0;</p>
<p align="left">}</p>
</div>
</div>
<p align="left">
</p>
<div class="codeseg">
<div class="codecontent">
<div class="codesniptitle"><span style="width: 100%;"><br>
</span></div>
<p align="left">using System;<br>
using System.IO;</p>
<p align="left">public class QuicksortSimple&nbsp; {</p>
<p align="left">&nbsp;public static int[]&nbsp;&nbsp;&nbsp; x;</p>
<p align="left">&nbsp;public static void Main ( String[] args )&nbsp;&nbsp; {</p>
<p align="left">&nbsp; int i;</p>
<p align="left">&nbsp; FileStream&nbsp;&nbsp; fs = new FileStream ( "InputData.in",
FileMode.Open, FileAccess.Read );<br>
&nbsp; StreamReader sr = new StreamReader ( fs );</p>
<p align="left">&nbsp; int&nbsp;&nbsp; N = System.Convert.ToInt32 ( sr.ReadLine() );<br>
&nbsp; Console.WriteLine ( "N = " + N );</p>
<p align="left">&nbsp; x = new int [ N ];</p>
<p align="left">&nbsp; DateTime&nbsp; dt1 = DateTime.Now;</p>
<p align="left">&nbsp; for ( i = 0; i &lt; N; i++ )<br>
&nbsp;&nbsp; x [ i ] = System.Convert.ToInt32 ( sr.ReadLine() );</p>
<p align="left">&nbsp; DateTime&nbsp; dt2 = DateTime.Now;<br>
&nbsp; Console.WriteLine ( "read_data : " + (dt2-dt1).TotalSeconds );<br>
&nbsp; sr.Close();<br>
&nbsp; fs.Close();</p>
<p align="left">&nbsp; dt1 = DateTime.Now;</p>
<p align="left">&nbsp; local_quicksort ( 0, x.Length - 1 );</p>
<p align="left">&nbsp; dt2 = DateTime.Now;</p>
<p align="left">&nbsp; Console.WriteLine ( "sort time : " +
(dt2-dt1).TotalSeconds );</p>
<p align="left">&nbsp;}</p>
<p align="left">&nbsp;public static void local_quicksort ( int first, int
last ) {</p>
<p align="left">&nbsp; int&nbsp;&nbsp; k, l;<br>
&nbsp; int&nbsp;&nbsp; tmp;</p>
<p align="left">&nbsp; if ( first &gt;= last )<br>
&nbsp;&nbsp; return;</p>
<p align="left">&nbsp; int&nbsp; pivot = x [ first ];</p>
<p align="left">&nbsp; k&nbsp;&nbsp;&nbsp;&nbsp; = 1;<br>
&nbsp; l&nbsp;&nbsp;&nbsp;&nbsp; = last;</p>
<p align="left">&nbsp; while ( x [ k ] &lt;= pivot &amp;&amp; k &lt; last )<br>
&nbsp;&nbsp; k++;<br>
&nbsp; while ( x [ l ] &gt; pivot )<br>
&nbsp;&nbsp; l--;</p>
<p align="left">&nbsp; while ( k &lt; l ) {</p>
<p align="left">&nbsp;&nbsp; tmp&nbsp;&nbsp;&nbsp;&nbsp; = x [ l ];<br>
&nbsp;&nbsp; x [ l ] = x [ k ];<br>
&nbsp;&nbsp; x [ k ] = tmp;</p>
<p align="left">&nbsp;&nbsp; do k++;<br>
&nbsp;&nbsp;&nbsp; while ( x [ k ] &lt;= pivot );<br>
&nbsp;&nbsp; do l--;<br>
&nbsp;&nbsp;&nbsp; while ( x [ l ] &gt; pivot );</p>
<p align="left">&nbsp; }</p>
<p align="left">&nbsp; tmp&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = x [ l ];<br>
&nbsp; x [ l ]&nbsp;&nbsp;&nbsp;&nbsp; = x [ first ];<br>
&nbsp; x [ first ] = tmp;</p>
<p align="left">&nbsp; local_quicksort ( first, l - 1 );<br>
&nbsp; local_quicksort ( l + 1, last&nbsp;&nbsp; );</p>
<p align="left">&nbsp;}</p>
<p align="left">}</p>
&nbsp;&nbsp;
<><br>
</></div>
</div>
<>Running them gives:<br>
<br>
[serdyuk@skif Quicksort]$ ./quicksort2<br>
read_data 0.06<br>
sort 0.0100000000<br>
<br>
[serdyuk@skif Quicksort]$ mono QuicksortSimple.exe<br>
N = 100000<br>
Elapsed time : 20.815316<br>
<br>
[serdyuk@skif Quicksort]$ mono -V<br>
Mono JIT compiler version 1.2.6 (tarball)<br>
Copyright (C) 2002-2007 Novell, Inc and Contributors.
<a class="moz-txt-link-abbreviated" href="http://www.mono-project.com">www.mono-project.com</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; TLS:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; __thread<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; GC:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Included Boehm (with typed GC)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; SIGSEGV:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; normal<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Notifications: epoll<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Architecture:&nbsp; x86<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Disabled:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; none&nbsp;</> <br>
<p>&nbsp;</p>
<p align="left">Why?</p>
<br>
<p align="left">A code to generate an input file for both programs is
as following:</p>
<div class="codeseg">
<div class="codecontent">
<p align="left">using System.IO;</p>
using System;<br>
<p align="left">public class FileWriter {</p>
<p align="left">&nbsp;public static void Main ( String[] args )&nbsp;&nbsp; {</p>
<p align="left">&nbsp; int&nbsp;&nbsp;&nbsp; N = 100000;<br>
&nbsp;&nbsp;</p>
<p align="left">&nbsp; FileStream&nbsp;&nbsp; fs = new FileStream ( "InputData.in",
FileMode.Create, FileAccess.Write );</p>
<p align="left">&nbsp; StreamWriter sw = new StreamWriter ( fs );</p>
<p align="left">&nbsp; Random&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; rand = new Random();</p>
<p align="left">&nbsp; sw.WriteLine ( N );</p>
<p align="left">&nbsp; for ( int i = 0; i &lt; N; i++ )<br>
&nbsp;&nbsp; sw.WriteLine ( rand.Next( 10000 ) );</p>
<p align="left">&nbsp; sw.Close();<br>
&nbsp; fs.Close();</p>
<p align="left">&nbsp;}</p>
<>} <br>
</></div>
</div>
<p align="left">&nbsp;</p>
<p align="left">Thanks.</p>
</span>
</body>
</html>