Sortering tekniker i programmering: sortering "bubbla"

bubbelsortering inte bara anses vara den snabbaste metoden dessutom stänger den listan över de långsammaste sätt att organisera. Men det har sina fördelar. Sättet att sortera bubbla - är det mest att varken en naturlig och logisk lösning på problemet, om du vill ordna objekten i en viss ordning. En vanlig människa manuellt, till exempel, det kommer att använda dem - bara genom intuition.

Vart tog så ett ovanligt namn?

Metod namn kom upp, med hjälp av analogi luftbubblor i vattnet. Det är en metafor. Lika små luftbubblor stiger uppåt - eftersom deras densitet är större än ett fluidum (i detta fall - vattnet), och varje grupperingselement, det är ju mindre värde, desto mera gradvis vägen till toppen av listnummer.

Beskrivning av algoritmen

bubbelsortering utförs enligt följande:

• första passage: elementen i arraynumren tas av de två paren och även jämfört. Om vissa delar av två-man team första värdet är större än det andra programmet gör dem utbytesplatser;
• följaktligen det största antalet missar slutet av arrayen. Medan alla andra element förblir som de var i ett kaotiskt sätt, och kräver mer sortering;
• och kräver därför ett andra pass att det framställs i analogi med det föregående (redan beskriven) och har ett antal jämförelser - minus en;
• vid passage nummer tre jämförelser, en mindre än det andra, och två, än den första. Och så vidare;
• summera att varje passage har (alla värden i arrayen, det speciella antal) minus (passagenummer) jämförelser.

Ännu kortare algoritm av ett program kan skrivas som:

• en array av tal kontrolleras, så länge som två nummer påträffas, den andra av dem är skyldig att vara större än den första;
• felaktigt placerade i förhållande till varandra delar av array mjukvaru swappar.

Pseudokod baserat på algoritmen som beskrivs

Den enklaste implementeringen utförs enligt följande:

Sortirovka_Puzirkom förfarande;

början

cykel för j från nachalnii_index till konechii_index;

cykel för i från nachalnii_index att konechii_index-1;

om massiv [i]> massiv [i + 1] (första element som är större än en sekund), då:

(Förändring placerar värden);

änden

Naturligtvis bara förvärrar denna enkelhet situationen: den enklare algoritmen, desto mer manifesterar alla brister. Investeringskvot tid är för stor även för en liten array (här kommer i relativitetsteori: Den tid för en lekman kan tyckas liten, men i själva verket en programmerare varannan eller ens millisekund räknas).

Det tog bättre genomförande. Till exempel, med hänsyn till utbyte av värden i array platser:

Sortirovka_Puzirkom förfarande;

början

sortirovka = true;

cykel tills sortirovka = true;

sortirovka = false;

cykel för i från nachalnii_index att konechii_index-1;

om massiv [i]> massiv [i + 1] (första element som är större än en sekund), då:

(Ändra element platser);

sortirovka = true; (Identifierad att utbytet har gjorts).

End.

begränsningar

Den största nackdelen - varaktigheten av processen. Hur mycket tid utförs sorteringsalgoritm bubbla?

Ledtiden beräknas från antalet fyrkantiga siffror i arrayen - slutresultatet av det är proportionell.

Om det värsta fallet arrayen passerar så många gånger som det har element minus ett värde. Detta beror i slutändan finns det bara ett element, som har inget att jämföra, och den sista pass genom matrisen blir oanvändbar åtgärder.

Dessutom effektiv metod för sortering av ett enkelt byte, som det kallas, endast för matriser av liten storlek. Stora mängder data med hjälp av processen kommer inte att fungera: resultatet blir antingen ett fel eller fel i programmet.

värdighet

bubbelsortering är mycket lätt att förstå. Läroplanerna tekniska universitet i studiet av beställnings delar av sitt utbud passera i första hand. Metoden är enkel att implementera både programmeringsspråket Delphi (L (Delphi), och C / C ++ (C / C plus plus), en otroligt enkla värden på plats algoritm i rätt ordning och vid Pascal (Pascal). Bubble sort är idealisk för nybörjare.

På grund av nackdelarna med algoritmen används inte i fritidsändamål.

princip visuell sortering

Vilken vy av uppsättningen 8 22 4 74 44 37 1 7

Steg 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

Steg 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

Steg 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

Steg 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

Steg 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

Steg 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Steg 7 1 4 7 8 22 37 44 74

bubbelsortering exempel i Pascal

exempel:

const kol_mas = 10;

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

a, b, k: integer;

börja

writeln ( 'input', kol_mas, 'element av uppsättningen');

för a: = 1 till kol_mas göra readln (massiv [a ]);

för a: = 1 till kol_mas-1 gör att börja

för b: = a + 1 till kol_mas inte börja

om massiv [a]> massiv [ b] sedan börja

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

avsluta;

avsluta;

avsluta;

writeln ( 'efter sort');

för a: = 1 till kol_mas göra writeln (massiv [a ]);

änden.

EXEMPEL bubbla sortering i C-språk (C)

exempel:

#include

#include

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

{

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

för (;;) {

ff = 0;

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

if (massiv [i] [i- 1]) {

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

ff ++;

}

}

if (ff == 0) break;

}

getch (); // visningsfördröjnings

återvända 0;

}.