Bubblesort - Veranschaulichung

Erhard Henkes

Da das Thema Sortieren, z.B. anhand von Bubble sort immer wieder kommt, hier ein Testfeld, damit man genau sieht, was passiert:

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

class xINT //Testklasse für zu sortierende Datenelemente
{

private:
  int num;
  static int countCtor;
  static int countDtor;
  static int countCopycon;
  static int countOpAssign;

public:
  xINT()
  {
      std::cout << this << ": " << "ctor" << std::endl;
      ++countCtor;
  }

 ~xINT()
  {
      std::cout << this << ": " << "dtor" << std::endl;
      ++countDtor;
  }

  xINT(const xINT& x)
  {
      std::cout << this << ": " << "copycon von " << std::dec << &x << std::endl;
      num = x.getNum();
      ++countCopycon;
  }

  xINT& operator=(const xINT& x)
  {
      if (&x == this)
      {
          std::cout << "Selbstzuweisung mit op=" << std::endl;
      }
      std::cout << this << ": " << "op= von " << std::dec << &x << std::endl;
      num = x.getNum();
      ++countOpAssign;
      return *this;
  }

  int getNum() const {return num;}
  void setNum(int val) {num = val;}
  static void statistik(std::ostream&);
  static void reset();
};

int xINT::countCtor     = 0;
int xINT::countDtor     = 0;
int xINT::countCopycon  = 0;
int xINT::countOpAssign = 0;

void xINT::statistik(std::ostream& os)
{
  os   << "Ctor:    " << countCtor    << std::endl
       << "Dtor:    " << countDtor    << std::endl
       << "Copycon: " << countCopycon << std::endl
       << "op=:     " << countOpAssign;
}

void xINT::reset()
{
    countCtor     = 0;
    countDtor     = 0;
    countCopycon  = 0;
    countOpAssign = 0;
}

std::ostream& operator<< (std::ostream& os, const xINT& x)
{
  os << x.getNum();
  return os;
}

std::istream& operator>> (std::istream& is, xINT& x)
{
  int i;
  is >> i;
  x.setNum(i);
  return is;
}

bool operator< (const xINT& a, const xINT& b)
{
    return a.getNum() < b.getNum();
}

bool operator> (const xINT& a, const xINT& b)
{
    return a.getNum() > b.getNum();
}

bool operator== (const xINT& a, const xINT& b)
{
    return a.getNum() == b.getNum();
}

bool operator!= (const xINT& a, const xINT& b)
{
    return a.getNum() != b.getNum();
}
//----------------------------------------------------

template <typename T>
void output(T* array, int N)
{
   int i;
   cout << endl;
   for(i=0;i<N;++i) cout << array[i] << ' ';
   cout << endl; cout << endl;
}

//----------------------------------------------------

template <typename T>
void bubbleSort(T* array, int N)
{
   for(int i=N-1; i>0; --i)
   {
      bool austausch = false;
      for(int j=0; j<i; ++j)
      {
         if(array[j+1] < array[j])
         {
            swap(array[j], array[j+1]);
            austausch = true;
            output(array,N); // Hier mit Ausgabe zum verfolgen
         }
      };
      if(!austausch) break;
   };
};

//----------------------------------------------------

int main()
{
   const int N = 7;
   int i;
   xINT array[N];

   for(i=0;i<N;++i) array[i].setNum( rand() % N );

   output(array,N);

   bubbleSort(array,N);

   output(array,N);

   getch();
}

Beispiel:

0x22ff30: ctor    // Element a (zu Beginn)
0x22ff34: ctor    // Element b (zu Beginn)
0x22ff38: ctor
0x22ff3c: ctor
0x22ff40: ctor
0x22ff44: ctor
0x22ff48: ctor

6 1 6 5 3 2 5

0x22fe50: copycon von 0x22ff30   // Element a wird nach temp (0x22fe50) gesichert
0x22ff30: op= von 0x22ff34       // Element b kommt auf alten Platz von Element a
0x22ff34: op= von 0x22fe50       // Element a kommt (von temp) auf alten Platz von Element b
0x22fe50: dtor                   // temp wird gelöscht

1 6 6 5 3 2 5

0x22fe50: copycon von 0x22ff38
0x22ff38: op= von 0x22ff3c
0x22ff3c: op= von 0x22fe50
0x22fe50: dtor

1 6 5 6 3 2 5

0x22fe50: copycon von 0x22ff3c
0x22ff3c: op= von 0x22ff40
0x22ff40: op= von 0x22fe50
0x22fe50: dtor

1 6 5 3 6 2 5

0x22fe50: copycon von 0x22ff40
0x22ff40: op= von 0x22ff44
0x22ff44: op= von 0x22fe50
0x22fe50: dtor

1 6 5 3 2 6 5

0x22fe50: copycon von 0x22ff44
0x22ff44: op= von 0x22ff48
0x22ff48: op= von 0x22fe50
0x22fe50: dtor

1 6 5 3 2 5 6

0x22fe50: copycon von 0x22ff34
0x22ff34: op= von 0x22ff38
0x22ff38: op= von 0x22fe50
0x22fe50: dtor

1 5 6 3 2 5 6

0x22fe50: copycon von 0x22ff38
0x22ff38: op= von 0x22ff3c
0x22ff3c: op= von 0x22fe50
0x22fe50: dtor

1 5 3 6 2 5 6

0x22fe50: copycon von 0x22ff3c
0x22ff3c: op= von 0x22ff40
0x22ff40: op= von 0x22fe50
0x22fe50: dtor

1 5 3 2 6 5 6

0x22fe50: copycon von 0x22ff40
0x22ff40: op= von 0x22ff44
0x22ff44: op= von 0x22fe50
0x22fe50: dtor

1 5 3 2 5 6 6

0x22fe50: copycon von 0x22ff34
0x22ff34: op= von 0x22ff38
0x22ff38: op= von 0x22fe50
0x22fe50: dtor

1 3 5 2 5 6 6

0x22fe50: copycon von 0x22ff38
0x22ff38: op= von 0x22ff3c
0x22ff3c: op= von 0x22fe50
0x22fe50: dtor

1 3 2 5 5 6 6

0x22fe50: copycon von 0x22ff34
0x22ff34: op= von 0x22ff38
0x22ff38: op= von 0x22fe50
0x22fe50: dtor

1 2 3 5 5 6 6

0x22ff30: ctor
0x22ff34: ctor
0x22ff38: ctor
0x22ff3c: ctor
0x22ff40: ctor
0x22ff44: ctor
0x22ff48: ctor

Man sieht, dass der Aufwand in der Testklasse xINT sich auf den Austausch benachbarter Elemente beschränkt. Man benötigt nur eine zusätzliche Speicherstelle für die beim Swap notwendige temporäre Variable.

Vielleicht hat jemand gute Ideen, was man hier zur Veranschaulichung noch dazu basteln könnte.

Erhard Henkes schrieb:

...damit man genau sieht, was passiert:

^^sowas ist doch bullshit.
hier sieht man viel besser, wie sorts funktionieren
http://www.site.uottawa.ca/~stan/csi2514/applets/sort/sort.html
http://www.solidware.com/sort/
http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html

Erhard Henkes

Ja, sehr schön. Davon gibt es vermutlich schon genug.
Hier z.B. ein weiterer Link: http://siebn.de/index.php?page=anisort/anisort

Ich möchte, dass ein Anfänger jeden Schritt, aber auch genau das damit zusammenhängende Speichermanagement erkennt und selbst den kompletten C++-Sourcecode in Händen hält, um auch eigene Experimente durchzuführen.

princess

weil es mir grad aufgefallen ist (und nix mit dem thema zu tun hat), es geht um die signatur....

man schreibt "guten code" so:

getter:

public:
type const& name() const {}

operator:

public: 
type& operator+=(type const& rhs); 
"freestanding:" 
type const 
operator+(type const& lhs, type const& rhs);

also zusammengefasst: die ganzen const statments "ließt" man von rechts nach links... bsp: der getter name ist constant auf eine constante referenz vom typ ... hab das aus diversen styleguids und mein prof+tutoren ham mich geprügelt wenn ich das anders gemacht hab... klar hat so jeder sein stil, aber diese variante find ich echt die schlauere...

//lhs: left hand side
//rhs: right hand side

queer_boy

princess schrieb:

type const
operator+(type const& lhs, type const& rhs); [/code]

hoffe, dass camper das nicht sieht. ansonsten erklär mal, warum du type const brauchst.

sothis_

const ist der anfang allen übels

BorisDieKlinge

ohje prinzesschen...

Erhard Henkes

Genau diese weitgehend sinnlose Streiterei ist das Problem bei der C++ Community. Kein Wunder, wenn sich da bald keiner mehr drauf einlassen möchte.

Erhard Henkes schrieb:

Ich möchte, dass ein Anfänger jeden Schritt, aber auch genau das damit zusammenhängende Speichermanagement erkennt und selbst den kompletten C++-Sourcecode in Händen hält, um auch eigene Experimente durchzuführen.

dann schau dir mal den c++ code auf dem von dir verlinkten applet an. wieso ist dein code so kompliziert? also für anfänger ist sowas absolut nix.

Bashar

Ich habe trotz aller möglichen Veranschaulichungen über Jahre hinweg (es gab zu QuickBasic, ca. 2 Jahre bevor pivke geboren ist, schon ein "Sortdemo", in dem mit eine zufällige Anordnung unterschiedlich langer Balken mit verschiedenen Algorithmen sortiert und animiert wurde) nie die einfachsten Sortieralgorithmen verstanden. Das kam erst durch eine abstraktere Sicht auf Sortieralgorithmen allgemein. Vielleicht bin ich ja sehr speziell, aber der Wert solcher Animationen leuchtet mir nicht so recht ein.

Simon2

Hi,

mir geht's halt andersherum: Ich verstehe die Sortiermechanismen über diese "Schritt-für-Schritt"-Animationen sehr viel besser.

Da sind unsere Denk-/Lernstrukturen wohl einfach anders.

Gruß,

Simon2.

Erhard Henkes

Ist schon o.k.

camper

queer_boy schrieb:

princess schrieb:

type const
operator+(type const& lhs, type const& rhs); [/code]

hoffe, dass camper das nicht sieht. ansonsten erklär mal, warum du type const brauchst.

Ich nehme an, es kommt meiner Bequemlichkeit entgegen, dass ich hier nun nichts mehr dazu zu schreiben brauche :p

sothis_

BorisDieKlinge schrieb:

ohje prinzesschen...

was geht'n mit dir?

vic1986

queer_boy schrieb:

... hoffe, dass camper das nicht sieht. ansonsten erklär mal, warum du type const brauchst. ...

Das macht natürlich besonders bei Oparatoren Sinn, damit das Ergebnis nicht als l-value eingesetzt werden kann.

Also, z.B. würden mit type const dann solche Ausdrücke verhindert:

5 + 7 = 99;

Was hat es mit camper auf sich?

Gruß

otze

//müll

camper

vic1986 schrieb:

Das macht natürlich besonders bei Oparatoren Sinn, damit das Ergebnis nicht als l-value eingesetzt werden kann.

Wenn man verhindern will, dass der Zuweisungsoperator auf das Ergebnis angewandt werden kann, dann ist const m.W. tatsächlich die einzig effektive Methode. Das Erschießen des Nachbarhundes ist ebenfalls effektiv, wenn man durch dessen Bellen belästigt wird.

vic1986

camper schrieb:

... Das Erschießen des Nachbarhundes ist ebenfalls effektiv, wenn man durch dessen Bellen belästigt wird. ...

Hübsches Bild, aber was heißt das konkret?

Nicht, dass ich diese Art der Beseitigung von Hunden nicht unterstützen würde ...

otze schrieb:

//müll

Wieso Müll? Die Kritik etwas ausführlicher darlegen bitte.

sothis_

vic1986 schrieb:

otze schrieb:

//müll

Wieso Müll? Die Kritik etwas ausführlicher darlegen bitte.

ich glaube er hat sich da selbst kritisiert

Bashar schrieb:

Ich habe trotz aller möglichen Veranschaulichungen über Jahre hinweg (es gab zu QuickBasic, ca. 2 Jahre bevor pivke geboren ist, schon ein "Sortdemo", in dem mit eine zufällige Anordnung unterschiedlich langer Balken mit verschiedenen Algorithmen sortiert und animiert wurde) nie die einfachsten Sortieralgorithmen verstanden. Das kam erst durch eine abstraktere Sicht auf Sortieralgorithmen allgemein.

lenken dich animationen und bunte bilder ab, oder verwirren sie dich gar?
dann bist du vielleicht ein sogenannter 'Savant'?

Bashar

fricky schrieb:

lenken dich animationen und bunte bilder ab, oder verwirren sie dich gar?
dann bist du vielleicht ein sogenannter 'Savant'?

Vielleicht bist du ein sogenannter 'Troll'?