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]
We will assume (for now) that sorting algorithms can only compare keys and assign them to new locations.
Sorting is an important problem… Many many algorithms require that we work with ordered collections of data.
There are many sorting algorithms, each with strengths and weaknesses.
Insertion sort implementation from our textbook:
public void insertionSort(T[] items) {
for (int i = 1; i < items.length; i++) { // Insert i'th record
for (int j = i; (j > 0) && (items[j].compareTo(items[j - 1]) < 0); j--) {
swap(items, j, j - 1);
}
}
}
public void swap(T[] items, int i, int j) {
T tmp = items[i];
items[i] = items[j];
items[j] = tmp;
}Selection Sort implementation from our textbook:
public void selectionSort(T[] items) {
for (int i = 0; i < items.length - 1; i++) { // Select i'th biggest record
int bigindex = 0; // Current biggest index
for (int j = 1; j < items.length - i; j++) { // Find the max value
if (items[j].compareTo(items[bigindex]) > 0) { // Found something bigger
bigindex = j; // Remember bigger index
}
}
swap(items, bigindex, items.length - i - 1); // Put it into place
}
}