witch doctor

Ich muss in Englisch etwas über "Operating Systems" schreiben.

Dabei wollte ich auch etwas über die Geschichte der einzelnen

Betriebssysteme schreiben (also über DOS, Windows, Mac, Linux).

Weiß jemand eine Internetseite, wo ich sowas finde?

Leider sind einige Algorithmen ganz schön schnell von den Animationen her dargestellt. Selbst mit der Geschwindigkeit von 1 ist es bei Insertion Sort zu schnell.

Originally posted by Pönk

Hi,

schau mal unter:

http://www.informatik.fh-trier.de/projekte/vivaldi/beispiele_vivaldi.html

sind verschiedene Sortiermechanismen dargestellt. Besonders interessant sind die Java-Simulationen, wo die Funktionsweise der Sortierung sehr gut dargestellt wird.

Gruß Pönk

Ich wollte nur sagen, dass ich diese Seite liebe!!!

Die ist super verständlich aufgemacht!!!

Danke!!!

Es wird schon klarer!

Ich schaue mir den ALgorithmus nochmal in Ruhe an und melde mich nochmal bei Fragen!

Aber erstmal danke!!!

(Bitte nicht als Spam werten! )

Also wenn r < l wäre, wären die Zeiger "aneinander vorbeigelaufen" ?

Aber wieso tausche ich dann?

Auch verstehe ich die Anwendung der Rekursion dort nicht.

Es ist Quicksort und der Vergleich ist anscheinend richtig.

Ich habe den so in zig Büchern gefunden.

Folgende Variante habe ich auch gefunden, die ich nicht verstehe:

quicksort (links, rechts)

Vergleichswert = A[(rechts-links+1)/2]

// sollte dies nicht einfach A[(links+rechts)/ 2 ] lauten?

do //Warum eine do-while Schleife? Macht das Sinn?

{

r:=rechts;

l:=links;

while (A[r]> Vergleichswert do r:=r-1;

while (A[l] < Vergleichswert do l:= l-1;

/* Ich glaube, dass habe ich verstanden.

* Das stellt doch lediglich die Bewegung der Elemente

* dar, oder? Also wenn das rechte Element größer ist

* als der Vergleichswert, dann gehe ein Element weiter.

* Falls ich das falsch verstanden haben sollte,

* korrigiert mich bitte.

*/

if l < r then tausche (l,r);

// Wieso l < r ?

// Müsste es nicht r < l heißen?

// Ich meine ich tausche doch den kleineren

// rechten Wert mit dem größeren linken Wert.

// Oder verstehe ich das falsch?

while (l < r) ; }

// Warum Solange l < r ?

if (links < r) then quicksort (links, r);

if (rechts > l ) then quicksort(l, rechts);

// An dieser Stelle war meine Verwirrung komplett.

// Ich verstehe hier schon die Rekursion und weiß

// selbstverständlich was eine Rekursion ist.

// Was ich da nicht verstehe, sind die beiden

// If-Bedingungen.

// Warum if (links < r) ?

// Warum if (rechts > l) ?

Dann habe ich noch folgende Variante auf einer Web-Seite gefunden:

Die folgende Funktion quicksort sortiert ein Teilstück des Arrays a vom Index lo bis zum Index hi.

Die Sortierfunktion ist in der Klasse QuickSorter gekapselt. Die Methode sort übergibt das zu sortierende Array an das Array a und ruft quicksort mit dem unteren Index 0 und dem oberen Index a.length-1 auf.

Die hier der Übersichtlichkeit halber verwendete Hilfsfunktion exchange(i, j) vertauscht die Array-Elemente a und a[j].

Die Anweisung zum Sortieren eines Arrays b mit Quicksort lautet

new QuickSorter().sort(;

Es folgt das Programm.

public class QuickSorter

{

private int[] a;

public void sort(int[] a0)

{

a=a0;

quicksort(0, a.length-1);

}

private void quicksort (int lo, int hi)

{

int i=lo, j=hi;

int x=a[(lo+hi)/2];

// Aufteilung

while (i<=j)

{

while (a<x) i++;

while (a[j]>x) j--;

if (i<=j)

{

exchange(i, j);

i++; j--;

}

}

// Rekursion

if (lo<j) quicksort(lo, j);

if (i<hi) quicksort(i, hi);

}

private void exchange(int i, int j)

{

int t=a;

a=a[j];

a[j]=t;

}

} // end class QuickSorter

Könnt ihr mir den erklären?

Ich verstehe den Algorithmus ab hier nicht

do // Warum eine do-while Schleife?

{

while (x < middleElement)

{

i++;

}

while (middleElement < x[j])

{

j--;

}

if (i <= j) //Verstehe ich nicht. Wenn das linke

// Element kleiner gleich den rechten

// Element ist dann mache das.

// Das linke Element muss doch

// kleiner gleich dem rechten Element

// sein, oder?

{

elementType tmp = x;

x = x[j];

x[j] = tmp;

i++;

j--;

}

} while (i <= j)

if (left < j)

{

quick(x, left, j); //Warum vergleiche ich

// links mit dem rechten

// Element?

}

if (i < right) //Und warum vergleiche ich

// rechts mit dem linken

// Element.

{

quick(x, i, right);

}

}

Helft mir! Ich stehe da komplett auf dem Schlauch! :confused:

Aber die Animationen sind genial, wo man genau die Vergleiche und Bewegungen sieht. Danke!! Werde ich sofort weiterempfehlen. :uli

Das Script allerdings auch!

Originally posted by Pönk

Hast du dir eigentlich meinen o.g. link mal angeschaut?

Ich finde es dort sehr ANSCHAULICH dargestellt inclusive Code (denke ist C++, kann aber auch JAVA sein)

Gruß Pönk

Ja habe ich danach gemacht.

Aber wirklich verstehe ich die algorithmen noch nicht.

Die Animation schaue ich mir nochmal in Ruhe an.

Ist wirklich gut.

Das Programm war Java. Aber wirklich verstanden habe ich es nicht.

Irgendwie war die Nachbearbeitungszeit vorbei.

Dumm gelaufen.

Hier mein Post nochmal, der letzte war nämlich nicht komplett.

Ich habe mir gerade mal das Skript von Prof. Kopp durchgelesen bzw. das Quicksort - Verfahren.

Folgendes verstehe ich nicht:

if (right>left)

muss das nicht ungekehrt heißen, also right < left?

Denn wenn rechts hinter dem Pivotelement ein kleineres Element auftaucht vertausche ich es doch mit dem größeren linken Element. Oder verstehe ich das jetzt komplett falsch?

Jedoch haben wir diesen Algorithmus ähnlich geschrieben.

Ich stelle mal zwei Varianten vor und schreibe dran, was ich nicht verstehe.

Erstmal ein ziemlich grober Algorithmus

quicksort (links, rechts)

Vergleichswert = A[(rechts-links+1)/2]

// sollte dies nicht einfach A[(links+rechts)/ 2 ] lauten?

do //Warum eine do-while Schleife? Macht das Sinn?

{

r:=rechts;

l:=links;

while (A[r]> Vergleichswert do r:=r-1;

while (A[l] < Vergleichswert do l:= l-1;

/* Ich glaube, dass habe ich verstanden.

* Das stellt doch lediglich die Bewegung der Elemente

* dar, oder? Also wenn das rechte Element größer ist

* als der Vergleichswert, dann gehe ein Element weiter.

* Falls ich das falsch verstanden haben sollte,

* korrigiert mich bitte.

*/

if l < r then tausche (l,r);

// Wieso l < r ?

// Müsste es nicht r < l heißen?

// Ich meine ich tausche doch den kleineren

// rechten Wert mit dem größeren linken Wert.

// Oder verstehe ich das falsch?

while (l < r) ; }

// Warum Solange l < r ?

if (links < r) then quicksort (links, r);

if (rechts > l ) then quicksort(l, rechts);

// An dieser Stelle war meine Verwirrung komplett.

// Ich verstehe hier schon die Rekursion und weiß

// selbstverständlich was eine Rekursion ist.

// Was ich da nicht verstehe, sind die beiden

// If-Bedingungen.

// Warum if (links < r) ?

// Warum if (rechts > l) ?

Sorry, aber ich bin total am verzweifeln bei den

Sortieralgorithmen.

Wie wichtig sind die eigentlich? Sehr wichtig, oder?

Hier das ganze nochmal als PASCAL-Programm, welches ich auch nicht wirklich verstanden habe.

Bitte helft mir!!!

Kennt einer zufällig noch eine einfache Java-Unsetzung?

Ich lerne eigentlich JAVA, werde aber bei Algorithmen

mit Pascal zugeschmissen.

Ich komme da total durcheinander.

Ich habe mir gerade mal das Skript von Prof. Kopp durchgelesen bzw. das Quicksort - Verfahren.

Folgendes verstehe ich nicht:

if (right>left)

muss das nicht ungekehrt heißen, also right < left?

Denn wenn rechts hinter dem Pivotelement ein kleineres Element auftaucht vertausche ich es doch mit dem größeren linken Element. Oder verstehe ich das jetzt komplett falsch?

Jedoch haben wir diesen Algorithmus ähnlich geschrieben.

Ich stelle mal zwei Varianten vor und schreibe dran, was ich nicht verstehe.

Erstmal ein ziemlich grober Algorithmus

quicksort (links, rechts)

Vergleichswert = A[(rechts-links+1)/2] // sollte dies nicht einfach

Falls es keine Demo gibt, kann man sich das Spiel ja auch erstmal aus der Videothek ausleihen. Ist sowieso sinniger, da man dann wirklich das volle Produkt testen kann.

Eine Demo enthält meist noch viele Fehler.

Danke.

Das Script werde ich mir auf jeden Fall ausdrucken und durchlesen.

Ja ich soll es theoretisch machen.

Hier die Aufgabenstellung:

Wenden Sie die folgenden Sortierverfahren auf das Feld

[36, 6, 11, 14, 6, 22, 29, 30]

an und zählen Sie die Anzahl der benötigten Vergleiche und Bewegungen

a) Direktes Einfügen

Ist das Verfahren stabil?

Direkte Auswahl

Ist das Verfahren stabil?

c) Direkter Austausch

Ist das Verfahren stabil?

d) Shakersort

Ist das Verfahren stabil?

e) Quicksort mit Auswahl des jeweils mittleren Elements als Vergleichswert,

Ist das Verfahren stabil?

f) Quicksort mit Auswahl über Dreiermedian,

Ist das Verfahren stabil?

Ich denke schon, dass ich die Algorithmen verstanden habe.

Ich mache ja auch die gleichen Schritte, wie die anderen.

Jedoch komme ich nicht auf dei Bewegungen und Vergleiche, weil ich nicht weiß wie die die ermittelt (nicht rechnerisch!) haben. Ich weiß nicht, wo die überall Bewegungen und Vergleiche sehen.

Werde hier noch einen Algorithmus vorstellen.

@Funky Funky

Dann kann ich es mir ja doch beruhigt holen, oder?

Mein System:

AMD Athlon 800 MHz

Zwei Platten: 40 und 40 Gig

DVD-ROM

Geforce 2 Graka (64MB)

384 MB RAM

In Informatik hatten wir mal die Aufgabe versch. Sortieralgorithmen (Sortieren durch Einfügen, durch auswahl, Bubblesort etc)

theoretisch auf ein Feld anzuwenden und dann zu ermitteln wieviel Bewegungen und Vergleiche dieser Algorithmus benötigt.

Ich komme da nur nie drauf! Den Algorithmus stumpf auszuführen ist ja nicht das Problem, aber auf die Vergleiche und Bewegungen zu kommen!

Wer kennt sich damit aus und könnte mir helfen? Ich schicke dann auch gerne meine Unterlagen per mail.

Ich habe ein Problem. Wir sollten ein Programm schreiben, welches eine Zahl einliest und ermittelt wie oft diese durch 2 teilbar ist. Dies sollte durch eine While - Schleife geschehen. Jedoch terminiert mein Programm und ich weiß nicht, wo der Fehler ist.

Hier der Programm-Code:

import java.io.*;

public class schleife

{

public static void main(String args[])

throws IOException

{

int zahl = 0;

int teiler = 2;

int c = zahl % teiler;

int d = 0;

BufferedReader din = new BufferedReader(

new InputStreamReader(System.in));

System.out.print("Bitte geben Sie eine Zahl zwischen 1 und 1000 ein: ");

while (c == 0) //Solange der Rest = 0 beträgt

{

zahl = zahl / teiler;

c = zahl % teiler;

d++;

}

System.out.println("Die Zahl " +zahl+ " ist " +d+ " mal durch 2 teilbar");

}

}

Wir habe heute die Musterlösung übers Netz erhalten und es stimmt:

y = x ^n

Doch ich verstehe nicht wieso. Wieso stellt man es so kompliziert dar.

Das geht doch bestimmt einfacher.

Ich meine, wenn man x und n eingelesen hat, kann man dann nicht

einfach dann x ^n nehmen bzw. x so oft multiplizieren wie groß n halt ist.

Oder ist das so in der Schleife dargestellt?

Doch wie?

Anmerkung: Ich stehe erst ganz am Anfang und brauche training.

Wie ist das denn dargestellt und wieso wird berücksichtigt, dass k ungerade bzw gerade ist.

Ich meine, das passt doch gar nicht. Wo übersehe ich was?

Kurz:

Ich verstehe die Schleife in dem Programm nicht.

Aha. Wird schon etwas klarer....

Mit der Potenz hatte ich auch schon im Hinterkopf.

Aber bei mir hat das nie gepasst. Aber vielleicht habe ich mich auch beim Einsetzen vertan.

Nun denn. Ich danke dir.

Ich studiere gerade Wirtschaftsinformatik im ersten Semester.

Dort nehmen wir unter anderem in der Einführung in der Informatik

Java Programmierung und halt auch die Analyse und Entwürfe von Algorithmen durch.

Ich habe allerdings nicht das Problem Struktogramme oder PAPs zu erstellen.

Bei mir liegt das Problem in der Analyse und dem Entwerfen von Algorithmen.

Irgendwie blicke ich dann nicht durch.

Ich gebe euch mal ein Beispiel zur Analyse:

lies n E IN ein (Element der natürlichen Zahlen)

lies x E IN

setze k = n

setze y = 1

setze z = x

SOLANGE k ungleich 0 TUE

    WENN k ungerade DANN

        setze k = k - 1

        setze y = y * z

    setze k = k div 2

    setze z = z * z

gib y aus

Was berechnet dieser Algorithmus?

Hat jemand eine Idee? Wie geht ihr denn da vor? Zum Beispiel bei dieser Aufgabe.

Gibt es eigentlich zu diesem Thema ein Buch, wo auch Aufgaben mit Lösungen

enthalten sind?

(Edit: CODE-Tags eingefügt, damit die Einrückung erkennbar ist | Klotzkopp)

Also ich kann mit heinrichg voll mit fühlen.

Ich studiere gerade Wirtschaftsinformatik im ersten Semester.

Dort nehmen wir unter anderem in der Einführung in der Informatik

Java Programmierung und halt auch die Analyse und Entwürfe von Algorithmen durch.

Ich habe allerdings nicht das Problem Struktogramme oder PAPs zu erstellen.

Bei mir liegt das Problem in der Analyse und dem Entwerfen von Algorithmen.

Irgendwie blicke ich dann nicht durch.

Ich gebe euch mal ein Beispiel zur Analyse:

[I] lies n E IN ein (Element der natürlichen Zahlen)

lies x E IN

setze k = n

setze y = 1

setze z = x

SOLANGE k ungleich 0 TUE

      WENN k ungerade DANN

                     setze k = k - 1

                     setze y = y * z

              setze k = k div 2

              setze z = z * z

gib y aus

Was berechnet dieser Algorithmus?

Hat jemand eine Idee? Wie geht ihr denn da vor? Zum Beispiel bei dieser Aufgabe.

Gibt es eigentlich zu diesem Thema ein Buch, wo auch Aufgaben mit Lösungen

enthalten sind?

(Edit: CODE-Tags eingefügt, damit die Einrückung erkennbar ist | Klotzkopp)