Sorteringsmetoder i programmering: sortering med "boble"

Sortering med en boble betraktes ikke bare som den raskeste metoden, det lukker 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 må 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 med luftbobler i vann. Dette er en metafor. Akkurat som små luftbobler stiger til toppen - fordi dens tetthet er større enn noe væske (i dette tilfellet - vann), og hvert element i arrayet, jo mindre er det i verdi, jo mer går det gradvis til begynnelsen av talllisten.

Beskrivelse av algoritmen

Bubblesortering 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 andre elementer 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 en;
• Ved passet er nummer tre sammenligninger en mindre enn den andre, og to, enn den første. Og så videre;
• Vi oppsummerer at hvert pass har (i matrisen, et spesifikt tall) minus (antall passerer) sammenligninger.

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

• Antallet tall er kontrollert til 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 ;

begynner

En loop for j fra nachalnii_index til konechii_index ;

En sløyfe for jeg fra nachalnii_index til konechii_index-1 ;

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

(Endre verdiene på steder);

Enden

Selvfølgelig forsterker enkelheten bare situasjonen: jo enklere algoritmen, desto mer viser det alle manglene. Tidkrevende er for stor, selv for et lite utvalg (her kommer relativiteten: for den gjennomsnittlige personen kan tiden være liten, men i programmørens sekund eller millisekunder på kontoen).

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

Prosedyre Sortirovka_Puzirkom ;

begynner

Sortirovka = true;

Syklus mens sortirovka = true;

Sortirovka = false;

En sløyfe for jeg fra nachalnii_index til konechii_index-1 ;

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

(Vi bytter elementene på steder);

Sortirovka = true; (Indikerte at utvekslingen ble gjort).

Slutten.

Ulemper ved metoden

Den største ulempen er varigheten av prosessen. Hvor lenge virker boble sorteringsalgoritmen ?

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

I verste fall vil arrayet bli krysset så 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 ved enkle utvekslinger, som den også kalles, kun effektiv for arrays av liten størrelse. Store mengder data kan ikke behandles ved å bruke det: Resultatet blir enten feil eller et programkrasj.

verdighet

Sortering av en boble er veldig lett å forstå. I læreplanene til tekniske universiteter, når man studerer rekkefølgen av elementene i en matrise, passerer den først. Metoden er lett implementert både i Delphi programmeringsspråk (D (Delphi) og C / C ++ (C / C plus pluss)), en utrolig enkel algoritme for å ordne verdier i riktig rekkefølge og for Pascal (Pascal) . Sorteringen med en boble er ideell for nybegynnere.

På grunn av mangler, blir algoritmen ikke brukt til ekstra-kurrikulære formål.

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å sortering av 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] så 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]

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

Ff ++;

}

}

Hvis (ff == 0) bryte;

}

Getch (); // skjermforsinkelse

Tilbake 0;

}.