001    package de.hska.info1.sortieren;
002    
003    /**
004     * Enthält Implementierungsvarianten von Bubblesort.
005     * 
006     * @author Christian Pape
007     */
008    public class Bubblesort implements Sortieren {
009            
010            /**
011             * Sortiert mit Bubblesort.
012             * Hat O(n*n) Zeitaufwand in jedem Fall.
013             */
014            public void sortieren1(int [] a) {
015                    for (int i = 0; i < a.length - 1; i++) {
016                            for (int j = a.length - 1; j > i  ; j--) {
017                                    if (a[j - 1] > a[j]) {
018                                            int t = a[j];
019                                            a[j] = a[j-1];
020                                            a[j-1] = t;
021                                    }
022                            }
023                    }
024            }
025            
026            /**
027             * Sortiert mit verbesserter Variante von Bubblesort.
028             * Hat O(n*n) Zeitaufwand im schlechtesten und mittleren Fall,
029             * jedoch O(n) im besten Fall (bei fast aufsteigend sortierten 
030             * Felder).
031             */
032            public void sortieren(int [] a) {
033                    boolean istSortiert = false;
034                    for (int i = 0; ! istSortiert && i < a.length - 1; i++) {
035                            istSortiert = true;
036                            for (int j = a.length - 1; j > i  ; j--) {
037                                    if (a[j - 1] > a[j]) {
038                                            int t = a[j];
039                                            a[j] = a[j-1];
040                                            a[j-1] = t;
041                                            istSortiert = false;
042                                    }
043                            }
044                    }
045            }
046    
047    }