Meni

Razvrstitev mehurčkov v jeziku C ++ s primeri

  • Glavni
  • Drugo
  • Razvrstitev mehurčkov v jeziku C ++ s primeri

bubble sort c with examples

Preizkusite Naš Instrument Za Odpravo Težav

Tehnika razvrščanja mehurčkov v jeziku C ++.

Bubble Sort je najpreprostejša tehnika razvrščanja.

V tehniki razvrščanja mehurčkov se vsak element na seznamu primerja s sosednjim elementom. Če je na seznamu A torej n elementov, se A (0) primerja z A (1), A (1) primerja z A (2) itd.

Po primerjavi, če je prvi element večji od drugega, se nato elementa zamenjata.

=> Obiščite tukaj za celoten tečaj strokovnjakov za C ++.

BUBBLE SORT

Kaj se boste naučili:

z uporabo regularnega izraza v c ++

Tehnika razvrščanja mehurčkov

S tehniko razvrščanja mehurčkov sortiranje poteka v prehodih ali ponovitvah. Tako je na koncu vsake ponovitve najtežji element postavljen na svoje pravo mesto na seznamu. Z drugimi besedami, največji element na seznamu se dvigne navzgor.

Spodaj smo podali splošen algoritem tehnike razvrščanja mehurčkov.

Splošni algoritem

Korak 1 : Za i = 0 do N-1 ponovite 2. korak
2. korak : Za J = i + 1 do N - ponavljam
3. korak : če je A (J)> A (i)
Zamenjaj A (J) in A (i)
(Konec notranje for zanke)
(Konec, če zunanja zanka)
4. korak : Izhod

Tukaj je psevdo-koda za algoritem za razvrščanje mehurčkov, kjer prečkamo seznam z uporabo dveh iterativnih zank.

V prvi zanki začnemo z 0thelement in v naslednji zanki začnemo od sosednjega elementa. V ohišju notranje zanke primerjamo vsakega od sosednjih elementov in jih zamenjamo, če niso v redu. Na koncu vsake ponovitve zunanje zanke najtežji element na koncu mehuri.

Psevkodo

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

Zgoraj navedena je psevdo-koda za tehniko razvrščanja mehurčkov. Poglejmo zdaj to tehniko z uporabo podrobne ilustracije.

Ilustracija

Vzamemo niz velikosti 5 in ponazorimo algoritem za razvrščanje mehurčkov.

Ilustracija razvrščanja mehurčkov - Pass 1

Ilustracija razvrščanja mehurčkov - podaja 2

Ilustracija mehurčkov - Pass 3

Niz je v celoti razvrščen.

Zgornjo ponazoritev lahko povzamemo v obliki tabele, kot je prikazano spodaj:

MimoNerazvrščen seznamprimerjavaRazvrščen seznam
{5,0,10,12,15}{10.12}{5,0,10,12,15}
eno{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}RAZREDJENO

Kot je prikazano na sliki, pri vsakem prehodu največji element mehurčka do zadnjega in s tem razvrsti seznam z vsakim prehodom. Kot je bilo omenjeno v uvodu, se vsak element primerja s sosednjim elementom in zamenja, če ni v redu.

Tako je, kot je prikazano na zgornji sliki, na koncu prvega prehoda, če naj bo matrika razvrščena v naraščajočem vrstnem redu, največji element postavljen na konec seznama. Za drugo podajo je drugi največji element postavljen na drugo zadnje mesto na seznamu in tako naprej.

Ko dosežemo prehod N-1 (kjer je N skupno število elementov na seznamu), bomo razvrstili celoten seznam.

kako odpreti hudourniško datoteko v operacijskem sistemu Windows

Tehniko razvrščanja po mehurčkih lahko izvedemo v katerem koli programskem jeziku. V nadaljevanju smo uvedli algoritem za razvrščanje oblačkov z uporabo jezika C ++ in Java.

Primer C ++

Oglejmo si primer programiranja za prikaz vrste mehurčkov.

#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 <

Izhod:

Seznam vnosov…

10 2 0 14 43 25 18 1 5 45

Razvrščen seznam elementov…

0 1 2 5 10 14 18 25 43 45

Število podaj za razvrščanje seznama: 10

Primer 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)

Izhod:

bubble_sort Izhod Java

V obeh programih smo uporabili niz 10 elementov in ga razvrstili s tehniko razvrščanja po mehurčkih. V obeh programih smo uporabili dve zanki for za iteracijo skozi sosednje elemente polja.

Na koncu vsakega prehoda (zunanja zanka) se največji element v matriki prepihne do konca polja. Štejemo tudi število prehodov, ki so potrebni za razvrščanje celotnega polja.

kako naredite lažni e-poštni naslov

Analiza kompleksnosti algoritma razvrščanja mehurčkov

Iz psevdo kode in ilustracije, ki smo jo videli zgoraj, v mehurčku naredimo primerjave N-1 v prvem prehodu, primerjave N-2 v drugem prehodu itd.

Zato je skupno število primerjav v obliki mehurčkov:

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

= N (N-1) / 2

= O (ndva) => Časovna zapletenost tehnike razvrščanja mehurčkov

Tako so spodaj podane različne zapletenosti tehnike razvrščanja mehurčkov:

Najslabša časovna zapletenostO (n 2)
Najboljša časovna zapletenostO (n)
Povprečna časovna zapletenostO (n 2)
Zapletenost prostoraO (1)

Tehnika razvrščanja oblačkov zahteva samo en dodaten pomnilniški prostor za spremenljivko temp, da olajša zamenjavo. Zato je zapletenost prostora za algoritem za razvrščanje mehurčkov O (1).

Upoštevajte, da bo časovna zapletenost tehnike razvrščanja mehurčkov najboljša, če bo seznam že razvrščen in bo O (n).

Zaključek

Glavna prednost Bubble Sort je preprostost algoritma. Pri razvrščanju oblačkov se pri vsakem prehodu največji element mehurči do konca seznama, če je polje razvrščeno v naraščajočem vrstnem redu.

Podobno za seznam, ki ga je treba razvrstiti po padajočem vrstnem redu, bo najmanjši element na svojem mestu na koncu vsakega prehoda.

Razvrščanje mehurčkov je najenostavnejše in enostavnejše za izvedbo tehnike razvrščanja, zato je običajno sortiranje predstavljeno občinstvu. Drugič, razvrščanje mehurčkov se uporablja tudi v aplikacijah, kot je računalniška grafika, pri čemer za polnjenje robov mnogokotnikov itd. Za razvrščanje oglišč, ki obdajajo poligon, zahteva razvrščanje mehurčkov.

V naši prihajajoči vadnici bomo podrobno izvedeli o razvrščanju izbora.

=> Obiščite tukaj, če se želite naučiti C ++ iz nič.

Priporočeno branje

^