Управление
Сравнений
0
Обменов
0
Шагов
0
Визуализация
Нажмите «Запустить» или «Шаг».
Идея алгоритма
Пузырьковая сортировка
for (j = 1; j < n; j++)
for (i = 0; i < n - j; i++)
if (y[i] > y[i+1]) {
b = y[i];
y[i] = y[i+1];
y[i+1] = b;
}Сортировка выбором
for (j = 1; j < n; j++) {
for (max = y[0], nom = 0, i = 1; i <= n - j; i++)
if (y[i] > max) { max = y[i]; nom = i; }
// обмен с последним элементом неотсортированной части
b = y[n-j]; y[n-j] = y[nom]; y[nom] = b;
}Сортировка вставкой
for (i = 1; i < n; i++)
for (b = y[i], j = i - 1; j >= 0 && b < y[j]; y[j+1] = y[j--])
;
// вставка b в позицию j+1Задание
- Запустите все три алгоритма на массиве из 12 элементов. Сравните число сравнений и обменов.
- Как меняется количество операций для пузырьковой сортировки на уже отсортированном массиве? На обратно отсортированном?
- Почему сортировка вставкой в среднем работает быстрее «пузырька», хотя обе O(n²)?
- Модифицируйте сортировку «пузырьком» так, чтобы она завершалась, если массив уже отсортирован (см. вариант 1 в теории).