Paulturner-Mitchell.com / računala / Metode sortiranja u programiranju: mjehurićasto sortiranje

Tehnike sortiranja u programiranju: mjehurićasto sortiranje

Razvrstavanje mjehurića ne samo da se ne smatra najvišebrza metoda, štoviše, zatvara popis najsporijih metoda naručivanja. Međutim, ima i svojih prednosti. Dakle, sortiranje metodom mjehurića najlogičnije je i najprirodnije rješenje problema ako elemente trebate poredati u određenom redoslijedu. Na primjer, obična osoba će ga koristiti ručno - samo intuicijom.

Odakle to neobično ime?

Naziv metode izumio je analogno smjehurići zraka u vodi. Ovo je metafora. Baš kao što se mali mjehurići zraka podižu prema gore - uostalom, njihova je gustoća veća od bilo koje tekućine (u ovom slučaju vode), tako i svaki element niza, što je manji u vrijednosti, to se više postupno probija na početak popisa brojeva.

Opis algoritma

Razvrstavanje mjehurića vrši se na sljedeći način:

prvi prolazak: elemente niza brojeva uzimaju dvojica i također se uspoređuju u parovima. Ako je u bilo koja dva elementa prva vrijednost veća od druge, program mijenja njihova mjesta;
dakle, najveći broj završava na kraju niza. Iako svi ostali elementi ostaju, kao što su bili, u kaotičnom redoslijedu i dalje zahtijevaju razvrstavanje;
stoga je potreban drugi prolaz: napravljen je analogno prethodnom (već opisanom) i ima broj usporedbi - minus jedan;
prolaz broj tri ima jednu usporedbu manje od druge, a dvije manje od prve. I tako dalje;
da rezimiramo, svaki prolaz ima (ukupne vrijednosti u polju, određeni broj) minus (broj prolaza) usporedbe.

Još kraće, algoritam budućeg programa može se napisati na sljedeći način:

niz brojeva provjerava se dok se ne nađu bilo koja dva broja, a drugi od njih mora biti veći od prvog;
program zamjenjuje elemente niza koji su pogrešno smješteni jedan u odnosu na drugi.

Pseudocode na temelju opisanog algoritma

Najjednostavnija implementacija je sljedeća:

postupak Sortirovka_Puzirkom;

Početak

ciklus za f iz nachalnii_index u konechii_index;

ciklus za ja iz nachalnii_index u konechii_index-1;

ako masiv [i]> masiv [i + 1] (prvi je element veći od drugog), zatim:

(mjenjati vrijednosti na mjestima);

kraj

Naravno, ovdje jednostavnost samo pogoršavasituacija: što je algoritam jednostavniji, u njemu se više pojavljuju svi nedostaci. Potrošnja vremena previsoka je čak i za mali niz (ovdje na scenu stupa relativnost: laicima se količina vremena može činiti malom, ali u poslu programera svaka sekunda ili čak milisekunda su bitne).

Bila je potrebna bolja provedba. Na primjer, uzimajući u obzir razmjenu vrijednosti u nizu na mjestima:

postupak Sortirovka_Puzirkom;

Početak

sortirovka = istinito;

ciklom doviđenja sortirovka = istinito;

sortirovka = lažno;

ciklus za ja iz nachalnii_index u konechii_index-1;

ako masiv [i]> masiv [i + 1] (prvi je element veći od drugog), zatim:

(zamijenite elemente na mjestima);

sortirovka = istinito; (naznačeno da je razmjena izvršena).

Kraj.

Nedostaci metode

Glavni nedostatak je trajanje postupka. Koliko traje algoritam sortiranja mjehurića?

Vrijeme izvršavanja izračunava se iz kvadrata broja brojeva u nizu - konačni rezultat proporcionalan je tome.

U najgorem slučaju niz će se prećionoliko puta koliko ima elemenata umanjenih za jednu vrijednost. To je zato što na kraju ostaje samo jedan element bez ičega za usporedbu, a posljednji prolazak kroz niz postaje beskorisna akcija.

Osim toga, metoda sortiranja jednostavnimrazmjene, kako se još naziva, samo za male nizove. Uz njegovu pomoć neće biti moguće obraditi velike količine podataka: rezultat će biti ili pogreške ili kvar programa.

dostojanstvo

Razvrstavanje mjehurića vrlo je lako razumljivo.U kurikulumima tehničkih sveučilišta, to je prvo koje prolazi kada se proučava poredak elemenata niza. Metodu je jednostavno implementirati u programski jezik Delphi (D (Delphi) i C / C ++ (C / C plus plus), nevjerojatno jednostavan algoritam za slaganje vrijednosti u ispravnom redoslijedu i na Pascalu. Bubble sort idealno je za početnike.

Zbog nedostataka algoritam se ne koristi u izvannastavne svrhe.

Jasan princip sortiranja

Početni prikaz niza 8 22 4 74 44 37 1 7

Korak 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

Korak 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 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Korak 3 1 4 8 22 7 74 37 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

Korak 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Korak 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Korak 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Korak 7 1 4 7 8 22 37 44 74

Primjer sortiranja mjehurića u Pascalu

primjer:

const kol_mas = 10;

var massiv: niz [1..kol_mas] cijelog broja;

a, b, k: cijeli broj;

početi

writeln ("input", kol_mas, "elementi niza");

za a: = 1 do kol_mas do readln (massiv [a]);

za: = 1 do kol_mas-1 počinju

za b: = a + 1 do kol_mas počinje

ako massiv [a]> massiv [b] onda započnite

k: = masiv [a]; masiv [a]: = masiv [b]; masiv [b]: = k;

kraj;

writeln ("nakon sortiranja");

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

kraj.

Primjer sortiranja mjehurića u C (C)

primjer:

#include

int glavni (int argc, char * argv [])

{

int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;

jer (;;) {

ff = 0;

za (i = 7; i> 0; i -) {

ako (massiv [i] <massiv [i-1]) {

zamijeniti (massiv [i], massiv [i-1]);

ff ++;

}

if (ff == 0) break;

}

getch (); // kašnjenje zaslona

return 0;

volio: