Metoda bubble c matrice unidimensională. Implementarea sortării cu bule în Java

S-a estimat că până la un sfert din timpul computerelor centralizate este cheltuit pentru sortarea datelor. Acest lucru se datorează faptului că este mult mai ușor să găsiți o valoare într-o matrice care a fost pre-sortată. Altfel, căutarea este un pic ca a căuta un ac într-un car de fân.

Există programatori care își petrec tot timpul de lucru studiind și implementând algoritmi de sortare. Acest lucru se datorează faptului că marea majoritate a software-ului de afaceri implică gestionarea bazelor de date. Oamenii caută informații în bazele de date tot timpul. Aceasta înseamnă că algoritmii de căutare sunt la mare căutare.

Dar există un „dar”. Algoritmii de căutare funcționează mult mai rapid cu bazele de date care sunt deja sortate. În acest caz, este necesară doar o căutare liniară.

În timp ce computerele sunt fără utilizatori în anumite momente, algoritmii de sortare continuă să funcționeze pe bazele de date. Căutătorii vin din nou, iar baza de date este deja sortată în funcție de unul sau altul scop de căutare.

Acest articol oferă exemple de implementări ale algoritmilor standard de sortare.

Sortare selecție

Pentru a sorta o matrice în ordine crescătoare, trebuie să găsiți elementul cu cea mai mare valoare la fiecare iterație. Cu el trebuie să schimbați ultimul element. Următorul element cu cea mai mare valoare este plasat pe penultimul loc. Acest lucru ar trebui să se întâmple până când elementele din primele locuri din matrice sunt în ordinea corectă.

cod C++

void SortAlgo::selectionSort(int date, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i data[k])(j = k; ) ) tmp = data[i]; data[i] = data[j]; data[j] = tmp; ) )

Sortare cu bule

Sortarea cu bule compară elementele adiacente și schimbă locuri dacă următorul element este mai mic decât cel anterior. Sunt necesare mai multe treceri prin date. În timpul primei treceri, primele două elemente din matrice sunt comparate. Dacă nu sunt în ordine, sunt schimbate și apoi sunt comparate elementele din perechea următoare. În aceeași condiție, își schimbă și locul. Astfel, sortarea are loc în fiecare ciclu până când se ajunge la sfârșitul matricei.

cod C++

void SortAlgo::bubbleSort(int date, int lenD) ( int tmp = 0; for (int i = 0;i) =(i+1);j--)( dacă (date[j]

Sortare prin inserare

Sortarea prin inserare împarte matricea în două regiuni: ordonată și neordonată. Inițial, întreaga matrice este o regiune neordonată. La prima trecere, primul element din regiunea neordonată este îndepărtat și plasat în poziția corectă în regiunea ordonată.

La fiecare trecere, dimensiunea regiunii ordonate crește cu 1, iar dimensiunea regiunii dezordonate scade cu 1.

Bucla principală merge de la 1 la N-1. La a j-a iterație, elementul [i] este inserat în poziția corectă în regiunea ordonată. Acest lucru se face prin deplasarea tuturor elementelor din regiunea ordonată care sunt mai mari decât [i] cu o poziție spre dreapta. [i] este introdus în spațiul dintre acele elemente care sunt mai mici decât [i] și cele care sunt mai mari decât [i].

cod C++

void SortAlgo::insertionSort(int date, int lenD) ( int key = 0; int i = 0; for (int j = 1;j) =0 && date[i]>key)( date = data[i]; i = i-1; data=key; ) ) )

Sortare îmbinare

cod C++

void SortAlgo::mergeSort(int date, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = new int; int * R = new int; for ( int i=0;i

Sortare rapida

Sortarea rapidă folosește un algoritm de împărțire și cucerire. Începe prin împărțirea matricei originale în două regiuni. Aceste părți sunt în stânga și în dreapta elementului marcat, numit suport. La sfârșitul procesului, o parte va conține elemente mai mici decât referința, iar cealaltă parte va conține elemente mai mari decât referința.

cod C++

void SortAlgo::quickSort(int * data, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1) ( int * L = int nou ; int * R = int nou ; pivot = date ; pentru (i = 0; i

Sortarea cu bule este cel mai simplu algoritm de sortare folosit exclusiv în scopuri educaționale. Nu există o aplicație practică pentru acest algoritm, deoarece nu este eficient, mai ales dacă este necesar să sortați o matrice mare. Avantajele sortării cu bule includ ușurința de implementare a algoritmului.

Algoritmul de sortare cu bule se rezumă la treceri repetate prin elementele matricei sortate. Iterarea prin elementele matricei realizează o buclă interioară. Pentru fiecare trecere, două elemente adiacente sunt comparate, iar dacă ordinea este incorectă, elementele sunt schimbate. Bucla exterioară va rula până când matricea este sortată. Astfel, bucla exterioară controlează de câte ori este executată bucla interioară Când, în timpul următoarei treceri prin elementele matricei, nu se face o singură permutare, matricea va fi considerată sortată. Pentru a înțelege bine algoritmul, să sortăm o matrice de, de exemplu, 7 numere folosind metoda bulelor (vezi Tabelul 1).
matrice originală: 3 3 7 1 2 5 0

Pentru a sorta matricea, cinci rulări ale buclei interioare, pentru , au fost suficiente. După ce a început, bucla for a funcționat de 6 ori, deoarece există 7 elemente în matrice, atunci ar trebui să existe o iterație (repetare) mai puțin a buclei for. La fiecare iterație, două elemente de matrice adiacente sunt comparate. Dacă elementul de matrice curent este mai mare decât următorul, atunci le schimbăm. Astfel, până când matricea este sortată, bucla interioară va rula și se va efectua operația de comparare. Rețineți că pentru fiecare execuție completă a buclei for, cel puțin un element al matricei își găsește locul. În cel mai rău caz, vor fi necesare n-2 rulări ale buclei interioare, unde n este numărul de elemente ale matricei. Acest lucru sugerează că sortarea cu bule este extrem de ineficientă pentru matrice mari.

Să dezvoltăm un program în care trebuie mai întâi să introduceți dimensiunea unei matrice unidimensionale, după care matricea este umplută cu numere aleatorii și sortată folosind sortarea cu bule.

// bu_sort.cpp: Definește punctul de intrare pentru aplicația consolă. #include „stdafx.h” #include #include #include folosind namespace std; void bubbleSort(int *, int); // prototipul funcției de sortare cu bule int main(int argc, char* argv) ( srand(time(NULL)); setlocale(LC_ALL, "rus"); cout<< "Введите размер массива: "; int size_array; // длинна массива cin >> size_array; int *sorted_array = new int ; // matrice dinamică unidimensională pentru (int counter = 0; counter< size_array; counter++) { sorted_array = rand() % 100; // заполняем массив случайными числами cout << setw(2) << sorted_array << " "; // вывод массива на экран } cout << "\n\n"; bubbleSort(sorted_array, size_array); // вызов функции сортировки пузырьком for (int counter = 0; counter < size_array; counter++) { cout << setw(2) << sorted_array << " "; // печать отсортированного массива } cout << "\n"; system("pause"); return 0; } void bubbleSort(int* arrayPtr, int length_array) // сортировка пузырьком { int temp = 0; // временная переменная для хранения элемента массива bool exit = false; // болевая переменная для выхода из цикла, если массив отсортирован while (!exit) // пока массив не отсортирован { exit = true; for (int int_counter = 0; int_counter < (length_array - 1); int_counter++) // внутренний цикл //сортировка пузырьком по возрастанию - знак >//sortează după balon în ordine descrescătoare - semn< if (arrayPtr >arrayPtr) // compară două elemente adiacente ( // efectuează o rearanjare a elementelor matricei temp = arrayPtr; arrayPtr = arrayPtr; arrayPtr = temp; exit = false; // elementele au fost rearanjate la următoarea iterație) ) )

Rezultatul programului este prezentat în Figura 1.

Figura 1 - Sortare cu bule

Când lucrați cu matrice de date, sarcina apare adesea sortarea în ordine crescătoare sau descrescătoare, adică comanda. Aceasta înseamnă că elementele aceleiași matrice trebuie aranjate strict în ordine. De exemplu, în cazul sortării crescătoare, elementul precedent trebuie să fie mai mic decât (sau egal) cu cel următor.

Soluţie

Există multe metode de sortare. Unele dintre ele sunt mai eficiente, altele sunt mai ușor de înțeles. Sortarea este destul de ușor de înțeles metoda bulelor, care se mai numește metoda simplă de schimb. Ce este și de ce are un nume atât de ciudat: „metoda cu bule”?

După cum știți, aerul este mai ușor decât apa, așa că bulele de aer plutesc. Este doar o analogie. În sortarea cu bule crescătoare, elementele mai ușoare (valoare mai mică) „plutesc” treptat până la începutul matricei, iar cele mai grele, unul după altul, cad în partea de jos (până la sfârșitul matricei).

Algoritmul și caracteristicile acestei sortări sunt următoarele:

1. În timpul primei treceri prin matrice, elementele sunt comparate între ele în perechi: primul cu al doilea, apoi al doilea cu al treilea, apoi al treilea cu al patrulea etc. Dacă elementul anterior este mai mare decât cel următor, atunci ele sunt schimbate.
2. Nu este greu de ghicit că, treptat, cel mai mare număr se dovedește a fi ultimul. Restul matricei rămâne nesortat, deși există o anumită mișcare a elementelor cu valoare mai mică la începutul matricei.
3. La a doua trecere, nu este nevoie să comparați ultimul element cu penultimul. Ultimul element este deja la locul lui. Aceasta înseamnă că numărul de comparații va fi cu unul mai puțin.
4. La a treia trecere, nu mai este nevoie să comparăm penultimul și al treilea element de la final. Prin urmare, numărul de comparații va fi cu două mai puțin decât în ​​prima trecere.
5. La urma urmei, atunci când iterați printr-o matrice, când mai sunt doar două elemente de comparat, se efectuează o singură comparație.
6. După aceasta, nu mai există nimic cu care să comparați primul element și, prin urmare, o trecere finală prin matrice nu este necesară. Cu alte cuvinte, numărul de treceri prin matrice este m-1, unde m este numărul de elemente din matrice.
7. Numărul de comparații din fiecare trecere este egal cu m-i, unde i este numărul de treceri prin matrice (primul, al doilea, al treilea etc.).
8. La schimbul de elemente de matrice, se folosește de obicei o variabilă „buffer” (a treia), unde valoarea unuia dintre elemente este plasată temporar.

Programul Pascal:

const m = 10 ; var arr: matrice [ 1 .. m ] de întreg ; i, j, k: întreg; începe randomizarea; scrie( "Matrice sursă: "); for i : = 1 to m do begin arr[ i] : = random(256 ) ; scrie (arr[ i] : 4 ) ; Sfârşit ; scrie ; scrie ; for i : = 1 to m- 1 do for j : = 1 to m- i do if arr[ j] > arr[ j+ 1 ] then begin k : = arr[ j] ; arr[ j] : = arr[ j+ 1 ] ; arr[ j+ 1 ] : = k sfârşit ; scrie( "Matrice sortată: "); pentru i : = 1 la m scrieți (arr[ i] : 4 ) ; scrie ; readln sfârşitul .

Nu numai că nu este considerată cea mai rapidă metodă, în plus, închide lista celor mai lente metode de comandă. Cu toate acestea, are și avantajele sale. Deci, sortarea cu bule este cea mai logică și naturală soluție la problemă dacă trebuie să aranjați elementele într-o anumită ordine. O persoană obișnuită, de exemplu, îl va folosi manual - pur și simplu prin intuiție.

De unde a venit un nume atât de neobișnuit?

Numele metodei a fost inventat folosind o analogie cu bulele de aer din apă. Aceasta este o metaforă. Așa cum bulele de aer mici se ridică în vârf - la urma urmei, densitatea lor este mai mare decât cea a oricărui lichid (în acest caz, apă), astfel încât fiecare element al matricei, cu cât este mai mic ca valoare, cu atât își face treptat mai mult. drum spre începutul listei de numere.

Descrierea algoritmului

Sortarea cu bule funcționează astfel:

• prima trecere: elementele matricei de numere sunt luate câte două și, de asemenea, comparate în perechi. Dacă într-o pereche de elemente prima valoare este mai mare decât a doua, programul le schimbă;
• prin urmare, ajunge la sfârșitul matricei. În timp ce toate celelalte elemente rămân așa cum erau, într-o ordine haotică și necesită o sortare suplimentară;
• de aceea este necesară o a doua trecere: se efectuează prin analogie cu cea anterioară (deja descrisă) și are numărul de comparații - minus unu;
• Pasajul numărul trei are cu o comparație mai puțin decât al doilea și cu două mai puțin decât primul. Și așa mai departe;
• Să rezumăm că fiecare trecere are (valori totale în matrice, un anumit număr) minus (numărul de trecere) comparații.

Și mai pe scurt, algoritmul viitorului program poate fi scris după cum urmează:

• matricea de numere este verificată până când sunt găsite două numere, iar al doilea dintre ele trebuie să fie mai mare decât primul;
• Programul schimbă elementele de matrice care sunt poziționate incorect unele în raport cu altele.

Pseudocod bazat pe algoritmul descris

Cea mai simplă implementare este așa:

Procedură Sortirovka_Puzirkom;

start

bucla pentru j din index_inițial inainte de konechii_index;

bucla pentru i din index_inițial inainte de konechii_index-1;

Dacă masiv[i]>massiv

(schimbați valorile);

Sfârşit

Desigur, aici simplitatea nu face decât să agraveze situația: cu cât algoritmul este mai simplu, cu atât mai multe neajunsurile apar în el. Consumul de timp este prea mare chiar și pentru o matrice mică (relativitatea intră în joc aici: pentru o persoană obișnuită, cantitatea de timp poate părea mică, dar în afacerea unui programator, fiecare secundă sau chiar milisecundă contează).

Era nevoie de o implementare mai bună. De exemplu, ținând cont de schimbarea valorilor într-o matrice:

Procedură Sortirovka_Puzirkom;

start

sortirovka = adevărat;

ciclu până acum sortirovka = adevărat;

sortirovka = fals;

bucla pentru i din index_inițial inainte de konechii_index-1;

Dacă masiv[i]>massiv(primul element este mai mare decât al doilea), atunci:

(schimbarea elementelor);

sortirovka = adevărat; (a indicat că schimbul a fost făcut).

Sfârşit.

Dezavantajele metodei

Principalul dezavantaj este durata procesului. Cât durează să faci o bula?

Timpul de execuție este calculat din pătratul numărului de numere din matrice - rezultatul final este proporțional cu acesta.

În cel mai rău caz, matricea va fi parcursă de același număr de ori cât există elemente în ea minus o valoare. Acest lucru se întâmplă pentru că, în cele din urmă, rămâne un singur element cu nimic cu care să se compare, iar ultima trecere prin matrice devine o acțiune inutilă.

În plus, metoda simplă de sortare prin schimb, așa cum este numită și, este eficientă numai pentru matrice mici. Nu va fi posibil să procesați cantități mari de date cu ajutorul acestuia: rezultatul va fi fie erori, fie eșecul programului.

Avantaje

Sortarea cu bule este destul de simplu de înțeles. În programele de învățământ ale universităților tehnice, atunci când se studiază ordonarea elementelor de matrice, aceasta este acoperită mai întâi. Metoda este ușor de implementat atât în ​​limbajul de programare Delphi (D) cât și în C/C++ (C/C plus plus), un algoritm incredibil de simplu pentru aranjarea valorilor în ordinea corectă, iar Bubble Sort este ideal pentru începători.

Din cauza deficiențelor sale, algoritmul nu este utilizat în scopuri extracurriculare.

Principiul de sortare vizuală

Vedere inițială a matricei 8 22 4 74 44 37 1 7

Pasul 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Pasul 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Pasul 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Pasul 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Pasul 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Pasul 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Pasul 7 1 4 7 8 22 37 44 74

Exemplu de sortare cu bule în Pascal

Exemplu:

const kol_mas=10;

var array:matrice de întreg;

a, b, k: întreg;

writeln("input", kol_mas, "elementele matricei");

for a:=1 to kol_mas do readln(array[a]);

pentru a:=1 la kol_mas-1 începe

pentru b:=a+1 la kol_mas începe

dacă massiv[a]>massiv[b] atunci începe

k:=matrice[a]; massiv[a]:=massiv[b]; matrice[b]:=k;

Sfârşit;

writeln("după sortare");

for a:=1 to kol_mas do writeln(massiv[a]);

Exemplu de sortare cu bule în limbajul C

#include

#include

int main(int argc, char* argv)

int massiv = (36, 697, 73, 82, 68, 12, 183, 88),i, ff;

pentru (; ;)(

ff = 0;

pentru (i = 7; i>0; i--)(

dacă (matrice[i]< massiv) {

swap(array[i],massiv);

dacă (ff == 0) rupere;

getch(); // întârziere ecran