Sorting: selection and insertion sort
Упорядочивание массива
- Сортировка означает упорядочивание значений массива, обычно от меньших к большим.
- На экзамене AP CSA вы должны уметь писать и трассировать две сортировки: сортировку выбором и сортировку вставками.
- Вам также нужно трассировать (но не писать) третью сортировку: сортировку слиянием. Здесь мы рассмотрим все три.
Сортировка выбором: идея
- Пройдите по массиву слева направо.
- На каждой позиции
iнайдите наименьшее значение в той части массива, которая еще не отсортирована (отiдо конца). - Поменяйте местами это наименьшее значение с позицией
i. Теперь элемент на позиции0..iотсортирован. - Повторяйте, пока весь массив не будет упорядочен.
public class Sorter {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // index of smallest so far
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // found a smaller value
}
}
int temp = a[min]; // swap a[i] and a[min]
a[min] = a[i];
a[i] = temp;
}
}
}
Сортировка выбором: трассировка
- Отсортируем
{5, 2, 4, 1, 3}. Часть слева от|уже отсортирована. - На каждом проходе выбирается наименьшее значение из оставшейся части и меняется местами с первым элементом.
start: [5, 2, 4, 1, 3]
i=0 smallest=1 → swap a[0],a[3]: [1 | 2, 4, 5, 3]
i=1 smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2 smallest=3 → swap a[2],a[4]: [1, 2, 3 | 5, 4]
i=3 smallest=4 → swap a[3],a[4]: [1, 2, 3, 4 | 5]
done: [1, 2, 3, 4, 5]
Сортировка вставками: идея
- Представьте, что вы держите игральные карты и добавляете одну карту за раз на правильное место.
- Начните с индекса
1. Назовите это значение ключом. - Сдвиньте большие значения слева на один шаг вправо, пока ключ не займет свое место.
- Поместите ключ на освободившееся место. Теперь всё, что слева, отсортировано.
public class Sorter {
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i]; // the value to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger values right
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key; // drop key into the gap
}
}
}
Сортировка вставками: трассировка
- Сортируем
{5, 2, 4, 1, 3}снова. Часть слева от|остается отсортированной по мере продвижения. key— это значение, которое мы вставляем на каждом проходе.
start: [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2: [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4: [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3: [1, 2, 3, 4, 5]
done: [1, 2, 3, 4, 5]
Сортировка слиянием: только трассировка
- Сортировка слиянием использует рекурсию (урок 15). Вы не пишете её на экзамене, но должны трассировать.
- Разделите массив пополам снова и снова, пока каждый кусочек не будет содержать одно значение.
- Объединяйте пары кусочков обратно, всегда сохраняя их в порядке.
Сортировка слиянием: трассировка
- Одно значение уже «отсортировано». Объединение двух отсортированных частей дает большую отсортированную часть.
split: [5, 2, 4, 1]
[5, 2] [4, 1]
[5] [2] [4] [1]
merge: [2, 5] [1, 4]
merge: [1, 2, 4, 5]
- Сортировка выбором и сортировка вставками медленны на больших массивах (они выполняют около n² шагов).
- Сортировка слиянием быстрее на больших массивах (около n·log n шагов). Вот почему она важна.
Распространенные ошибки
- И сортировка выбором, и сортировка вставками имеют сложность O(n²).
- Трассируйте маленький массив вручную, чтобы проверить свою сортировку.
Теперь попробуйте сами
- Каждое задание содержит скелет метода с TODO. Отсортируйте массив на месте (измените сам
a). - Скрытый Харнес (Harness) сортирует несколько массивов и проверяет результат.
- Используйте Check answer (Проверить ответ), чтобы скомпилировать ваш код с предоставленными тестами и посмотреть результаты. Сохраните интерфейс класса и метода, показанный в стартере.
Selection / insertion sort
Sorting compares and swaps until the list is ordered.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Complete selectionSort(int[] a) so it sorts the array in place from small to large, using selection sort. The checker tests several arrays.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Complete insertionSort(int[] a) so it sorts the array in place from small to large, using insertion sort. The checker tests several arrays.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Complete isSorted(int[] a) returning true if the array is in order from small to large (each item is <= the next), else false. An empty or one-item array counts as sorted.
Нажмите Запустить, чтобы увидеть результат здесь.