Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Insertionsort

No description
by

Sarah Larschow

on 26 November 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Insertionsort

Einfache Erklärung Im Grunde kann man sich den Insertionsort so vorstellen: Man hat eine Reihe von Zahlen (7 ; 3 ; 5 ; 0 ; 6 ; 1 ; 2 ; 4), die sich in der Reihenfolge von klein nach groß sortieren sollen.
Es beginnt die erste Zahl, also in unserem Beispiel die 7. Diese vergleicht sich mit ihrem Nachbarn, also der 3. Da die drei kleiner ist als die 7 tauschen die beiden ihre Plätze. Dann überprüft die 3 ob ihr rechter Partner kleiner ist als sie. In diesem Fall hat sie keinen also bleibt sie an ihrem Platz. Neue Reihenfolge: (3 ; 7 ; 5 ; 0 ; 6 ; 1 ; 2 ; 4). Jetzt kommt die 5 ins Spiel. Sie überprüft wieder ob sie kleiner ist als die 7. Das ist sie und somit tauschen sie die Plätze. Nun vergleicht sich die 5 mit der 3, da die 5 aber nicht kleiner ist bleibt die 5 an ihrem Platz.
Neue Reihenfolge: (3 ; 5 ; 7 ; 0 ; 6 ; 1 ; 2 ; 4). engl.: insertion "Einfügen" und sort "sortieren"
Insertionsort ist ein elementares Sortier­verfahren. Sehr gut geeignet ist es für das Sortieren von kleinen Datenmengen oder für das Einfügen von weiteren Elementen in eine schon sortierte Folge.


Insertionsort im Struktogramm Insertionsort im Java-Code Erklärung zum Java-Code - In Punkt 1 wird die for-Schleife definiert.
- In Punkt 2 wird der einzusortierender_wert für den Java-Code gespeichert.
- In Punkt 3 nimmt der Wert j den Wert i an.
- In Punkt 4 werden die beiden Werte verglichen.
- In Punkt 5 und 6 werden die Werte vertauscht, falls A[i] kleiner ist als der verglichene Wert j
- In Punkt 7 nimmt der alte Wert A[i] den neuen Wert j an Insertionsort
Video-Beispiel In diesem Struktogramm wird
der Insertionsort nochmals dargestellt. (h) ist der betrachtete Wert.
Das Element (h) wird eingefügt, indem die größeren Elemente (a[x]) um eine Position nach rechts geschoben werden. Wenn (h) kleiner ist als (a[ x ]) wird das Element (h) auf dem frei gewordenen Platz (a[ j ]) eingefügt wird.

INSERTIONSORT(A)
1 for i --> 2 to Länge(A)
2 einzusortierender_wert --> A[i]
3 j --> i
4 while j > 1 and A[j-1] > einzusortierender_wert
5 A[j] --> A[j - 1]
6 j --> j − 1
7 A[j] einzusortierender_wert

(Dieser Java-Code ist ein Pseudocode)



http://de.wikipedia.org/wiki/Insertionsort

http://www.qsl.net/d/dg1xpz/programm/java/insertion.html

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertion.htm Quellen:
Full transcript