Insertion Sort
Implementierung
package net.bitelligence.training.exercise.sorting.insertion_sort;
public class InsertionSort {
/**
* This method sorts an array of integers using the insertion sort algorithm.
* The method iterates through the array, comparing each element to the one before it
* and swapping them if necessary to maintain the ascending order.
*
* @param numbers The array of integers to be sorted
* @return The sorted array of integers
*/
public int[] sort(int[] numbers) {
// ...
return numbers;
}
}package net.bitelligence.training.exercise.sorting.insertion_sort;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
public class InsertionSortTest {
@Test
public void should_correctly_sort_mixed_arrays() {
int[] unsorted1 = {};
int[] unsorted2 = { 1 };
int[] unsorted3 = { 2, 1 };
int[] unsorted4 = { 2, 1, 3 };
int[] unsorted5 = { 2, 4, 1, 3 };
int[] unsorted6 = { 2, 1, 2, 3, 9 };
int[] unsorted7 = { 1, 2, 3, 4, 5, 6 };
int[] expected1 = {};
int[] expected2 = { 1 };
int[] expected3 = { 1, 2 };
int[] expected4 = { 1, 2, 3 };
int[] expected5 = { 1, 2, 3, 4 };
int[] expected6 = { 1, 2, 2, 3, 9 };
int[] expected7 = { 1, 2, 3, 4, 5, 6 };
assertArrayEquals(expected1, new InsertionSort().sort(unsorted1));
assertArrayEquals(expected2, new InsertionSort().sort(unsorted2));
assertArrayEquals(expected3, new InsertionSort().sort(unsorted3));
assertArrayEquals(expected4, new InsertionSort().sort(unsorted4));
assertArrayEquals(expected5, new InsertionSort().sort(unsorted5));
assertArrayEquals(expected6, new InsertionSort().sort(unsorted6));
assertArrayEquals(expected7, new InsertionSort().sort(unsorted7));
}
}package net.bitelligence.training.exercise.sorting.insertion_sort;
public class InsertionSort {
/**
* This method sorts an array of integers using the insertion sort algorithm.
* The method iterates through the array, comparing each element to the one before it
* and swapping them if necessary to maintain the ascending order.
*
* @param numbers The array of integers to be sorted
* @return The sorted array of integers
*/
public int[] sort(int[] numbers) {
for (int i = 1; i < numbers.length; i++) {
int number = numbers[i];
int j = i;
// Shift numbers to the right until the current number found its position
while (j > 0 && number < numbers[j - 1]) {
numbers[j] = numbers[j - 1];
j--;
}
numbers[j] = number;
}
return numbers;
}
}public class InsertionSort {
/**
* This method sorts an array of integers using the insertion sort algorithm.
* The method iterates through the array, comparing each element to the one before it
* and swapping them if necessary to maintain the ascending order.
*
* @param numbers The array of integers to be sorted
* @return The sorted array of integers
*/
public int[] sort(int[] numbers) {
for (int i = 1; i < numbers.length; i++) {
for (int j = i; j > 0; j--) {
if (numbers[j] < numbers[j-1]) {
int temp = numbers[j];
numbers[j] = numbers[j-1];
numbers[j-1] = temp;
}
}
}
return numbers;
}
}Funktionsweise
Der Insertion Sort Algorithmus ist ein einfacher und effizienter Sortieralgorithmus, der auf einer einfachen Idee basiert: Ein vorläufig sortiertes Array wird Schritt für Schritt erweitert, indem neue Elemente an der richtigen Stelle eingefügt werden.
Im Detail funktioniert der Algorithmus wie folgt:
Das erste Element des Arrays gilt als sortiert und wird als ein eigenständiger, sortierter Teil betrachtet.
Das nächste Element wird betrachtet und mit dem ersten Element verglichen. Wenn das nächste Element größer als das erste ist, bleibt es an seiner Stelle. Wenn es kleiner ist, wird es mit dem ersten Element vertauscht.
Der Prozess wird fortgesetzt, indem das dritte Element betrachtet wird und mit den bereits sortierten Elementen verglichen wird. Wenn es kleiner ist als eines der bereits sortierten Elemente, wird es an die richtige Stelle eingefügt.
Der Prozess wiederholt sich für jedes Element im Array, bis das gesamte Array sortiert ist.
Hilfestellung
Tipp #1
Verstehen Sie die Grundidee des Algorithmus: Der Insertion sort funktioniert, indem das Array durchlaufen wird und jedes Element an die richtige Position im sortierten Teil des Arrays eingefügt wird. Der sortierte Teil des Arrays beginnt mit dem ersten Element und wächst in jeder Iteration um ein Element.
Tipp #2
Implementieren Sie den Vergleich und das Einfügen korrekt: Stellen Sie sicher, dass Sie die Elemente im Array richtig miteinander vergleichen und sie korrekt einfügen, falls notwendig.
Optional
Optimieren Sie den Algorithmus: Der Insertion sort hat eine Zeitkomplexität von O(n²) im schlechtesten und O(n) im besten Fall. Es gibt jedoch Möglichkeiten, den Algorithmus zu optimieren, z.B. durch die Verwendung von Binary Search beim Einfügen der Elemente um die Anzahl der Vergleiche zu reduzieren.