Elementarschritt im Bubblesort

04/22/2012 12:52 kaiN_92#1
Huhu,

ich sitz gerade an ner Uni-Aufgabe und weiß zum ersten mal nicht, was ich zutun hab :|.

Quote:
Wir betrachten das Problem SecondLargest:
Input: eine Folge a von n ganzen Zahlen
Output: das zweitgrote Element der Folge
(a) Entwickeln Sie einen Algorithmus in Python- oder Java-Code, der das Problem lost.
(b) Wieviele Elementarschritte (Vergleiche, Zuweisungen, arithmetische Operationen,
boolesche Operationen, . . . ) benotigt Ihr Algorithmus in Abhangigkeit von n?
ich hab mich zur Lösung für nen BubbleSort entschieden, bei dem er dann einfach das 2. Glied ausgibt (bzw solang nach hinten rutscht bis n != n-1)

Allerdings komme ich auf die Elementarschrittfrage nicht klar..

Vergleiche gibt es ja maximal soviele, wie viele Zahlen verglichen werden..
also zB bei
1,8,3,4
gibt es 4 durchläufe, bis sicher das größte vorne ist..innerhalb dieser durchläufe gibt es maximal 3 Vertauschungen..4x3 = 12..
etc..aber ich weiß nicht was mit dem Rest sein soll..außerdem ist dies ja die maximale Anzahl an Vertauschungen..und variable, je nach eingabe.

Wäre Klasse, wenn jemand Rat weiß.

Code:
# coding=latin-1
def bubblesort(glieder):
 
        maxdurchlaeufe = len(glieder) #Bestimmung der maximalen Anzahl an Tauschvorgängen
        n = len(glieder) - 1 #Da die 2.größte ausgegeben werden soll
 
        while maxdurchlaeufe >= 1: #durchlaufcounter
 
                for k in range(len(glieder) - 1): #beginn forschleife
 
                        if glieder[k] > glieder[k+1]: #falls Position k+1 kleiner als k tausche
 
                                temp = glieder[k]    #zwischenspeichern von zahl k in temp          
 
                                glieder[k] = glieder[k+1] #k+1 nach k
 
                                glieder[k+1] = temp #k in k+1 (Ende Tausch)
 
                maxdurchlaeufe = maxdurchlaeufe - 1  #durchlaufcounter--
 
        while glieder[n] == glieder[n-1]: #falls letzte beiden Zahlen gleich solang zurückgehen bis seq[n] != seq[n-1]
            n -= 1
        return glieder[n-1] #Ausgabe 2. größte Zahl
04/22/2012 13:29 ms​#2
Es gibt immer n * (n - 1) Durchläufe. Deine While-Schleife läuft immer n-Mal und deine innere For-Schleife (n-1)-Mal.
Dein Algorithmus bricht nicht ab wenn es bei einem Durchlauf keine Vertauschungen gab, deswegen ist die Anzahl immer gleich.
04/22/2012 13:32 kaiN_92#3
Arg..stimmt -_-"..

Da ich Python-Krüppel bin hab ich gar keine Abbruchbedingung drin..total verplant !

Danke !
04/22/2012 13:55 Dr. Coxxy#4
außerdem ist bei der aufgabenstellung (wenn es denn die originale ist) der bubblesort wie mit kanonen auf spatzen zu schießen.
musst ja nicht das gesamte array sortieren, sondern nur das 2. größte element FINDEN!
d.h. gehst linear durch, speicherst immer die beiden größten ab:
pseudocode:
Code:
	int max1 = 0; // größtes element
	int max2 = 0; // 2. größtes element
	for (int i = 0; i < n; i++)
	{
		if (array[i] > max1)
		{
			max2 = max1;
			max1 = array[i];
		}
		else if (array[i] > max2)
		{
			max2 = array[i];
		}
	}
	printf("2. Grösstes Element: %d\n", max2);
vorgabe ist dabei, dass alle elemente in der liste > 0 sind, ansonsten musst du die initialisierungen von max1/2 bei nem int auf -2,147,483,648 setzen, o.ä. tricks.
ist vielleicht nicht die sauberste lösung, aber die schnellste, da maximal n*2 vergleiche durchgeführt werden und maximal n kopiervorgänge.
ist ungetestet und hat vllt nen paar kleinere häkelchen, z.b. dass in dem array mindestens 2 elemente drin sein müssen, die initwerte von max1/2 kleiner als mindestens 2 der arrayelemente sein müssen, ???...
mehr fällt mir so jetzt nicht ein...

kann auch gut sein, dass man da noch was optimieren kann, war jetzt 20 second brainstorm ;)
04/22/2012 14:20 xNopex#5
Quote:
Input: eine Folge a von n ganzen Zahlen
Quote:
Originally Posted by Dr. Coxxy
int max1 = 0; // größtes element
int max2 = 0; // 2. größtes element
Failbob..

Trivialerweise versagt dein Code schon bei der Folge 1,2.... 20s brainstorm vllt doch bisschen zu wenig für dich..

Mein Ansatz wäre spontan zweimal das Maximum zu bilden, wobei das erste Maximum vor dem zweiten Durchgang aus der Folge entfernt wird.

EDIT: Wenn du cool bist, machst du das via Rekursion.
04/22/2012 14:30 MoepMeep#6
Quote:
Originally Posted by Dr. Coxxy View Post
vorgabe ist dabei, dass alle elemente in der liste > 0 sind, ansonsten musst du die initialisierungen von max1/2 bei nem int auf -2,147,483,648 setzen, o.ä. tricks.
Es wäre auch viel zu einfach, max1 auf den wert des 1.Elementes zu setzen :<
04/22/2012 14:31 Dr. Coxxy#7
jaja, wie schrecklich, nen kleinen copy vergessen, habs korrigiert...

Code:
	int max1 = 0; // größtes element
	int max2 = 0; // 2. größtes element
	for (int i = 0; i < n; i++)
	{
		if (array[i] > max1)
		{
			max2 = max1;
			max1 = array[i];
		}
		else if (array[i] > max2)
		{
			max2 = array[i];
		}
	}
	printf("2. Grösstes Element: %d\n", max2);
das was nopex erwähnt hat mit 2x maximum hab ich auch schon gedacht, aber so dürfte es ein wenig schneller sein, vorteil ist natürlich, dass das mit ner rekursion auch eine n-te lösung einfach finden lassen sollte, während man bei meiner im worst case das ganze array doppelt hat...

@moep:
geht ja auch nicht:
Code:
-1, -2, -3, -4
04/22/2012 14:36 xNopex#8
Trotzdem will er ganze Zahlen und nicht natürliche mit 0..
04/22/2012 14:41 MoepMeep#9
Da klein coxxy es anscheinend nicht versteht :<
Code:
int max1 = array[0] > array[1]?array[0]:array[1];
int max2 = array[0] > array[1]?array[1]:array[0];
Natürlich vorher prüfen, ob das Array überhaupt so groß ist ;)
04/22/2012 14:42 Dr. Coxxy#10
Code:
	int max1 = array[0] >= array[1] ? array[0] : array[1]; // größtes element
	int max2 = array[0] <= array[1] ? array[0] : array[1]; // 2. größtes element

	for (int i = 0; i < n; i++)
	{
		if (array[i] > max1)
		{
			max2 = max1;
			max1 = array[i];
		}
		else if (array[i] > max2)
		{
			max2 = array[i];
		}
	}
	printf("2. Grösstes Element: %d\n", max2);
EDIT:
und moep war 30 sekunden schneller als ich...
dann sag das auch, anstatt die "lösung" hinterherzuschieben.

Quote:
Es wäre auch viel zu einfach, max1 auf den wert des 1.Elementes zu setzen :<
das hier ist nämlich eindeutig falsch.
04/22/2012 14:43 MoepMeep#11
Und wo ist die Überprüfung ob das Array überhaupt 2 Elemente hat?
04/22/2012 14:45 Dr. Coxxy#12
Quote:
Originally Posted by MoepMeep View Post
Und wo ist die Überprüfung ob das Array überhaupt 2 Elemente hat?
die erwähne ich in meiner ersten antwort:
Quote:
ist ungetestet und hat vllt nen paar kleinere häkelchen, z.b. dass in dem array mindestens 2 elemente drin sein müssen,
genauso, wie das min initialisierungsproblem, das hätte der te ja auch selbst hinkriegen können, habs ja erwähnt...
das mit dem fehlenden copy war natürlich my fault, war aber auch nur in 1 min so hingerotzt ;)
04/22/2012 15:11 ms​#13
Warum muss eigentlich jeder Thread hier in einen Penisvergleich degenerieren? :|
04/22/2012 15:14 Dr. Coxxy#14
ist halt ein forum, da passiert das (leider?).

immerhin hat man verschiedene meinungen und lernt idr. was dabei, auch wenn mans nicht immer zugeben will ;)
04/22/2012 15:54 MrSm!th#15
Quote:
Originally Posted by Metin2Spieler97 View Post
Es gibt immer n * (n - 1) Durchläufe. Deine While-Schleife läuft immer n-Mal und deine innere For-Schleife (n-1)-Mal.
Dein Algorithmus bricht nicht ab wenn es bei einem Durchlauf keine Vertauschungen gab, deswegen ist die Anzahl immer gleich.
Nein, das gilt für das O-Kalkül, aber da werden Elementarschritte wie Vergleiche etc. vernachlässigt und nur Schleifendurchläufe betrachtet.