Sorteringsmetoder i programmering: sortering med "boble"

Sortering etter boble anses ikke bare som mestved en rask metode lukker den også listen over de langsommere måtene å bestille. Men det har også sine fordeler. Så, sortering etter boblemetoden er den mest logiske og naturlige løsningen på problemet, hvis du vil ordne elementene i en bestemt rekkefølge. En vanlig person, for eksempel, vil bruke den for hånd, bare ved intuisjon.

Hvor kom dette uvanlige navnet fra?

Navnet på metoden ble oppfunnet ved hjelp av en analogi medluftbobler i vannet. Dette er en metafor. På samme måte som små luftbobler stiger oppover - fordi deres tetthet er større enn et fluid (i dette tilfellet - vann), og hvert gruppeelement, jo mindre det er verdien er, jo mer gradvis måte til toppen av listenummer.

Beskrivelse av algoritmen

Sortering etter boble utføres som følger:

• det første passet: elementene i gruppen av tall er tatt i to og sammenlignes også i par. Hvis i noen av elementene den første verdien er større enn den andre, gjør programmet utveksling av steder;
• Derfor er det største tallet på slutten av arrayet. Mens alle de andre elementene forblir, som de var, i en kaotisk rekkefølge og krever ytterligere sortering;
• Derfor er det nødvendig med et andre pass: det er produsert analogt med den forrige (allerede beskrevet) og har en rekke sammenligninger - minus ett;
• Ved passet er nummer tre sammenligninger en mindre enn den andre, og to, enn den første. Og så videre;
• La oss oppsummere at hvert pass har (i matrisen, et bestemt tall) minus (antall passerer) sammenligninger.

Enda kortere algoritme for det fremtidige programmet kan skrives som følger:

• arrayet av tall er sjekket inntil to tall er funnet, hvorav det andre må være større enn det første;
• feil plassert i forhold til hverandre elementer i arrayet, bytter programmet.

Pseudokode basert på den beskrevne algoritmen

Den enkleste implementeringen er som følger:

prosedyre Sortirovka_Puzirkom;

Begynnelsen

sykle for j fra nachalnii_index opp til konechii_index;

sykle for jeg fra nachalnii_index opp til konechii_index-1;

om massiv [i]> massiv [i + 1] (det første elementet er større enn det andre), da:

(endre verdiene på steder);

Enden

Selvfølgelig, her forenkler bare enkelhetenSituasjon: Jo enklere algoritmen, desto mer viser det alle manglene. Investerings forholdet tiden er for stor selv for en liten gruppe (her kommer i relativitets: Tiden for lekmann kan virke lite, men faktisk en programmerer hvert sekund eller enda millisekund teller).

Det tok en bedre gjennomføring. For eksempel, tar du hensyn til verdisetting i matrisen på enkelte steder:

prosedyre Sortirovka_Puzirkom;

Begynnelsen

sortirovka = true;

syklus til sortirovka = true;

sortirovka = false;

sykle for jeg fra nachalnii_index opp til konechii_index-1;

om massiv [i]> massiv [i + 1] (det første elementet er større enn det andre), da:

(vi bytter elementene på steder);

sortirovka = true; (indikerte at utvekslingen ble gjort).

Enden.

Ulemper ved metoden

Den største ulempen er prosessens varighet. Hvor lenge virker boble sorteringsalgoritmen?

Utførelsestiden beregnes fra kvadratet av antall tall i gruppen - sluttresultatet er proporsjonalt med det.

I verste tilfelle vil arrayet bli beståttså mange ganger som det er elementer i det, minus en verdi. Dette er fordi det til slutt er bare ett element som ikke har noe å sammenligne med, og det siste passerer gjennom arrayet blir en ubrukelig handling.

I tillegg er metoden for sortering enkelutveksling, som det også kalles, bare for arrays av liten størrelse. Store datamengder kan ikke behandles ved å bruke det: Resultatet blir enten feil eller feil i et program.

verdighet

Sortering av en boble er veldig enkel å forstå. I læreplanene til tekniske universiteter, når de studerer rekkefølgen av elementene i en matrise, passerer den først. Metoden er enkel å implementere både Delphi programmeringsspråk (L (Delphi), og C / C ++ (C / C pluss pluss), en utrolig enkel verdier av plassering algoritme i riktig rekkefølge og på Pascal (Pascal). Bubble typen er ideell for nybegynnere.

På grunn av mangler, blir algoritmen ikke brukt til ekstrautdanning.

Et klart prinsipp for sortering

Den opprinnelige visningen av gruppen er 8 22 4 74 44 37 1 7

Trinn 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

Trinn 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

Trinn 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

Trinn 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

Trinn 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

Trinn 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Trinn 7 1 4 7 8 22 37 44 74

Eksempel på å sortere en boble i Pascal

eksempel:

const kol_mas = 10;

var massiv: array [1..kol_mas] av heltall;

a, b, k: heltall;

begynne

writeln ("input", kol_mas, "elementer av array");

for a: = 1 til kol_mas gjør readln (massiv [a]);

for a: = 1 til kol_mas-1 begynner

for b: = a + 1 til kol_mas begynner

hvis massiv [a]> massiv [b] da begynner

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

end;

end;

end;

writeln ("etter sort");

for a: = 1 til kol_mas gjør writeln (massiv [a]);

slutten.

Eksempel på sortering med en boble i C (C)

eksempel:

#include

#include

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

{

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

for (;;) {

ff = 0;

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

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

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

ff ++;

}

}

hvis (ff == 0) bryte;

}

getch (); // skjermforsinkelse

returner 0;

}.