Given an unordered sequence of items, rearrange them so that they are in non-decreasing order. (Or non-increasing)
[7, 1, 3, 21, 3] \(\rightarrow\) [1, 3, 3, 7, 21]There are many sorting algorithms, each with strengths and weaknesses.
Insertion sort implementation from our textbook:
private static void insertionSort(int[] numbers) {
for (int i = 1; i < numbers.length; i++) {
int j = i;
while (j > 0 && numbers[j] < numbers[j - 1]) {
// Swap numbers[j] and numbers [j - 1]
int temp = numbers[j];
numbers[j] = numbers[j - 1];
numbers[j - 1] = temp;
j--;
}
}
}Selection Sort implementation from our textbook:
private static void selectionSort(int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) {
// Find index of smallest remaining element
int indexSmallest = i;
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[j] < numbers[indexSmallest]) {
indexSmallest = j;
}
}
// Swap numbers[i] and numbers[indexSmallest]
int temp = numbers[i];
numbers[i] = numbers[indexSmallest];
numbers[indexSmallest] = temp;
}
}