imagine-fundal

Blog / 📊 3 algoritmi de sortare vectori în C++
facebook instagram whatsapp tiktok twitter

     În tutorialul de astăzi vă voi arăta cum funcționează și cum putem aplica 3 algoritmi de sortare a tablourilor unidimensionale (vectori), în limbajul de programare C++ Imagine C++. Înainte de a începe, considerăm sortat vectorul care are aranjate, în ordine crescătoare, toate valorile. Primul pas este să înțelege cum funcționează codul prezentat. Fiind 3 algoritmi separați vom parcurge înainte explicația logică, apoi vom vedea reprezentarea în limbaj. Un exemplu de intrare - ieșire care funcționează este v = {12, 51, 32, 61, 14}, cu afișarea 12 14 32 51 61.

     Primul algoritm de sortare pe care îl vom parcurge în tutorial este sortare prin selecție, un algoritm simplu, care folosește 2 structuri repetivite cu număr cunoscut de pași și o structură alternativă pentru a testa valorile parcurse. Complexitatea algoritmului este O(n2). Acest program constă în folosirea a două variabile de parcurgere (i, j), care reprezintă 2 poziții consecutive din șirul nesortat de numere. Apoi, la fiecare pas, vom verifica dacă numărul de pe poziția mai mică este mai mare ca valoare decât cel de pe poziția următoare. Dacă da, vom interschimba numerele folosind funcția integrată, swap().

#include <bits/stdc++.h>
using namespace std;
int n, v[1001];
void sortare_selectie(int* v) {
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (v[i] > v[j])
                swap(v[i], v[j]);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    sortare_selectie(v);
    for (int i = 1; i <= n; i++) 
        cout << v[i] << " ";
    return 0;
}

     Al doilea algoritm pe care îl vom parcurge astăzi este sortarea STL (Standard Template Library). Acesta poate fi folosit apelând funcția cu 2 parametri (în cazul sortării în ordine crescătoare), primul fiind prima poziție din vector, iar al doilea ultima. Complexitatea algoritmului este O(n * logn). Chiar dacă este cel mai la îndemână algoritm, acesta poate fi greu de folosit în unele situații mai complexe (sortări în funcție de ceva), necesitând crearea unor funcții cu parametrii speciali.

#include <bits/stdc++.h>
using namespace std;
int n, v[1001];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    sort(v, v + n + 1);
    for (int i = 1; i <= n; i++) 
        cout << v[i] << " ";
    return 0;
}

     Ultimul, dar nu cel din urmă, algoritm pe care îl vom înțelege este QuickSort, numit și sortare Divide Et Impera. Acest algoritm se bazează pe procedeul menționat anterior pentru a funcționa. Va partiționa șirul mare în mai multe subșiruri, pe care va lucra simultan și care vor fi sortate. Cel mai simplu de scris este folosind recursivitatea, în timp ce celelalte 2 programe prezentate nu au nevoie necesară de funcții separate. Începem prin a apela funcția sortare_quick(), folosind 3 parametrii, vectorul pe care dorim să îl modificăm, poziția de start de pe care se va începe sortarea și poziția de stop. De ce poziție de start și stop și nu prima poziție din vector respectiv ultima? Răspunsul este simplu, pe parcursul fragmentării vom folosi diverse repere numite pivoți. Apoi, folosind fiecare pivot, vom verifica toate numerele din partiție și le vom interschimba în funcție de valori, folosind funcția prestabilită, swap(). La finalul partiționării vom trimite noul pivot către procesare. Rapiditatea ultimului algoritm din tutorial constă în metoda de împărțire a activitățiilor și oferă complexitatea O(n * logn).

#include <bits/stdc++.h>
using namespace std;
int n, v[1001];
int partition(int* v, int inc, int sf) {
    int pivot = v[inc];
    int counter = 0;
    for (int i = inc + 1; i <= sf; i++)
        if (v[i] <= pivot)
            counter++;
    int poz = inc + counter;
    swap(v[poz], v[inc]);
    int i = inc, j = sf;
    while (i < poz && j > poz) {
        while (v[i] <= pivot)
            i++;
        while (v[j] > pivot)
            j--;
        if (i < poz && j > poz)
            swap(v[i++], v[j--]);
    } return poz;
}
void sortare_quick(int* v, int inc, int sf) {
    if (inc >= sf)
        return;
    int part = partition(v, inc, sf);
    sortare_quick(v, inc, part - 1);
    sortare_quick(v, part + 1, sf);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    sortare_quick(v, 1, n);
    for (int i = 1; i <= n; i++) 
        cout << v[i] << " ";
    return 0;
}

     Mai jos poți vedea problemele recomandate și totodată concluzia tutorialului. Ordinea vitezei algoritmilor este:

sortarea prin selecție

sortarea Standard Template Library (STL)

sortarea rapidă (QuickSort)

     În timp ce ordinea permesibilității de modificare este:

sortarea rapidă (QuickSort)

sortarea prin selecție

sortarea Standard Template Library (STL)

     Probleme recomandate de pe platforma PBinfo: sortpp, paresort, sort2

imagine

pbinfo / 61

imagine

pbinfo / 258

imagine

pbinfo / 38