Блог пользователя master_flomaster

Автор master_flomaster, история, 3 года назад, По-русски

Пора углубляться в сортировки и после сортировки пузырьком мы изучим сортировку вставками.

Как работает эта сортировка?

На самом деле, если вам кажется, что сортировка вставками намного быстрее, чем сортировка пузырьком, то вы заблуждаетесь) Потому что если у нас массив изначально отсортирован по убыванию, и мы, когда запустим сортировку вставками от такого массива (а наша сортировка сортирует по возрастанию), то асимптотика такого алгоритма будет 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] << " ";
}

Я решил еще решить задачку с помощью метода сортировки вставками:

Ссылка на задачу

Я бы порекомендовал бы вам самим попробовать решить эту задачку именно методом сортировки вставками, но кто вообще слушает рекомендации?)

Решение

На этом все, надеюсь вам было интересно :)

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится