Selection Sort
Implementierung
package net.bitelligence.training.exercise.sorting.selection_sort;
public class SelectionSort {
/**
* This method sorts an array of integers using the selection sort algorithm.
* Selection sort is a simple sorting algorithm that finds the smallest element
* in an unsorted array and swaps it with the first element.
* This process is repeated until the entire array is sorted.
*
* @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.selection_sort;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
class SelectionSortTest {
@Test
public void should_correctly_sort_mixed_arrays() {
final int[] unsorted1 = {};
final int[] unsorted2 = { 1 };
final int[] unsorted3 = { 2, 1 };
final int[] unsorted4 = { 2, 1, 3 };
final int[] unsorted5 = { 2, 4, 1, 3 };
final int[] unsorted6 = { 2, 1, 2, 3, 9 };
final int[] unsorted7 = { 1, 2, 3, 4, 5, 6 };
final int[] expected1 = {};
final int[] expected2 = { 1 };
final int[] expected3 = { 1, 2 };
final int[] expected4 = { 1, 2, 3 };
final int[] expected5 = { 1, 2, 3, 4 };
final int[] expected6 = { 1, 2, 2, 3, 9 };
final int[] expected7 = { 1, 2, 3, 4, 5, 6 };
assertArrayEquals(expected1, new SelectionSort().sort(unsorted1));
assertArrayEquals(expected2, new SelectionSort().sort(unsorted2));
assertArrayEquals(expected3, new SelectionSort().sort(unsorted3));
assertArrayEquals(expected4, new SelectionSort().sort(unsorted4));
assertArrayEquals(expected5, new SelectionSort().sort(unsorted5));
assertArrayEquals(expected6, new SelectionSort().sort(unsorted6));
assertArrayEquals(expected7, new SelectionSort().sort(unsorted7));
}
}package net.bitelligence.training.exercise.sorting.selection_sort;
public class SelectionSort {
/**
* This method sorts an array of integers using the selection sort algorithm.
* Selection sort is a simple sorting algorithm that finds the smallest element
* in an unsorted array and swaps it with the first element.
* This process is repeated until the entire array is sorted.
*
* @param numbers The array of integers to be sorted
* @return The sorted array of integers
*/
public int[] sort(int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[j] < numbers[minIndex])
minIndex = j;
}
int temp = numbers[i];
numbers[i] = numbers[minIndex];
numbers[minIndex] = temp;
}
return numbers;
}
}Funktionsweise
Der Selection sort ist ein einfacher Sortieralgorithmus, der das Array in zwei Teile aufteilt: den sortierten Teil und den unsortierten Teil. Der Algorithmus wählt iterativ das kleinste (oder größte) Element aus dem unsortierten Teil des Arrays aus und tauscht es mit dem ersten Element des unsortierten Teils, sodass es zum ersten Element des sortierten Teils wird. Durch das wiederholte Auswählen des kleinsten Elements wird der unsortierte Teil des Arrays nach und nach kleiner, bis das gesamte Array sortiert ist.
Hilfestellung
Tipp #1
Verstehen Sie die Grundidee des Algorithmus: Der Selection sort funktioniert, indem das Array durchlaufen wird und das kleinste Element im unsortierten Teil des Arrays ausgewählt und an die erste Position des unsortierten Teils des Arrays verschoben wird. Der unsortierte Teil des Arrays wird in jeder Iteration kleiner, bis das gesamte Array sortiert ist.
Tipp #2
Implementieren Sie die Auswahl und das Tauschen korrekt: Stellen Sie sicher, dass Sie das kleinste Element im unsortierten Teil des Arrays richtig auswählen und es korrekt mit dem ersten Element im unsortierten Teil des Arrays tauschen.
Optional
Optimieren Sie den Algorithmus: Der Selection sort hat eine Zeitkomplexität von O(n²) in jedem Fall.
Es gibt jedoch Möglichkeiten, den Algorithmus zu optimieren, z.B. durch die Verwendung von Heaps, um das Minimum zu finden, oder durch das Vermeiden von Tauschoperationen, indem man nur den Index des Minimums merkt und am Ende nur einmal tauscht.