Сортировка вставками (*-*)

#	User	Rating
1	tourist	3947
2	jiangly	3740
3	Radewoosh	3652
4	Benq	3626
5	jqdai0815	3620
6	orzdevinwang	3612
7	ecnerwala	3587
8	Geothermal	3569
8	cnnfls_csy	3569
10	ksun48	3485

#	User	Contrib.
1	awoo	163
2	maomao90	160
3	adamant	156
4	atcoder_official	155
4	nor	155
6	cry	153
7	-is-this-fft-	152
7	maroonrk	152
9	SecondThread	148
10	Petr	146

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

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

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

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

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

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

Решение

#include <bits/stdc++.h>

#define int long long
using namespace std;


signed main() {
    int n, max_s;
    cin >> n >> max_s;
    vector<int> x(n); // массив на n элементов
    for (int i = 0; i < n; ++i) {
        cin >> x[i]; // ввод элементов
    }
    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]); // меняем местами
        }
    }
    int sum = 0; // наша сумма 
    for (int i = n - 1; i >= n - max_s; --i) { // 
        if (sum + x[i] > sum){ // так как предметы могут быть отрицательными, то проверяем, что мы взяли положительный
            sum += x[i];
        }

    }
    cout << sum;
    return 0;
}

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

master_flomaster's blog