Sortare cu bule

Sortarea după schimburi simple , sortarea după un balon ( în engleză bubble sort ) este un algoritm de sortare simplu . A înțelege și a implementa acest algoritm este cel mai simplu, dar este eficient doar pentru matrice mici. Complexitatea algoritmului: . $O$ $(n^{2})$

Algoritmul este considerat educațional și practic nu este utilizat în afara literaturii educaționale; în schimb, în practică sunt utilizați algoritmi de sortare mai eficienți. În același timp, metoda de sortare prin schimb stă la baza unora dintre algoritmii mai avansați, cum ar fi sortarea cu agitare , sortarea în grămada și sortarea rapidă .

Algoritm

Algoritmul constă în treceri repetate prin matricea sortată. Pentru fiecare trecere, elementele sunt comparate secvențial în perechi și, dacă ordinea în pereche este incorectă, elementele sunt permutate. Trecerile prin matrice se repetă o dată sau până când la următoarea trecere se dovedește că schimburile nu mai sunt necesare, ceea ce înseamnă că matricea este sortată. Cu fiecare trecere a algoritmului prin bucla interioară, următorul element cel mai mare al matricei este pus în locul său la sfârșitul matricei lângă „cel mai mare element” anterior, iar cel mai mic element se mută cu o poziție la începutul matricei. matrice („plutește” în poziția dorită, ca un balon în apă - de aici și numele algoritmului). $N-1$

Implementare

Dificultate: . $O(n^{2})$

Cel mai rău caz:

Numărul de comparații din corpul buclei este . $(N-1){\frac N2}$
Numărul de comparații din anteturile buclei este . $(N-1){\frac N2}$
Numărul total de comparații este . $(N-1)N$
Numărul de atribuiri din anteturile buclei este . $(N-1){\frac N2}$
Numărul de schimburi este egal cu , care este de ori mai mare decât în sortarea de selecție . $(N-1){\frac N2}$ ${\frac N2}$

Cel mai bun caz (matricea deja sortată este introdusă):

Numărul de comparații din corpul buclei este . $(N-1){\frac N2}$
Numărul de comparații din anteturile buclei este . $(N-1){\frac N2}$
Numărul total de comparații este . $(N-1)N$
Numărul de schimburi este de . $0$

Particularitatea acestui algoritm este următoarea: după prima completare a buclei interioare, elementul maxim al matricei este întotdeauna în poziția --a. La a doua trecere, următorul element ca mărime este pe loc. Si asa mai departe. Astfel, la fiecare trecere ulterioară, numărul de elemente procesate este redus cu 1 și nu este nevoie să „parcurgeți” întregul tablou de la început până la sfârșit de fiecare dată. $N$ $N-1$

Întrucât o subgrupă a unui element nu trebuie să fie sortată, sortarea nu necesită mai mult decât iterații ale buclei exterioare. Prin urmare, în unele implementări, bucla exterioară funcționează întotdeauna fără probleme și nu ține evidența dacă au existat sau nu au existat schimburi la fiecare iterație. $N-1$ $N-1$

Introducerea unui indicator (steagul F) al schimburilor reale în bucla interioară reduce numărul de treceri suplimentare în cazurile cu matrice de intrare parțial sortate. Înainte de fiecare trecere prin bucla interioară, steag-ul este resetat la 0, iar după ce a avut loc schimbul, acesta este setat la 1. Dacă steagul este 0 după ieșirea din bucla interioară, atunci nu au existat schimburi, adică matricea este sortat și puteți părăsi programul de sortare înainte de program.

Pseudocod pentru un algoritm și mai îmbunătățit cu verificarea schimburilor care au avut loc într-adevăr în bucla interioară.

Intrare: matrice formată din elemente, numerotate de la la $UN]$ $N$ $A[0]$ $A[N-1]$

BUCLA PENTRU J = 1 LA N - 1 PASUL 1 PENTRU J = 1 LA N - 1 PASUL 1 F = 0 F = 0 BUCLA PENTRU I = 0 LA N - 1 - J PASUL 1 PENTRU I = 0 LA N - 1 - J PASUL 1 DACĂ A [ I ] > A [ I + 1 ] ATUNCI SCHIMBĂ A [ I ], A [ I + 1 ]: F = 1 DACĂ A [ I ] > A [ I + 1 ] ATUNCI SCHIMBA A [ I ], A [ I + 1 ]: F = 1 NEXT I NEXT I DACĂ F = 0 ATUNCI EXIT LOOP IF F = 0 THEN EXIT PENTRU NEXT J NEXT J

În cazul unei ieșiri anticipate de la sortare, acest algoritm face o trecere redundantă fără schimburi.

Cel mai rău caz (nu se îmbunătățește):

Numărul de comparații din corpul buclei este . $(N-1){\frac N2}$
Numărul de comparații în anteturile buclei . $(N-1){\frac N2}$
Numărul total de comparații este . $(N-1)N$
Numărul de atribuiri din anteturile buclei este . $(N-1){\frac N2}$
Numărul de schimburi este de . $(N-1){\frac N2}$

Cel mai bun caz (îmbunătățit):

Numărul de comparații din corpul buclei este . $(N-1)$
Numărul de comparații în anteturile buclei . $(N-1)$
Numărul total de comparații este . $2(N-1)$
Numărul de schimburi este de . $0$

Timpul de sortare a 10.000 de numere întregi scurte pe același complex hardware-software (operație de comparație ≈3,4 µs, schimb ≈2,3 µs) prin sortare prin selecție a fost ≈40 sec, prin sortare cu bule și mai îmbunătățită ≈30 sec și prin sortare rapidă ≈ 0,027 sec.

$O(n\cdot n)$ mai mare decât sort sort , dar la mic diferența nu este foarte mare, iar codul programului este foarte simplu, deci este destul de acceptabil să utilizați sortarea cu bule pentru multe sarcini cu matrice de dimensiuni reduse pe mașini inactive și puțin încărcate. $O(n\cdot\log n)$ $n$

Algoritmul poate fi ușor îmbunătățit făcând următoarele:

Bucla interioară poate fi modificată astfel încât să scaneze alternativ matricea de la început, apoi de la sfârșit. Un algoritm modificat în acest fel se numește shuffle sort sau shaker sort. Acest lucru nu reduce complexitatea . $O(n\cdot n)$

În sortarea cu bule, cu fiecare trecere prin bucla interioară, puteți adăuga definiția următorului element minim și îl puteți plasa la începutul matricei, adică combinați algoritmii de sortare cu bule și sortare de selecție , în timp ce numărul de treceri. bucla interioară este înjumătățită, dar numărul de comparații și un schimb se adaugă după fiecare trecere prin bucla interioară.

Pseudocod al algoritmului combinat de sortare cu bule și sortare de selecție ( implementare stabilă ):

PENTRU J = 0 LA N - 1 PASUL 1 F = 0 MIN = J PENTRU I = J LA N - 1 - J PASUL 1 DACĂ Y [ I ] > Y [ I + 1 ] ATUNCI SCHIMBA Y [ I ], Y [ I + 1 ]: F = 1 DACĂ Y [ I ] < Y [ MIN ] ATUNCI MIN = I NEXT I DACĂ F = 0 ATUNCI EXIT PENTRU IF MIN <> J THEN SWAP Y [ J ], Y [ MIN ] NEXT J

Un exemplu despre cum funcționează algoritmul

Să luăm o matrice cu numere „5 1 4 2 8” și să sortăm valorile în ordine crescătoare folosind sortarea cu bule. Sunt evidențiate acele elemente care sunt comparate în această etapă.

Prima trecere:

( 5 1 4 2 8) ( 1 5 4 2 8), Aici algoritmul compară primele două elemente și le schimbă. (1 5 4 2 8) (1 4 5 2 8), Schimbă deoarece

5>4

(1 4 5 2 8) (1 4 2 5 8), Schimbă deoarece

5>2

(1 4 2 5 8 ) (1 4 2 5 8 ), Acum, deoarece elementele sunt la locul lor ( ), algoritmul nu le schimbă.

8>5

A doua trecere:

( 1 4 2 5 8) ( 1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8), Schimbă deoarece

4>2

(1 2 4 5 8) (1 2 4 5 8)

Acum matricea este complet sortată, dar algoritmul nu știe acest lucru. Prin urmare, trebuie să facă o trecere completă și să determine că nu au existat permutări ale elementelor.

A treia trecere:

( 1 2 4 5 8) ( 1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)

Acum matricea este sortată și algoritmul poate fi completat.

Link -uri

Animarea algoritmilor de sortare
Vizualizare dinamică 7 algoritmi de sortare open source
Levitin A. V. Capitolul 3. Metoda forței brute: Bubble sort // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 144-146. — 576 p. — ISBN 978-5-8459-0987-9

Dicționare și enciclopedii	mare chinezesc

Algoritmi de sortare
Teorie	Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar	bule Agitând Piticii Rapid Pieptene Sortare par-impar Pe bit
Alegere	Alegere Piramidal Neted
inserții	inserții shella copac
fuziune	fuziune
Fara comparatii	Socoteală bloc
hibrid	introsort Timsort
Alte	Topologic retelelor biton
nepractic	Bogosort Soiul de ciudăţeni clătită încet