Пора углубляться в сортировки и после сортировки пузырьком мы изучим сортировку вставками.
На самом деле, если вам кажется, что сортировка вставками намного быстрее, чем сортировка пузырьком, то вы заблуждаетесь) Потому что если у нас массив изначально отсортирован по убыванию, и мы, когда запустим сортировку вставками от такого массива (а наша сортировка сортирует по возрастанию), то асимптотика такого алгоритма будет O(N * N), потому что каждый новый неотсортированный элемент мы будет засовывать в начало массива => пробегаться по всему массиву заново.
Вот код:
int n = 5; // количество элементов в массиве
vector<int> x = {8, 1, 3, 4, 0}; // сам массив
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && x[j - 1] > x[j]; j--) { // пока j > 0 и элемент j-1 > j
swap(x[j - 1], x[j]); // меняем местами
}
}
// Вывод массива
for (int i = 0; i < n; ++i) {
cout << x[i] << " ";
}
Я решил еще решить задачку с помощью метода сортировки вставками:
Я бы порекомендовал бы вам самим попробовать решить эту задачку именно методом сортировки вставками, но кто вообще слушает рекомендации?)
На этом все, надеюсь вам было интересно :)
Comments (0)
