bubble sort

bastele grade an einer Sorter-Testroutine. Könnt ihr mal drüberschaun, ob so o.k.?

#include <iostream>
#include <ctime>
#include <conio.h>
using namespace std;

int g_n,g_N,g_s;

void bubblesort(int *array, int left, int right)
{
  g_s=0;
  int sorts,swap;
  int n=0;
  int N=right-left+1;

  for(int y=left;y<right;y++)   // 1. Schleife
  {
    sorts=0;
    for(int x=left;x<(right-y);x++) // 2. Schleife
    {
        if(array[x]>array[x+1])
        {
            swap=array[x];
            array[x]=array[x+1];
            array[x+1]=swap;
            sorts++;
        }
        n++;
    }
    g_s+=sorts;
    if(!sorts) break;
  }
  g_n=n;
  g_N=N;
}

int main()
{
  const int MAX = 1000;
  clock_t t1,t2;
  double ts;
  int a[MAX];
  for(int i=0;i<(MAX+1);i++) a[i]=MAX-i; //ungünstigster Fall
  t1=clock();
  bubblesort(a,0,MAX-1);
  t2=clock();
  ts=(t2-t1)/static_cast<double>(CLOCKS_PER_SEC);
  //for(int x=0;x<(MAX);x++) cout << a[x] << ' ';
  cout << "\nN=" << g_N << "\tDurchlaeufe: " << g_n << "\tSorts: " << g_s
       << "\tZeit: " << ts << endl;
  //getch();

  int b[MAX];
  for(int i=0;i<(MAX+1);i++) b[i]=i+1; //günstigster Fall
  t1=clock();
  bubblesort(b,0,MAX-1);
  t2=clock();
  ts=(t2-t1)/static_cast<double>(CLOCKS_PER_SEC);
  //for(int x=0;x<(MAX);x++) cout << b[x] << ' ';
  cout << "\nN=" << g_N << "\tDurchlaeufe: " << g_n << "\tSorts: " << g_s
       << "\tZeit: " << ts << endl;
  //getch();

  int c[MAX];
  for(int j=0; j<10; j++)
  {
  srand(time(NULL)*j);
  for(int i=0;i<(MAX+1);i++) c[i]=rand()%MAX; //zufälliger Fall
  t1=clock();
  bubblesort(c,0,MAX-1);
  t2=clock();
  ts=(t2-t1)/static_cast<double>(CLOCKS_PER_SEC);
  //for(int x=0;x<(MAX);x++) cout << c[x] << ' ';
  cout << "\nN=" << g_N << "\tDurchlaeufe: " << g_n << "\tSorts: " << g_s
       << "\tZeit: " << ts << endl;
  }

  getch();
  return(0);
}

Wie kann ich die Zufälligkeit noch erhöhen? Ist "srand(time(NULL)*j);" hier o.k., mir ist nix bessres eingfallen.

Sorry. Kan dir ier nicht weiter helfen. Bin gerade beim Zeiger und so....
Hab das Programm aber von der Seite geklaut und bei mir compiliert, aber was es da tut. Noch schwarze Magie für mich.....Aber da meldet sich schon ein c++ Experte. Von denen gibt es hier genug(zum glück).Cu.

Con*n

Hi,

ich Versuch mich mal, was mir so aufgefallen ist.

mit

int a[MAX]; 
   for(int i=0;i<(MAX+1);i++) a[i]=MAX-i;

schreibst Du über die Arraygrenzen hinaus. Wenn Du ein Array anlegst mit 'int a[1000]' dann kannst Du es nur von a[0] bis a[999] ansprechen. In Deinem Code ist es aber bis a[1000].

Warum der Cast von CLOCKS_PER_SEC nach double? Schau mal in die "time.h" rein. dort steht bei mir "#define CLOCKS_PER_SEC 1000.0" das ist ja schon ein double. Wenn Du unbedingt casten willst, dann nach clock_t. Das ist aber unnötig.

Um Dein Array mit Zufallswerten zu füllen, solltest Du Dir vielleicht was schreiben, bei dem jeder Wert im Array am Schluß nur einmal vorkommt, ich glaub, dann bekommt bubble am meisten zu tun.

grüße Con@n

Erhard Henkes

Arraygrenzen sind wichtig.
static_cast muss bleiben, float reicht.

Bei Dev-C++ steht in time.h:

/*
 * Number of clock ticks per second. A clock tick is the unit by which
 * processor time is measured and is returned by 'clock'.
 */
#define	CLOCKS_PER_SEC	((clock_t)1000)
#define	CLK_TCK		CLOCKS_PER_SEC

Interessant ist, dass diese Methode zwar mehr Durchläufe braucht als die von Volkard in seinem alten Tutorial (Lektion 49, siehe http://www.xan.ch/pc/code/cpp/bubble_sort.html ) vorgestellte (dort ist noch eine weitere Abfrage eingebaut, um Läufe zu sparen), aber dennoch schneller ist (die swap-Aufgabe habe ich bei Volkard analog integriert, sonst hat seine Methode keine Chance).

Vergleich mit 20000 Elementen (Prozessor ca. 1.4 GHz):

N        Läufe       Sorts      Zeit(s)    Methode
20000    199979847   99687170   4.276      diese hier
20000    199867759   99687170   4.607      Volkard (integrierter Swap)

#include <iostream>
#include <ctime>
#include <conio.h>
using namespace std;

int g_n,g_N,g_s;

void bubblesortVolkard(int *array,int size)
{
   int N=size;
   g_s=0;
   int n=0;
   int sorts, swap;
   int obergrenze=size-1;
   while(obergrenze>0)
   {
      int letzterAustausch=0;
      sorts=0;
      for(int pos=0;pos<obergrenze;++pos)
      {
         if(array[pos]>array[pos+1])
         {
            swap=array[pos];
            array[pos]=array[pos+1];
            array[pos+1]=swap;
            letzterAustausch=pos;
            sorts++;
         };
         n++;
      };
      g_s+=sorts;
      obergrenze=letzterAustausch;
   };
   g_n=n;
   g_N=N;
};

void bubblesort(int *array, int left, int right)
{
  g_s=0;
  int sorts,swap;
  int n=0;
  int N=right-left+1;

  for(int y=left;y<right;y++)   // 1. Schleife
  {
    sorts=0;
    for(int x=left;x<(right-y);x++) // 2. Schleife
    {
        if(array[x]>array[x+1])
        {
            swap=array[x];
            array[x]=array[x+1];
            array[x+1]=swap;
            sorts++;
        }
        n++;
    }
    g_s+=sorts;
    if(!sorts) break;
  }
  g_n=n;
  g_N=N;
}

int main()
{
  int MAX;
  cout<<"Anzahl Elemente im Array? ";
  cin>>MAX;
  clock_t t1,t2;
  double ts;

/*
...
*/

  int c[MAX];
  int d[MAX];
  srand(time(NULL));
  for(int i=0;i<(MAX);i++) {d[i]=c[i]=rand()%MAX;} //zufälliger Fall
  cout<<endl<<endl;

  t1=clock();
  bubblesort(c,0,MAX-1); //Methode1
  t2=clock();
  ts=(t2-t1)/static_cast<float>(CLOCKS_PER_SEC);
  cout << "\nN=" << g_N << "\tLaeufe: " << g_n << "\tSorts: " << g_s
       << "\tZeit: " << ts << " BS Test" << endl;
  cout<<endl;       

  t1=clock();
  bubblesortVolkard(d,MAX); //Methode2
  t2=clock();
  ts=(t2-t1)/static_cast<float>(CLOCKS_PER_SEC);
  cout << "\nN=" << g_N << "\tLaeufe: " << g_n << "\tSorts: " << g_s
       << "\tZeit: " << ts << " BS Volkard" << endl;

  getch();
  return 0;
}

Siehe auch hier:
http://leepoint.net/notes/cpp/algorithms/arrayfuncs/bubblesort2.html

Bubble sort sind O((N-1)^2/2), und Omega(N-1). Durchschnitt siehe oben. Das ist auf jeden Fall zu langsam. Siehe quick sort, heap sort usw.

Eine Animation zu bubble sort findet man z.B. hier:
http://rz06.rz-fddi.fh-karlsruhe.de/~lijo0014/sort_animiert.html

Erhard Henkes

Deutlich schneller ist Quicksort:

// siehe http://sattas.homeunix.net/zeugs/quicksort.pdf
#include <iostream>
#include <ctime>
#include <conio.h>
using namespace std;

const int MAX = 10000000; // mit Bubble Sort gar nicht erst probieren!
int daten[MAX];

void quicksort( int von, int bis )
{
  int links = von, rechts = bis, mitte, zwischen;
  mitte = ( von + bis ) / 2;
  do{
      for(;daten[links] < daten[mitte]; links++);
          for(;daten[mitte] < daten[rechts]; rechts--);
              if(links <= rechts) 
              { 
                  //Tausch durchfuehren
                  zwischen = daten[links];
                  daten[links] = daten[rechts];
                  daten[rechts] = zwischen;
                  links++;
                  rechts--;
              }
    }
    while (links <= rechts);
    if(von < rechts) quicksort(von, rechts);
    if(links < bis)  quicksort(links, bis);
}

int main()
{
  clock_t t1,t2;
  double ts;
  srand(time(NULL));

  for(int i=0;i<(MAX);i++) 
  {
    daten[i] = rand()%MAX;
  } 

  t1=clock();
  quicksort(0,MAX-1); 
  t2=clock();

  ts=(t2-t1)/static_cast<float>(CLOCKS_PER_SEC);
  cout << "\tZeit: " << ts << " QuickSort Test" << endl;
  cout<<endl;       

  getch();
  return 0;
}