Meni

Razvrstavanje mjehurića na C ++ s primjerima

  • Glavni
  • Ostalo
  • Razvrstavanje mjehurića na C ++ s primjerima

bubble sort c with examples

Isprobajte Naš Instrument Za Uklanjanje Problema

Tehnika sortiranja mjehurića na C ++.

Bubble Sort je najjednostavnija tehnika sortiranja.

U tehnici razvrstavanja mjehurića svaki se element na popisu uspoređuje sa susjednim elementom. Dakle, ako na popisu A ima n elemenata, tada se A (0) uspoređuje s A (1), A (1) uspoređuje s A (2) i tako dalje.

Nakon usporedbe ako je prvi element veći od drugog, dva se elementa zamijene.

=> Posjetite ovdje za cjeloviti tečaj stručnjaka za C ++.

BUBBLE SORT

Što ćete naučiti:

kako otvoriti mkv datoteku na Windowsima

Tehnika sortiranja mjehurića

Tehnikom sortiranja mjehurića sortiranje se vrši u dodavanjima ili iteracijama. Tako se na kraju svake iteracije najteži element postavlja na svoje odgovarajuće mjesto na popisu. Drugim riječima, najveći element na popisu se uskočio.

U nastavku smo dali opći algoritam tehnike razvrstavanja mjehurića.

Opći algoritam

Korak 1 : Za i = 0 do N-1 ponovite 2. korak
Korak 2 : Za J = i + 1 do N - ponavljam
3. korak : ako je A (J)> A (i)
Zamijenite A (J) i A (i)
(Kraj unutarnje for petlje)
(Kraj ako je vanjska petlja za)
4. korak : Izlaz

Evo pseudo-koda za algoritam sortiranja oblačića, gdje prelazimo popis koristeći dvije iterativne petlje.

U prvoj petlji započinjemo od 0thelementa i u sljedećoj petlji započinjemo od susjednog elementa. U tijelu unutarnje petlje uspoređujemo svaki susjedni element i zamjenjujemo ih ako nisu u redu. Na kraju svake iteracije vanjske petlje, najteži element na kraju mjehuriće.

Pseudokod

Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array(i-1) > array(i) then swap array(i-1) and array(i) swapped = true end if end for until not swapped end procedure

Gore navedeno je pseudo-kôd za tehniku ​​sortiranja mjehurića. Pokažimo sada ovu tehniku ​​pomoću detaljne ilustracije.

Ilustracija

Uzmemo niz veličine 5 i ilustriramo algoritam sortiranja mjehurića.

Ilustracija sortiranja mjehurića - prolazak 1

Ilustracija sortiranja mjehurića - prolazak 2

Ilustracija mjehurića - prolazak 3

Niz je u potpunosti sortiran.

Gornja ilustracija može se sažeti u tabličnom obliku kako je prikazano dolje:

ProćiNesortirani popisusporedbaPoredani popis
{5,0,10,12,15}{10.12}{5,0,10,12,15}
1{10,5,15,0,12}{10,5}{5,10,15,0,12}
{5,10,15,0,12}{10,15}{5,10,15,0,12}
{5,10,15,0,12}{15,0}{5,10,0,15,12}
{5,10,0,15,12}{15.12}{5,10,0,12,15}
dva{5,10,0,12,15}{5,10}{5,10,0,12,15}
{5,10,0,12,15}{10,0}{5,0,10,12,15}
3{5,0,10,12,15}{5,0}{0,5,10,12,15}
{5,0,10,12,15}{5,10}{5,0,10,12,15}
{5,0,10,12,15}UREDJENO

Kao što je prikazano na ilustraciji, pri svakom prolazu najveći element mjehuriće do zadnjeg, sortirajući tako popis sa svakim prolazom. Kao što je spomenuto u uvodu, svaki se element uspoređuje sa susjednim elementom i zamjenjuje jedan s drugim ako nisu u redu.

Dakle, kao što je prikazano na gornjoj ilustraciji, na kraju prvog prolaska, ako se polje želi sortirati u rastućem redoslijedu, najveći se element stavlja na kraj popisa. Za drugi prolazak, drugi najveći element postavlja se na drugo posljednje mjesto na popisu i tako dalje.

Kad dosegnemo prolaze N-1 (gdje je N ukupan broj elemenata na popisu), sortirat ćemo cijeli popis.

koji je najbolji besplatni glazbeni downloader?

Tehnika sortiranja mjehurića može se implementirati u bilo kojem programskom jeziku. Implementirali smo algoritam razvrstavanja oblačića koristeći jezik C ++ i Java u nastavku.

Primjer C ++

Pogledajmo primjer programiranja za demonstraciju vrste mjehurića.

#include using namespace std; int main () { int i, j,temp,pass=0; int a(10) = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ... '; for(i = 0; i<10; i++) { cout <

Izlaz:

Popis unosa ...

10 2 0 14 43 25 18 1 5 45

Poređani popis elemenata ...

0 1 2 5 10 14 18 25 43 45

Broj prolaza za sortiranje popisa: 10

Primjer Java

class Main { public static void main(String() args) { int pass = 0; int() a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a(i)

Izlaz:

bubble_sort Java izlaz

U oba programa koristili smo niz od 10 elemenata i sortirali smo ga tehnikom sortiranja mjehurića. U oba programa koristili smo dvije for petlje za iteraciju kroz susjedne elemente niza.

Na kraju svakog prolaza (vanjska petlja), najveći element u nizu oblačiće se do kraja niza. Također računamo broj prolaza potrebnih za sortiranje cijelog niza.

Analiza složenosti algoritma sortiranja mjehurića

Iz pseudo koda i ilustracije koju smo vidjeli gore, u mjehuriću, uspoređujemo N-1 u prvom prolazu, N-2 u drugom prolazu i tako dalje.

Stoga je ukupan broj usporedbi u sortiranju mjehurića:

I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1

= N (N-1) / 2

= O (ndva) => Vremenska složenost tehnike sortiranja mjehurića

Stoga su u nastavku dane razne složenosti tehnike sortiranja mjehurića:

Najgora vremenska složenostO (n 2)
Najbolja vremenska složenostNa)
Prosječna vremenska složenostO (n 2)
Složenost prostoraO (1)

Tehnika sortiranja mjehurića zahtijeva samo jedan dodatni memorijski prostor za vremensku varijablu kako bi se olakšala zamjena. Stoga je složenost prostora za algoritam sortiranja mjehurića O (1).

Imajte na umu da će najbolja vremenska složenost za tehniku ​​razvrstavanja mjehurića biti kada je popis već sortiran i to će biti O (n).

Zaključak

Glavna prednost Bubble Sort-a je jednostavnost algoritma. U razvrstavanju oblačića, pri svakom prolazu, najveći se element oblači do kraja popisa ako je niz sortiran uzlaznim redoslijedom.

Slično tome, za popis koji će se sortirati u opadajućem redoslijedu, najmanji element bit će na svom mjestu na kraju svakog prolaska.

Budući da je sortiranje mjehurića najjednostavnije i najjednostavnije, sortiranje u obliku mjehurića obično se koristi za predstavljanje sortiranja publici. Drugo, razvrstavanje mjehurića također se koristi u aplikacijama poput računalne grafike pri čemu ispunjavanje rubova poligona itd. Zahtijeva razvrstavanje mjehurića za sortiranje vrhova koji oblažu poligon.

U našem nadolazećem vodiču detaljno ćemo naučiti o sortiranju odabira.

=> Posjetite ovdje da biste C ++ naučili od nule.

api testiranje intervjua pitanja i odgovori

Preporučena literatura

^