Grade 9 · Sorting and searchingCitește în română

Insertion sort

Original: Sortarea prin inserție

O(n²)C++1748 lines1 example

The idea

Like arranging playing cards in your hand: the first i - 1 elements are already sorted, and v[i] is inserted in its place among them. We save v[i] in x and shift to the right the elements larger than x, then put x in the gap left behind.

Original description (Romanian)

Ca la aranjarea cărților de joc în mână: primele i - 1 elemente sunt deja sortate, iar v[i] este inserat la locul lui printre ele. Salvăm v[i] în x și mutăm la dreapta elementele mai mari decât x, apoi punem x în golul rămas.

Complexity
O(n²) in the worst case, O(n) if the array is almost sorted
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

6
5 2 9 1 5 6

Expected output

1 2 5 5 6 9

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

sortare-prin-insertie.cpp
/*
 * Titlu: Sortarea prin inserție
 * Clasa: 9
 * Capitol: Sortare și căutare
 * Descriere: Ca la aranjarea cărților de joc în mână: primele i - 1 elemente
 *            sunt deja sortate, iar v[i] este inserat la locul lui printre ele.
 *            Salvăm v[i] în x și mutăm la dreapta elementele mai mari decât x,
 *            apoi punem x în golul rămas.
 * Complexitate: O(n²) în cazul cel mai rău, O(n) dacă vectorul e aproape sortat
 *
 * Exemplu
 * Intrare:
 * 6
 * 5 2 9 1 5 6
 * Ieșire: 1 2 5 5 6 9
 */
#include <iostream>
using namespace std;

int v[1001];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    for (int i = 2; i <= n; i++)
    {
        int x = v[i];
        int j = i - 1;
        while (j >= 1 && v[j] > x)
        {
            v[j + 1] = v[j];
            j--;
        }
        v[j + 1] = x;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << v[i] << ' ';
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.