Šķirošanas metodes programmēšanā: šķirošana "burbulis"

burbulis kārtot ne tikai uzskatīta par visātrāko, turklāt, tas aizveras sarakstu vislēnāko veidus, kā organizēt. Tomēr tas ir savas priekšrocības. Tādējādi metode šķirošanas burbulis - visvairāk, ka neviena no tām nav dabisks un loģisks risinājums problēmai, ja jūs vēlaties, lai sakārtotu vienumus noteiktā secībā. Parasts cilvēks manuāli, piemēram, tā tos izmantot - tikai ar intuīciju.

Kur bija tik neparastu vārdu?

Metodes nosaukums nāca klajā, izmantojot analoģiju gaisa burbuļi ūdenī. Tā ir metafora. Tāpat kā mazi gaisa pūslīši paceltos augšup - jo to blīvums ir lielāks nekā šķidrumu (šajā gadījumā - ūdens), un katra masīva elementu, jo mazāka tā ir vērtība, jo vairāk pakāpenisku ceļu uz augšu no saraksta numuru.

Apraksts algoritma

burbulis kārtošanas tiek veikta šādi:

• pirmais pass: elementi masīva skaitļiem tiek veikti ar diviem pāriem un arī salīdzinot. Ja daži no divu cilvēku komandu pirmā vērtība elementi ir lielāka nekā otrā, programma ļauj tiem apmainīties vietām;
• Līdz ar to, lielākais skaits no kļūdām beigām masīva. Kamēr visi pārējie elementi paliek, jo tie bija, haotiskā veidā, un prasa vairāk šķirošana;
• un tāpēc ir nepieciešama otra caurlaide: tas ir izgatavots pēc analoģijas ar iepriekšējo (minēts iepriekš), un ir vairāki salīdzinājumi - mīnus viens;
• pie pasāžas numuru trīs salīdzinājumus, viena mazāk nekā sekundi, un divi, nekā pirmā. Un tā tālāk;
• Rezumējot ka katrs fragments ir (visas vērtības, kas ir masīvs, noteiktu skaitu) mīnus (fragments skaits) salīdzināšanu.

Pat īsāks algoritms programmas var rakstīt šādi:

• masīvs skaitļu tiek pārbaudīta tik ilgi, kamēr tiek atrastas divi cipari, otrais no tiem ir pienākums būt lielāks nekā pirmais;
• nepareizi novietots attiecībā pret otru elementu masīva programmatūras mijmaiņas darījumiem.

Pseudocode balstoties uz algoritmu, kas aprakstīts

Vienkāršākais īstenošana tiek veikta šādi:

Sortirovka_Puzirkom procedūra;

sākums

cikls j no nachalnii_index līdz konechii_index;

cikls i no nachalnii_index līdz konechii_index-1;

ja Massiv [i]> Massiv [i + 1] (pirmais elements ir lielāks nekā otrā), tad:

(Pārmaiņas liek vērtības);

beigas

Protams, tas vienkāršība tikai pasliktina situāciju: vienkāršāku algoritmu, jo vairāk tas izpaužas visus trūkumus. Ieguldījumu īpatsvars laiks ir pārāk liels, pat par nelielu masīvs (šeit nāk relativitāti: laika summa lajs var likties mazs, bet patiesībā ir programmētājs katru otro vai pat milisekunžu skaitu).

Pagāja labāku īstenošanu. Piemēram, ņemot vērā apmaiņu vērtībām masīva vietās:

Sortirovka_Puzirkom procedūra;

sākums

sortirovka = true;

cikls līdz sortirovka = true;

sortirovka = false;

cikls i no nachalnii_index līdz konechii_index-1;

ja Massiv [i]> Massiv [i + 1] (pirmais elements ir lielāks nekā otrā), tad:

(Mainīt elementus vietām);

sortirovka = true; (Konstatēts, ka apmaiņa ir veikta).

End.

ierobežojumi

Galvenais trūkums - ilgums procesā. Cik daudz laika tiek veikta šķirošanas algoritmu burbulis?

Lead laiks tiek aprēķināts no skaita kvadrātveida numuriem masīvā - gala rezultātā tas ir samērīgs.

Ja sliktākajā gadījumā masīvs ir pagājis tik daudz reižu, cik tas ir elementi, mīnus vienu vērtību. Tas notiek tāpēc, ka galu galā ir tikai viens elements, kas nav ko salīdzināt, un pēdējais caurlaide caur masīvs kļūst bezjēdzīgi darbība.

Turklāt efektīva metode šķirošanas vienkāršu apmaiņu, kā to sauc, tikai bloki mazo izmēru. Lielu datu apjomu, izmantojot procesu, nestrādās: rezultāts būs vai nu kļūda vai neveiksmes programmas.

cieņa

burbulis kārtošanas ir ļoti viegli saprast. Tehnisko universitāšu pētījumu pasūtīšanas elementiem tās masīva mācību programmas iet pirmajā vietā. Metode ir viegli īstenot gan Delphi programmēšanas valodu (L (Delphi), un C / C ++ (C / C plus plus), kas ir neticami vienkārši vērtības vietu algoritma pareizā secībā, un pie Pascal (Pascal). Bubble kārtošanas ir ideāls iesācējiem.

Sakarā ar trūkumiem algoritma netiek izmantots ārpusskolas mērķiem.

Visual kārtošana princips

Sākotnējo skats no masīva 8 22 4 74 44 37 1 7

Step 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

Step 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

Step 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

Step 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

Step 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

Step 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Step 7 1 4 7 8 22 37 44 74

burbulis šķirot piemērs Pascal

piemērs:

const kol_mas = 10;

VAR Massiv: array [1..kol_mas] of integer;

a, b, k: integer;

sākt

writeln ( "input", kol_mas, 'elementi masīva');

par a: = 1 līdz kol_mas do readln (Massiv [v ]);

par a: = 1 līdz kol_mas-1 do sākt

B: = a + 1, lai kol_mas do sākt

ja Massiv [a]> Massiv [ b], tad sākas

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

galu;

galu;

galu;

writeln ( "pēc veida");

par a: = 1 līdz kol_mas do writeln (Massiv [v ]);

beigas.

PIEMĒRS burbulis šķirošana C valodā (C)

piemērs:

#include

#include

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

{

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

par (;;) {

ff = 0;

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

ja (Massiv [i] [i- 1]) {

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

ff ++;

}

}

ja (ff == 0) break;

}

getch (); // displejs aizkavēšanās

atgriezties 0;

}.