001    package de.hska.info1.sortieren;
002    
003    
004    /**
005     * Enthät Implementierungsvarianten von
006     * Sortieren durch direktes Einfügen.
007     * <p/>
008     * Alle haben einen Zeitaufwand im besten Fall von O(n) und
009     * O(n<sup>2</sup>) sonst.
010     * 
011     * @author Christian Pape
012     */
013    public class DirektesEinfuegen implements Sortieren {
014    
015            /**
016             * Implementierungsvariante, die aus folgenden
017             * Verfeinerungsschritten innerhalb der äusseren
018             * for-Schleife entstanden ist:
019             * <ul>
020             *   <li>Position j suchen, an dem a[i] eingefügt werden soll</li>
021             *   <li>a[i] zwischenspeichern (da es sonst überschrieben wird)</li>
022             *   <li>Alle Elemente a[j] ... a[i - 1] eins nach rechts verschieben</li>
023             *   <li>Zwischengespeicherten Wert von a[i] nach a[j] kopieren.</li>
024             * </ul>
025             * Hat im mittleren und schlechtesten Fall einen Zeitaufwand von O(n*n),
026             * im besten Fall O(n) bei fast aufsteigend sortierten Feldern.
027             */
028            public void sortieren(int [] a) {
029                    for (int i = 1; i < a.length; i++) {
030                            int j = i;
031                            int t = a[i];
032                            while( j > 0 && a[j - 1] > t ) {
033                                    j--;
034                                    // Binärsuche wäre auch möglich
035                            }
036                            for (int k = i - 1; k >= j; k--) {
037                                    a[k + 1] = a[k];
038                            }
039                            a[j] = t;
040                    }
041            }
042    
043            /**
044             * <p>Verbesserte Variante, bei der das nächste zu betrachtende
045             * Elemente durch Vertauschen mit dem linken grösseren Nachbarn
046             * bis an die richtige Stelle von rechts nach links "durchrutscht".
047             * <p/>
048             * <p>Hat im mittleren und schlechtesten Fall einen Zeitaufwand von O(n*n),
049             * im besten Fall O(n) bei fast aufsteigend sortierten Feldern.</p>
050         *
051             */
052            public void sortieren1(int [] a) {
053                    for (int i = 1; i < a.length; i++) {
054                            for (int j = i; j > 0 && a[j - 1] > a[j]; j--) {
055                                    int t = a[j];
056                                    a[j] = a[j - 1];
057                                    a[j - 1] = t;
058                            }
059                    }
060            }
061    
062            public static void main(String [] argv) {
063                    DirekteAuswahl direkteAuswahl = new DirekteAuswahl();
064                    Zeitmessen.zeitmessen(direkteAuswahl);
065            }
066    }