Java vs. C#
-
Original erstellt von thomas80d:
Nimm mal den modifizierten Code.OK! ...hat kompiliert und wirft keine Exception. Scheint aber trotzdem wieder länger zu dauern. Ich lass das mal so nebenher laufen und warte, ob es irgendwann ein Ergebnis gibt.
-
Ich habe jetzt mal die Ausgabe vorgezogen. Sie erfolgt jetzt vorerst direkt nach den einzelnen Schritten. Anscheinend ist die Erzeugung des langen Strings (bzw. das aneinanderhängen) tatsächlich das Problem. Trotzdem schonmal die ersten Ergebnisse (ich hatte aber einiges nebenher laufen, so dass die Werte wohl noch ein bischen besser aussehen müßten) :
Array erzeugen : 0 ms
Dazu ist allerdings zu sagen, dass bei Java (bei C# weiß ich das nicht) nach dem Erzeugen des Arrays jedes Element des Arrays auf einen Standardwert gesetzt wird. Das wird bei C++ meines Wissens nach nicht gemacht. ...ist aber natürlich auch nicht immer nötig.
Zufallszahlen : 901 ms
Sortieren : 311 ms
-
Warum hört keiner auf mich?
Das Zahlen in Strings umwandeln wird mit sprintf und stringstreams gleichlahm sein, da jedesmal eine komplette Kopie erzeugt wird. und Das kopieren muss pro Zusätzliche Zahl einmal mit allen Zahlen gemacht werden. Das dauert, wie ihr seht Jahre. Verwendet mal deque<char> für strings oder meinet wegen auch list<char>. das umwandeln ansich kann ja mit stringstreams oder sprintf gemacht werden.
Und beim sortieren bitte std::sort aus <algorithm> nehmen. Das ist um einiges schneller, als qsort, da der Aufruf von less geinlinet werden kann.
Wenn wir schon vergleichen, dann auch richtig. Wenn kingruedi das nicht hinbekommt, werde ich mich mal bemühen. Aber ich denke, dass er das schaffen sollte.
-
@Helium
ich will auch noch eine Version, die stärker die STL nutzt und eine möglichst effiziente schreiben, ich wollte nur testen, ob das schneller ist sich stärker auf die alten C Dinge zu verlassen
-
Ich werde jetzt weitere Zeiten der momentanen C++-Version nicht angeben. ...wir wissen ja, was lahm ist und es bringt uns wenig zu wissen, ob jetzt die 1000fache odre die 2000fache Zeit benötigt wird. Ich bin zumindest mal gespannt, ob das in der nächsten Version vernünftig beschleunigt werden kann. Ich habe jetzt übrigens auch eine Java-Version des Programms, in der ich diesen riesigen String "per Hand" als Byte-Array erstelle. ...das ist nochmal etwas schneller. Ich bin mal gespannt, wie schnell ihr an die Zeit rankommt, ich kann mir zumindest nicht vorstellen, dass ihr das nicht schafft. Ihr könnt euch ja auch eine eigene Methode schreiben.
-
Ich hab mal die C++-Version abgeändert auf stringstreams. Ist jetzt bedeutend schneller.
#include <iostream> #include <cmath> #include <limits> #include <fstream> #include <sstream> #include <algorithm> #include <functional> using namespace std; #include <windows.h> #ifdef _MSC_VER #undef max #endif int main() { DWORD times[7]; const size_t arrayLength=5000000; size_t i=0; //Arrays erzeugen times[0] = GetTickCount(); int *intArray=new int[arrayLength]; double *doubleArray=new double[arrayLength]; times[1] = GetTickCount(); //Zufallszahlen srand(unsigned int(0)); for(;i<arrayLength;++i) { intArray[i]=static_cast<int>(numeric_limits<int>::max()*rand()/RAND_MAX+1.0); doubleArray[i]=(numeric_limits<double>::max()*rand()/RAND_MAX+1.0); } times[2] = GetTickCount(); //Sortieren sort(&intArray[0], &intArray[arrayLength-1], less<int>()); times[3] = GetTickCount(); //int to char ostringstream stringBuffer(); for(i=0;i<arrayLength;++i) { stringBuffer << intArray[i] << endl; } times[4] = GetTickCount(); //string in Datei schreiben ofstream out("demo.txt"); if(!out.is_open()) { cerr << "Fehler" << endl; return 1; } out << stringBuffer.str(); out.close(); times[5] = GetTickCount(); //Wurzeln berechnen for(i=0;i<arrayLength;++i) doubleArray[i]=sqrt(doubleArray[i]); times[6] = GetTickCount(); //Ausgabe: cout << "Array erzeugen: " << times[1] - times[0] << "ms" << endl; cout << "Zufallszahlen erzeugen: " << times[2] - times[1] << "ms" << endl; cout << "Sortieren: " << times[3] - times[2] << "ms" << endl; cout << "String anhängen: " << times[4] - times[3] << "ms" << endl; cout << "Speichern: " << times[5] - times[4] << "ms" << endl; cout << "Wurzeln berechnen: " << times[6] - times[5] << "ms" << endl; delete[] intArray; delete[] doubleArray; }[ Dieser Beitrag wurde am 10.10.2002 um 08:52 Uhr von thomas80d editiert. ]
-
Mein Compiler meckert mal wieder überall dran rum.
Benchmark.cpp:28: parse error before 'int'
Benchmark.cpp:41: invalid conversion from 'unsigned int' to 'std::_Ios_Openmode'
Benchmark.cpp:41: initializing argument 1 of 'std::basic_ostringstream<_CharT, _Traits, _Alloc>::basic_ostringstream(std::_Ios_Openmode) [with _CharT = char, _Traits = std::char_traits<char>, _Alloc = std::allocator<char>]'...ich weiß natürlich nicht, was diese Fehler bedeuten.
[ Dieser Beitrag wurde am 09.10.2002 um 23:41 Uhr von Gregor editiert. ]
-
ich war gestern leider krank, will aber noch meine Version mit vectoren posten, da man dann auch sort verwenden kann.
-
Immer her mit anderen Versionen. Bin mal gespannt, wann jemand eine bringt, die mein Compiler tatsächlich akzeptiert.
BTW : @Thomas : Nach der Veränderung sind die beiden Fehler in Zeile 41 weg. Dafür sind zwei neue Fehler in den Zeilen 44 und 55 entstanden. ...wenn das bei dir kompiliert, dann kannst du mir ja einfach wieder eine ausführbare Datei schicken!
-
... wie schön dass man C++-Programme schreiben kann die dann auf allen(! *rofl*) Maschinen und Compilern lauffähig bzw. Kompilierbar sind ...
SCNR
-
probierts mal folgendes:
#include <iostream> /* std::cout std::endl */ #include <cmath> /* sqrt() */ #include <ctime> /* time_t difftime() */ #include <fstream> /* std::ofstream */ #include <algorithm> #include <functional> #include <limits> #include <sstream> /* std::ostringstream */ // using namespace std; #ifdef WIN32 #include <windows.h> #ifdef _MSC_VER #undef max #endif #else #include <sys/time.h> #endif int main() { #ifdef WIN32 DWORD times[7]; #else struct timeval times[7]; struct timezone tz; #endif const size_t arrayLength=5000000; size_t i=0; //Arrays erzeugen #ifdef WIN32 times[0] = GetTickCount(); #else gettimeofday(×[0], &tz); #endif int *intArray=new int[arrayLength]; double *doubleArray=new double[arrayLength]; #ifdef WIN32 times[1] = GetTickCount(); #else gettimeofday(×[1], &tz); #endif //Zufallszahlen srand( (unsigned int)0 ); for(;i<arrayLength;++i) { intArray[i] = static_cast<int>(std::numeric_limits<int>::max() * rand() / RAND_MAX + 1.0); doubleArray[i] = (std::numeric_limits<double>::max() * rand() / RAND_MAX + 1.0); } #ifdef WIN32 times[2] = GetTickCount(); #else gettimeofday(×[2], &tz); #endif //Sortieren sort(&intArray[0], &intArray[arrayLength-1], std::less<int>()); #ifdef WIN32 times[3] = GetTickCount(); #else gettimeofday(×[3], &tz); #endif //int to char std::ostringstream stringBuffer; for(i=0;i<arrayLength;++i) { stringBuffer << intArray[i] << std::endl; } #ifdef WIN32 times[4] = GetTickCount(); #else gettimeofday(×[4], &tz); #endif //string in Datei schreiben std::ofstream out("demo.txt"); if(!out.is_open()) { std::cerr << "Fehler" << std::endl; delete[] intArray; delete[] doubleArray; return 1; } out << stringBuffer.str(); out.close(); #ifdef WIN32 times[5] = GetTickCount(); #else gettimeofday(×[5], &tz); #endif //Wurzeln berechnen for(i=0; i<arrayLength; ++i) { doubleArray[i] = sqrt(doubleArray[i]); } // for_each(doubleArray[0], doubleArray[arrayLength - 1], sqrt); #ifdef WIN32 times[6] = GetTickCount(); #else gettimeofday(×[6], &tz); #endif //Ausgabe: #ifdef WIN32 std::cout << "Array erzeugen: " << (times[1] - times[0]) << std::endl; std::cout << "Zufallszahlen erzeugen: " << (times[2] - times[1]) << std::endl; std::cout << "Sortieren: " << (times[3] - times[2]) << std::endl; std::cout << "String anhaengen: " << (times[4] - times[3]) << std::endl; std::cout << "Speichern: " << (times[5] - times[4]) << std::endl; std::cout << "Wurzeln berechnen: " << (times[6] - times[5]) << std::endl; #else std::cout << "Array erzeugen: " << (times[1].tv_usec - times[0].tv_usec) << std::endl; std::cout << "Zufallszahlen erzeugen: " << (times[2].tv_usec - times[1].tv_usec) << std::endl; std::cout << "Sortieren: " << (times[3].tv_usec - times[2].tv_usec) << std::endl; std::cout << "String anhaengen: " << (times[4].tv_usec - times[3].tv_usec) << std::endl; std::cout << "Speichern: " << (times[5].tv_usec - times[4].tv_usec) << std::endl; std::cout << "Wurzeln berechnen: " << (times[6].tv_usec - times[5].tv_usec) << std::endl; #endif delete[] intArray; delete[] doubleArray; return 0; }
-
Gratuliere! Der Code kompiliert bei mir. Es sollte aber noch schneller gehen. ...das Sort von der letzten Version ist z.B. deutlich schneller. Hier die Ergebnisse :
1,2 GHz 1,6 GHz Array : 0 0 Zufallszahlen : 1241 921 sortieren : 2654 2003 String erzeugen : 107054 79053 Speichern : 10495 4327 Wurzel berechnen : 912 631Ich habe meinen PC aber nicht dafür neu gestartet. Kann also sein, dass man durchaus noch etwas bessere Ergebnisse erreichen könnte. ...könnte auch sein, dass bessere Ergebnisse rauskommen, wenn mir noch jemand verrät, wie man g++ dazu bringen kann, besser zu optimieren. (falls man das kann)
-
BTW : Die erzeugte Textdatei ist interessant. Sie ist nur 24MB groß und es sind nur die Zahlen 1, 65538 und 65539 enthalten. Die letzte Zahl ist eine 65538. Es stellen sich also folgende Fragen :
1. Warum wird nicht richtig sortiert?
2. Warum werden nur diese 3 Zahlen erzeugt?[ Dieser Beitrag wurde am 11.10.2002 um 02:28 Uhr von Gregor editiert. ]
-
nochmal BTW : Ich habe gerade gesehen, dass das Programm mit diesen "x" kompiliert wurde. Interessant, dass das geht!
[ Dieser Beitrag wurde am 11.10.2002 um 03:47 Uhr von Gregor editiert. ]
-
Original erstellt von Gregor:
**nochmal BTW : Ich habe gerade gesehen, dass das Programm mit diesen "x" kompiliert wurde. Interessant, dass das geht! [ Dieser Beitrag wurde am 11.10.2002 um 03:47 Uhr von [qb]Gregor** editiert. ][/QB]
Na, das ist so nicht ganz richtig. Da du ja Windows verwendet und der Code mit dem "x" in dem Nicht-Windows Teil steht, wird das gar nicht mitkompiliert.
-
Versuch mal beim g++ folgende Optionen
g++ -O3 -Wall -W -fomit-frame-pointer -fschedule-insns2 -malign-double -pipe -march=athlon -mcpu=athlon -o code code.cc
athlon musst du durch den CPU Typ ersetzen, den du benutzt. Es kann sein, dass die Optionen -fschedule-insns2 -malign-double Probleme bereiten.
So ich schreib mal den Code mit den vectoren auf Descartes Code um
BTW.
Das mit dem x aus × muss ich mal Loggy melden
-
#include <iostream> /* std::cout std::endl */ #include <cmath> /* sqrt() */ #include <ctime> /* time_t difftime() */ #include <fstream> /* std::ofstream */ #include <algorithm> #include <functional> #include <limits> #include <sstream> /* std::ostringstream */ #ifndef NO_VECTOR #include <vector> #endif // using namespace std; #ifdef WIN32 #include <windows.h> #ifdef _MSC_VER #undef max #endif #else #include <sys/time.h> #endif int main() { #ifdef WIN32 DWORD times[7]; #else struct timeval times[7]; struct timezone tz; #endif const size_t arrayLength=5000000; size_t i=0; //Arrays erzeugen #ifdef WIN32 times[0] = GetTickCount(); #else gettimeofday(×[0], &tz); #endif #ifdef NO_VECTOR int *intArray=new int[arrayLength]; double *doubleArray=new double[arrayLength]; #else std::vector<int> intArray(arrayLength); std::vector<double> doubleArray(arrayLength); #endif #ifdef WIN32 times[1] = GetTickCount(); #else gettimeofday(×[1], &tz); #endif //Zufallszahlen std::srand( (unsigned int)0 ); for(;i<arrayLength;++i) { #ifdef NO_VECTOR intArray[i] = static_cast<int>(std::numeric_limits<int>::max() * rand() / RAND_MAX + 1.0); doubleArray[i] = (std::numeric_limits<double>::max() * rand() / RAND_MAX + 1.0); #else intArray.push_back(static_cast<int>(std::numeric_limits<int>::max() * std::rand() / RAND_MAX + 1.0)); doubleArray.push_back(std::numeric_limits<double>::max() * std::rand() / RAND_MAX + 1.0); #endif } #ifdef WIN32 times[2] = GetTickCount(); #else gettimeofday(×[2], &tz); #endif //Sortieren #ifdef NO_VECTOR sort(&intArray[0], &intArray[arrayLength-1], std::less<int>()); #else sort(intArray.begin(), intArray.end(), std::less<int>()); #endif #ifdef WIN32 times[3] = GetTickCount(); #else gettimeofday(×[3], &tz); #endif //int to char std::ostringstream stringBuffer; for(i=0;i<arrayLength;++i) { stringBuffer << intArray[i] << std::endl; } #ifdef WIN32 times[4] = GetTickCount(); #else gettimeofday(×[4], &tz); #endif //string in Datei schreiben std::ofstream out("demo.txt"); if(!out.is_open()) { std::cerr << "Fehler" << std::endl; #ifdef NO_VECTOR delete[] intArray; delete[] doubleArray; #endif return 1; } out << stringBuffer.str(); out.close(); #ifdef WIN32 times[5] = GetTickCount(); #else gettimeofday(×[5], &tz); #endif //Wurzeln berechnen for(i=0; i<arrayLength; ++i) { doubleArray.push_back(std::sqrt(doubleArray[i])); } // for_each(doubleArray[0], doubleArray[arrayLength - 1], sqrt); #ifdef WIN32 times[6] = GetTickCount(); #else gettimeofday(×[6], &tz); #endif //Ausgabe: #ifdef WIN32 std::cout << "Array erzeugen: " << (times[1] - times[0]) << std::endl; std::cout << "Zufallszahlen erzeugen: " << (times[2] - times[1]) << std::endl; std::cout << "Sortieren: " << (times[3] - times[2]) << std::endl; std::cout << "String anhaengen: " << (times[4] - times[3]) << std::endl; std::cout << "Speichern: " << (times[5] - times[4]) << std::endl; std::cout << "Wurzeln berechnen: " << (times[6] - times[5]) << std::endl; #else std::cout << "Array erzeugen: " << (times[1].tv_usec - times[0].tv_usec) << std::endl; std::cout << "Zufallszahlen erzeugen: " << (times[2].tv_usec - times[1].tv_usec) << std::endl; std::cout << "Sortieren: " << (times[3].tv_usec - times[2].tv_usec) << std::endl; std::cout << "String anhaengen: " << (times[4].tv_usec - times[3].tv_usec) << std::endl; std::cout << "Speichern: " << (times[5].tv_usec - times[4].tv_usec) << std::endl; std::cout << "Wurzeln berechnen: " << (times[6].tv_usec - times[5].tv_usec) << std::endl; #endif #ifdef NO_VECTOR delete[] intArray; delete[] doubleArray; #endif return 0; }
-
<Descartes> Code mit den genannten Compiler-Optionen :
1,2 GHz 1,6 GHz Array : 0 0 Zufallszahlen : 1132 842 sortieren : 470 400 String erzeugen : 105052 78092 Speichern : 10254 4316 Wurzel berechnen : 221 160Sieht schon deutlich besser aus.
-
Kingruedis Code mit den genannten Compiler-Optionen :
1,2 GHz 1,6 GHz Array : 130 120 Zufallszahlen : 1502 1162 sortieren : 1412 1101 String erzeugen : 103999 76490 Speichern : 5158 3165 Wurzel berechnen : 561 460...bei mir schwanken die Ergebnisse übrigens von mal zu mal recht stark. Wenn mir etwas komisch vorkommt, dann mache ich die Messung immer nochmal. Hier war z.B. das "Wurzel berechnen" bei einer Mesung sehr langsam (4026).
Ich zeige gleich mal meine Java-Version, bei der ich die Stringerzeugung per Hand mache. Vielleicht hilft die Version, das in C++ effizienter zu implementieren.
EDIT : Die txt-Datei hat hier übrigens nur 15MB!
[ Dieser Beitrag wurde am 11.10.2002 um 14:00 Uhr von Gregor editiert. ]
-
2. Java-Variante (per Hand String + Sortieren)
1,2 GHz 1,6 GHz Array : 190 181 Zufallszahlen : 4677 3495 sortieren : 2683 2013 String erzeugen : 2784 2093 Speichern : 2844 2844 Wurzel berechnen : 181 130Komischerweise wirken sich die MHz hier garnicht auf die Geschwindigkeit des Speicherns aus.
der Code :
[java]
import java.util.;
import java.io.;public class Benchmark2
{
public Benchmark2 ()
{
}private final static byte [] digits = {'0','1','2','3','4','5','6','7','8','9'};
private final static byte [] DigitTens = {
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
'2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
'3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
'4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
'5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
'6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
'7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
'8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
'9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
} ;private final static byte [] DigitOnes = {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
} ;public static void main (String[] args)
{
long [] times = new long [7];
int i;
int arrayLength = 5000000;
times [0] = System.currentTimeMillis ();
// Array erzeugen
int [] array = new int [arrayLength];
double [] doubleArray = new double [arrayLength];
times [1] = System.currentTimeMillis ();
// Zufallszahlen erzeugen
Random rand = new Random();
for (i = 0 ; i < arrayLength ; ++i)
{
array[i] = rand.nextInt ();
doubleArray[i] = rand.nextDouble ();
}
times [2] = System.currentTimeMillis ();
// Array sortieren
sort (array);
times [3] = System.currentTimeMillis ();
// Zahlen des Arrays in einen großen String verwandeln (jede Zeile eine Zahl)
byte [] byteArray = new byte [arrayLength * 12];
int pos = 0;
int currentStringPos;
byte [] tempString;
for (i = 0 ; i < array.length ; ++i)
{
pos = addIntegerToString (array[i], byteArray, pos);
byteArray [pos] = '\n';
++pos;
}
times [4] = System.currentTimeMillis ();
// String in eine Datei abspeichern
BufferedOutputStream stream;
try
{
stream = new BufferedOutputStream (new FileOutputStream ("test.txt"));
stream.write (byteArray,0,pos);
stream.close ();
}
catch (IOException e)
{
System.out.println ("FEHLER FEHLER FEHLER FEHLER FEHLER");
}
times [5] = System.currentTimeMillis ();
// Wurzeln berechnen
for (i = 0 ; i < doubleArray.length ; ++i)
{
doubleArray[i] = Math.sqrt(doubleArray[i]);
}
times [6] = System.currentTimeMillis ();
// Ausgabe der Zeiten
System.out.println ("Array erzeugen : " + String.valueOf (times[1]-times[0]) + "ms");
System.out.println ("Zufallszahlen erzeugen : " + String.valueOf (times[2]-times[1]) + "ms");
System.out.println ("Sortieren : " + String.valueOf (times[3]-times[2]) + "ms");
System.out.println ("String (anhängen) : " + String.valueOf (times[4]-times[3]) + "ms");
System.out.println ("Speichern : " + String.valueOf (times[5]-times[4]) + "ms");
System.out.println ("Wurzeln berechnen : " + String.valueOf (times[6]-times[5]) + "ms");
}private final static int addIntegerToString(int i, byte [] string, int currentPos)
{
int q, r, charPos ;
charPos = 12 ;
byte buf [] = new byte [charPos] ;
byte sign = 0 ;if (i == Integer.MIN_VALUE)
{
buf = new byte [] {'0','-','2','1','4','7','4','8','3','6','4','8'};
charPos = 1;
}
else
{
if (i < 0)
{
sign = '-' ;
i = -i ;
}// Generate two digits per iteration
while ( i >= 65536 )
{
q = i / 100 ;
// really: r = i - (q * 100) ;
r = i - ((q << 6) + (q << 5) + (q << 2)) ;
i = q ;
buf [--charPos] = DigitOnes [r] ;
buf [--charPos] = DigitTens [r] ;
}// Fall thru to fast mode for smaller numbers
// assert(i <= 65536, i);
for (;;)
{
q = (i * 52429) >>> (16+3) ;
r = i - ((q << 3) + (q << 1)) ; // r = i-(q*10) ...
buf [--charPos] = digits [r] ;
i = q ;
if (i == 0) break ;
}
if (sign != 0)
{
buf [--charPos] = sign ;
}
}int end = 12 - charPos+currentPos;
for (;currentPos < end ; ++currentPos, ++charPos)
{
string [currentPos] = buf[charPos];
}
return currentPos;
}private final static void sort (int [] a)
{
quickSort (a,0,a.length-1);
}private final static void quickSort (int [] a, int begin, int end)
{
int i=begin,j=end;
int pivotElement = a[((end + begin) >>> 1)];
int temp = 0;
while (i < j)
{
while (a[i] < pivotElement) ++i;
while (a[j] > pivotElement) --j;
if (a[i] == (temp = a[j]))
{
++i;
continue;
}
a[j] = a[i];
a[i] = temp;
if (a[i] != pivotElement) ++i;
else
{
temp = ((j-i) >>> 1) + i;
a[i] = a[temp];
a[temp] = pivotElement;
}
if (a[j] != pivotElement) --j;
else
{
temp = ((j-i) >>> 1) + i;
a[j] = a[temp];
a[temp] = pivotElement;
}
}
if ((temp = j - begin) > 18) quickSort (a,begin,j-1);
else if (temp > 1) insertionSort (a,begin,j-1);
if ((temp = end - j) > 18) quickSort (a,j+1,end);
else if (temp > 1) insertionSort (a,j+1,end);
}private final static void insertionSort (int [] a, int begin, int end)
{
int j, b;
int temp;
int i = begin;
while (i != end)
{
++i;
temp = a[i];
b = i;
j = i - 1;
while (temp < a[j])
{
a[b] = a[j];
b = j;
--j;
if (b == begin) break;
}
a[b] = temp;
}
}
}[/code]