import java.util.Arrays; public class InsertionSort { /** * Der klassische Insertion-Sort. * * @param numbers * diese ganzen Zahlen werden aufsteigend sortiert. */ public static void sort(int[] numbers) { for (int len = 1; len < numbers.length; len++) { // Suche das erste Element das gr�sser ist als numbers[len] for (int i = 0; i < len; i++) { if (numbers[i] > numbers[len]) { // Dann sind wir fertig und f�gen numbers[len] an der // Stelle i ein insert(numbers, i, numbers[len], len); break; } } // jetzt sind len+1 Elemente sortiert } assert isOrdered(numbers); } /** * F�ge ein Element in ein Pr�fix eines Arrays ein. * * @param numbers * in dieses Array wird eingef�gt. * @param index * an dieser Stelle wird eingef�gt, die nachfolgenden Elemente * bis (exklusive) len werden um eins nach hinten * verschoben. * @param element * der einzuf�gende Wert. * @param len * L�nge des Pr�fixes. Alle elemente vor len (und ab * index) werden verschoben, element len selbst * wird �berschrieben. */ private static void insert(int[] numbers, int index, int element, int len) { assert index < len && len < numbers.length; for (int i = len; i > index; i--) { numbers[i] = numbers[i - 1]; } numbers[index] = element; } public static void main(String[] args) { int[] numbers = { 3, 4, 3, 2, 1 }; System.out.println("Davor: " + Arrays.toString(numbers)); sort(numbers); System.out.println("Danach: " + Arrays.toString(numbers)); } //---------------------- Pr�dikate f�r Assertions public static boolean isOrdered(int[] a) { for (int i = 0; i < a.length - 1; i++) { if (!(a[i] <= a[i + 1])) { return false; } } return true; } }