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

Selection sort

Original: Sortarea prin selecție

O(n²)C++1752 lines1 example

The idea

For every position i, from 1 to n - 1, we look for the minimum of v[i..n] and bring it to position i with a single swap. After step i, the first i positions hold the i smallest values, in order. It always makes about n²/2 comparisons, but at most n - 1 swaps.

Original description (Romanian)

Pentru fiecare poziție i, de la 1 la n - 1, căutăm minimul din v[i..n] și îl aducem pe poziția i printr-o singură interschimbare. După pasul i, primele i poziții conțin cele mai mici i valori, în ordine. Face mereu cam n²/2 comparații, dar cel mult n - 1 interschimbări.

Complexity
O(n²)
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-selectie.cpp
/*
 * Titlu: Sortarea prin selecție
 * Clasa: 9
 * Capitol: Sortare și căutare
 * Descriere: Pentru fiecare poziție i, de la 1 la n - 1, căutăm minimul din
 *            v[i..n] și îl aducem pe poziția i printr-o singură interschimbare.
 *            După pasul i, primele i poziții conțin cele mai mici i valori, în
 *            ordine. Face mereu cam n²/2 comparații, dar cel mult n - 1
 *            interschimbări.
 * Complexitate: O(n²)
 *
 * 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 = 1; i < n; i++)
    {
        int pozMin = i;
        for (int j = i + 1; j <= n; j++)
        {
            if (v[j] < v[pozMin])
            {
                pozMin = j;
            }
        }
        int aux = v[i];
        v[i] = v[pozMin];
        v[pozMin] = aux;
    }
    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.