de.hska.info1.sortieren
Class DirektesEinfuegen

java.lang.Object
  de.hska.info1.sortieren.DirektesEinfuegen

All Implemented Interfaces:

Sortieren

public class DirektesEinfuegen
extends java.lang.Object
implements Sortieren

Enthät Implementierungsvarianten von Sortieren durch direktes Einfügen.

Alle haben einen Zeitaufwand im besten Fall von O(n) und O(n²) sonst.

Author:

pape

Constructor Summary

DirektesEinfuegen()

Method Summary

static void	main(java.lang.String[] argv)
void	sortieren(int[] a) Implementierungsvariante, die aus folgenden Verfeinerungsschritten innerhalb der äusseren for-Schleife entstanden ist: Position j suchen, an dem a[i] eingefügt werden soll a[i] zwischenspeichern (da es sonst überschrieben wird) Alle Elemente a[j] ... a[i - 1] eins nach rechts verschieben Zwischengespeicherten Wert von a[i] nach a[j] kopieren.
void	sortieren1(int[] a) Verbesserte Variante, bei der das nächste zu betrachtende Elemente durch Vertauschen mit dem linken grösseren Nachbarn bis an die richtige Stelle von rechts nach links "durchrutscht".

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DirektesEinfuegen

public DirektesEinfuegen()

Method Detail

sortieren

public void sortieren(int[] a)

Implementierungsvariante, die aus folgenden Verfeinerungsschritten innerhalb der äusseren for-Schleife entstanden ist:

• Position j suchen, an dem a[i] eingefügt werden soll
• a[i] zwischenspeichern (da es sonst überschrieben wird)
• Alle Elemente a[j] ... a[i - 1] eins nach rechts verschieben
• Zwischengespeicherten Wert von a[i] nach a[j] kopieren.

Hat im mittleren und schlechtesten Fall einen Zeitaufwand von O(n*n), im besten Fall O(n) bei fast aufsteigend sortierten Feldern.

Specified by:

sortieren in interface Sortieren

sortieren1

public void sortieren1(int[] a)

Verbesserte Variante, bei der das nächste zu betrachtende Elemente durch Vertauschen mit dem linken grösseren Nachbarn bis an die richtige Stelle von rechts nach links "durchrutscht".

Hat im mittleren und schlechtesten Fall einen Zeitaufwand von O(n*n), im besten Fall O(n) bei fast aufsteigend sortierten Feldern.

main

public static void main(java.lang.String[] argv)