Sortieralgorithmus Bubblesort - Formel für die anzahl der Prüfungen

18.02.2012, 00:06

Tom123

Sortieralgorithmus Bubblesort - Formel für die anzahl der Prüfungen

Meine Frage:
Hallo,

Ich bin zur Zeit auf der suche nach einer Formel, welche beschreibt wie oft eine Prüfung, einer n-großen Liste mit dem Sortieralgorithmus Bubblesort stattfindet. Zudem muss ich sagen, dass es sich um die Version handelt, bei der man davon ausgeht, dass jeweils das letzte Element (nach dem ersten Sortier-Durchgang) nicht mehr geprüft werden muss.

Meine Ideen:
Was ich weiß:

Enthält die Liste z.B. 5 Elemente werden komplette 4 durchgänge benötigt (Sortierdurchgänge = Anzahl der Elemente in der Liste n - 1).

In dem 1. Sortierdurchgäng werden alle zahlen geprüft = 4 Prüfungen
In dem 2. Sortierdurchgäng, werden alle zahlen bis auf die letze geprüft = 3 Prüfungen.
Im 3. Sortierdurchgäng sind es nur noch 2 Prüfungen.

Meine Frage lautet jetzt, wie bekomme ich für diese Situartion eine Formel, welche mir die Anzahl der Prüfungen ausgibt, wenn ich nur den Wert N (Größe der zu Sortierenden Liste) kenne.

Gruß Tommy

18.02.2012, 01:51

SusiQuad

Auf diesen Beitrag antworten »

RE: Sortieralgorithmus Bubblesort - Formel für die anzahl der Prüfungen
Finde eine Formel für $\begin{eqnarray*} 1 + 2 + \cdots + n \end{eqnarray*}$ .

Wir betrachten dazu folgende Tabelle und spielen Puzzle...

$\begin{eqnarray*} \begin{array}{ccccc} 1 = & (1) & \cdot & \cdot & \cdot 2 = & 1 & (1) & \cdot & \cdot 3 = & 1 & 1 & (1) & \cdot \cdot n = & 1 & 1 & \cdots &(1) \end{array} \end{eqnarray*}$

Die linke Spaltesumme ist obige Summe $\begin{eqnarray*} 1 + 2 + \cdots + n \end{eqnarray*}$ . Die Zeilen sind genausoviele 1-en, wie links in der Spalte stehen (z.B.) $\begin{eqnarray*} 1 + 1 + 1 = 3 \end{eqnarray*}$ oder (z.B.) die letzte Zeile $\begin{eqnarray*} 1 + 1 + \cdots + 1 = n \end{eqnarray*}$

Also zählen wir die 1-en in diesem Dreieck.

Wenn unterhalb von den (1)-en u Stück stehen, ist n + u unsere Summe, denn es gibt n (1)-en in der Diagonalen. Oberhalb gibt es aber auch u Punkte und insgesamt ist es ein Quadrat mit $\begin{eqnarray*} n^2 \end{eqnarray*}$ Einträgen.

Also gilt $\begin{eqnarray*} n^2 = n + 2~u \end{eqnarray*}$ . Das Quadrat besteht also aus der Diagonalen plus 2 Dreiecken.
Damit ist $\begin{eqnarray*} u= \frac{n^2-n}{2} \end{eqnarray*}$
und $\begin{eqnarray*} u + n = \frac{n~(n+1)}{2} = 1 + 2 + \cdots + n \end{eqnarray*}$ ist Deine Formel.

18.02.2012, 01:59

Kasen75

Auf diesen Beitrag antworten »

RE: Sortieralgorithmus Bubblesort - Formel für die anzahl der Prüfungen
Hallo Tom,

führe doch deine liste einfach weiter. Außerdem komme ich auf eine andere Formel als SusiQuad.

Zitat:

In dem 1. Sortierdurchgäng werden alle zahlen geprüft = 4 Prüfungen
In dem 2. Sortierdurchgäng, werden alle zahlen bis auf die letze geprüft = 3 Prüfungen.
Im 3. Sortierdurchgäng sind es nur noch 2 Prüfungen.

Das ist ein sehr guter Ansatz. In deinem Beispiel ist n =5

Anzahl der prüfungen sind:

4
3
2
1

Anders angeordnet:

4 3
1 2
------------
Summe 5 5

= 2*n

Jetzt muss man noch überlegen, wie die 2 entstanden ist. Die 2 entsteht, dadurch, dass man jeweils zwei Elemente der n-1 Elemente untereinander schreibt und somit die Anzahl der Summen halbiert. Anders gesagt die (n-1) werden durch 2 geteilt.

Jetzt musst du nur noch die 2 durch das ersetzen, was ich beschrieben habe.

Ich hoffe ich konnte Dir weiterhelfen. Melde dich bitte wenn du weiter gekommen bist. Auch wenn nicht.

Bis dann.

18.02.2012, 16:02

Tom123

Auf diesen Beitrag antworten »

Erst einmal vielen Dank für eure Hilfe.

Ich hatte mir gestern Abend mir auch eine Formel überlegt, welche am ende irgendwie quatsch/falsch und nicht mehr nachvollziehbar war.

( ( (n-1)*n) /2 ) -n
(Ich wollte vom Quadrat die erste zeile "Abschneiden" und den Rest des Quadrates teilen).
____________________________________________________________________

Die Erklärung von SusiQuad kann ich leider garnicht nachvollziehen.
Bin dazu wohl einfach nicht intelligent genug.

Die erklärung von Kasen75 ist für mich etwas verständlicher.
Obwohl ich nicht genau dahinter komme, wie Du von 5 5 auf 2 kommst.
Auch die "andere Anordnung" kommt mir spanisch vor:

Aus: 4 3 2 1 wird:

4 3
1 2

Müsste es nicht:

4 3
2 1

sein?

Gruß Tom

18.02.2012, 18:32

Kasen75

Auf diesen Beitrag antworten »

Hallo Tom,

der Grund warum ich das so angeordnet habe ist, dass wir möglichst auf einfache Weise zu einer Formel kommen. Die Art wie du und wie ich es angeordnet haben ist beides richtig. Absolut korrekt. Bei mir steht die größte Anzahl von Prüfungen über der kleinsten Anzahl von Prüfungen. Danach die zweitgrößte Anzahl von Prüfungen über die der zweit kleinsten Anzahl von Prüfungen. [Bei mir ist es im Uhrzeigersinn angeordnet]. Somit ergibt sich immer die gleiche Summe (=n). Und die ist dann (n-1)/2 - mal vorhanden. In deinem Beispiel 2-mal.

Deine Formel sieht schon sehr sehr gut aus, auch wenn sie noch nicht vollständig richtig ist. Gratulation. Ich hoffe mit dem obigen Hinweis kannst du deine Formel korregieren. Es ist wirklich nicht viel was du von deiner Formel wegnehmen musst. Bitte dann posten. Würde mich freuen.

Grüße

18.02.2012, 19:22

Tom123

Auf diesen Beitrag antworten »

Nabend,

Das war ja eine Geburt ^^
Ich hab meinen fehler erkannt:

(((n-1)*n) /2 )

Ist die gesuchte Formel.

Vielen Dank
Gruß Tom

18.02.2012, 22:21

Kasen75

Auf diesen Beitrag antworten »

Hallo Tom,

jetzt hast du im Prinzip das gemacht, was der der berühmte Mathematiker Carl Friedrich Gauss in jungen Jahren (als Schüler) gemacht haben soll. Er soll die Gauß´sche Summenformel entwickelt haben. Deine Formel ist eine Variante davon. Glückwunsch und weiter viel Spaß mit der Mathematik.

mfg

Neue Frage »

Antworten »

Sortieralgorithmus Bubblesort - Formel für die anzahl der Prüfungen

Verwandte Themen