de.hska.java.aufgaben.sortieren
Class NatuerlichesMischen

java.lang.Object
  de.hska.java.aufgaben.sortieren.NatuerlichesMischen

All Implemented Interfaces:

Sortieren

public class NatuerlichesMischen
extends java.lang.Object
implements Sortieren

Natürliches Mischen ist eine Verbesserung der nicht-rekursiven Variante von Mergesort bzw. Direktem Mischens. Bim natürlichen Mischen wird nicht mit stetig grösser werdener Schrittweite von 2, 4, 8, ..., 2^log₂(n) sondern mit variabler Schrittweite: Es werden immer die nächsten beiden aufsteigend sortierten Folgen verschmolzen.

In der Folge 7 4 6 3 1 2 8 5

werden anfangs die ersten beiden enthaltenen aufsteigend sortierten Folgen 7 und 4 6 verschmolzen, dann 3 mit 1 2 und zuletzt 8 und 5. Dies wird solange wiederholt, bis das Feld aufsteigend sortiert ist. Wir demonstrieren das obiger Folge, die aufsteigend sortierten Bereiche sind mit | voneinander separiert.

 7 | 4 6 | 3 |1  2 | 8 | 5
 4 6 7 | 3 | 1 2 | 8 | 5
 4 6 7   1 2 3 | 8 | 5
 4 6 7 1 2 3 5 8
 
 4 6 7 | 1 2 3 | 5 8
 1 2 3 4 6 7 | 5 8
 
 1 2 3 4 5 6 7 8
 

Im besten Fall hat mein ein bereits aufsteigend sortiertes Feld, der Zeitaufwand beträgt O(n). Im schlimmsten Fall können wir natürlich nicht besser werden als O(n log₂n ). Durch die erhöhte Anzahl von Vergleichen ist dieser Algorithmus aber in der Praxis vermutlich langsamer als Direktes Mischen.

Zurück zum Aufgabentext

Author:

pape

Constructor Summary

NatuerlichesMischen()

Method Summary

void	sortieren(int[] a) Sortiert die Zahl in a aufsteigend mit Natürlichem Mischen.

Methods inherited from class java.lang.Object

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

Constructor Detail

NatuerlichesMischen

public NatuerlichesMischen()

Method Detail

sortieren

public void sortieren(int[] a)

Sortiert die Zahl in a aufsteigend mit Natürlichem Mischen.

Specified by:

sortieren in interface Sortieren