Bubble sort, denumit uneori sortare scufundată, este un algoritm de sortare simplu care parcurge în mod repetat lista, compară elementele adiacente și le schimbă dacă sunt în ordinea greșită. Trecerea prin listă se repetă până când lista este sortată.
Care este ordinea complexității în sortarea cu bule în cel mai rău caz?
Bubble Sort este un algoritm de sortare stabil, ușor de implementat, cu o complexitate temporală de O(n²) în cazurile medii și cele mai grave – și O(n) în cel mai bun caz.
De ce este cel mai rău caz pentru sortarea cu bule N 2?
Cel mai rău caz absolut pentru sortarea cu bule este când cel mai mic element al listei se află la capătul mare . … În cel mai rău caz, este nevoie de n iterații de n/2 schimburi, astfel încât comanda este, din nou, n2.
De ce este cel mai rău caz sortarea cu bule?
Cea mai proastă situație pentru sortarea cu bule este când cel mai mic element al listei se află în ultima poziție … În această situație, cel mai mic element se va deplasa în jos cu un loc la fiecare trecere prin listă, ceea ce înseamnă că sortarea va trebui să facă numărul maxim de treceri prin listă, și anume n - 1.
Cum se calculează cel mai bun caz de complexitate a sortării cu bule?
Pentru a calcula complexitatea algoritmului de sortare cu bule, este util să determinați câte comparații efectuează fiecare buclă. Pentru fiecare element din matrice, sortarea cu bule face n − 1 n-1 n−1 comparații. În notația O mare, sortarea cu bule efectuează comparații O (n) O(n) O(n).
