Sortiranje tehnike programiranja: sortiranje "bubble"

bubble sort ne samo da smatra da je najbrža metoda, štaviše, on zatvara popis najsporije načina da se organizuju. Međutim, ona ima svoje prednosti. Dakle, način sortiranja bubble - najviše da niti je prirodna i logično rješenje za taj problem, ako želite organizirati stavke u određenim redoslijedom. Običan čovek ručno, na primjer, to će ih koristiti - samo intuicijom.

Odakle takvo neobično ime?

Način ime se pojavilo, koristeći analogiju mjehurića zraka u vodi. To je metafora. Baš kao što je malo mjehurića zraka rasti prema gore - jer im je gustoća veća od tekućine (u ovom slučaju - voda), i svaki element niza, manja je vrijednost, više postepeni put do vrha brojeva liste.

Opis algoritma

bubble sort se vrši na sljedeći način:

• prvom prolazu: elementi brojeva niza donosi dva para ali iu odnosu. Ako se neki elementi dva čoveka tim prva vrijednost je veća od druge, program ih čini razmjena mjestima;
• Shodno tome, najveći broj promašaja na kraju niza. Dok su svi ostali elementi ostaju kao što su bili, u haotičnom način, i zahtijevaju više sortiranje;
• i stoga zahtijevaju drugom prolazu: je napravljen po analogiji sa prethodnim (već opisano) i ima broj poređenja - minus jedan;
• u prolazu broj tri poređenja, jedan manje od sekunde, i dva, od prve. I tako dalje;
• sumirati da svaki odlomak ima (sve vrijednosti u nizu, određeni broj) minus (prolaz broj) poređenja.

Čak i kraće algoritam programa se može pisati kao:

• niz brojeva provjerava se onoliko dugo koliko su pronašli nikakve dva broja, drugi od njih će sigurno biti veći nego prvi;
• nepravilno pozicionirani u odnosu na druge elemente niza softvera swap.

Pseudo na osnovu algoritma opisan

Najjednostavnija implementacija se vrši na sljedeći način:

Sortirovka_Puzirkom postupka;

početak

ciklus za j od nachalnii_index do konechii_index;

ciklusa i iz nachalnii_index do konechii_index-1;

ako massiv [i]> massiv [i + 1] (prvi element veći od jedne sekunde), a zatim:

(Promjeni postavlja vrijednosti);

kraj

Naravno, ovo jednostavnost samo pogoršava situaciju: jednostavniji algoritam, više se manifestuje sve nedostatke. odnos uloženog vremena je prevelika čak i za male niz (ovdje dolazi u relativnosti: Iznos vrijeme za laik može činiti mala, ali u stvari, programer svake sekunde ili čak milisekundi računa).

Bilo je to bolje implementacije. Na primjer, uzimajući u obzir razmjene vrijednosti na lokacijama niza:

Sortirovka_Puzirkom postupka;

početak

sortirovka = true;

ciklus do sortirovka = true;

sortirovka = false;

ciklusa i iz nachalnii_index do konechii_index-1;

ako massiv [i]> massiv [i + 1] (prvi element veći od jedne sekunde), a zatim:

(Promijeniti elementi mjesta);

sortirovka = true; (Utvrdi da je izvršena razmjena).

Kraj.

ograničenja

Glavni nedostatak - trajanje procesa. Koliko vremena se izvodi algoritam sortiranja balon?

Olovo put se izračunava na osnovu broja kvadrata brojeva u nizu - krajnji rezultat je proporcionalan.

Ako najgorem slučaju je niz prošlo onoliko puta koliko ima elemenata minus jednu vrijednost. To se događa zbog toga što se na kraju postoji samo jedan element, koji nemaju ništa za usporedbu, a posljednji kroz niz postaje beskoristan akciju.

Pored toga, efikasna metoda sortiranja jednostavne razmjene, kako se zove, samo za nizove malih dimenzija. Velike količine podataka uz pomoć procesa neće raditi: rezultat će biti ili greška ili neuspjeh programa.

dostojanstvo

bubble sort je vrlo lako razumjeti. Nastavnim planovima i programima tehničkih fakulteta u proučavanju naručivanje elemenata svoje niza proći na prvom mjestu. Metoda je lako implementirati i na Delphi programskom jeziku (L (Delphi), kao i C / C ++ (C / C plus plus), izuzetno jednostavan vrijednosti lokacije algoritma u pravom red i na Pascal (Pascal). Bubble vrsta je idealna za početnike.

S obzirom na nedostatke algoritma se ne koristi u vannastavnim svrhe.

princip Visual sortiranje

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 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 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

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

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

bubble sort primjer u Pascalu

primjer:

const kol_mas = 10;

var massiv: array [1..kol_mas] od cijeli broj;

a, b, k: integer;

početi

writeln ( 'input', kol_mas, 'elemenata niza');

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

za: = 1 do kol_mas-1 do početi

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

ako massiv [a]> massiv [ b], a zatim početi

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

završiti;

završiti;

završiti;

writeln ( 'nakon vrstu');

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

kraj.

PRIMJER balon sortiranje u jeziku C (C)

primjer:

#include

#include

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

{

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

za (;;) {

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 (); // prikaz kašnjenje

return 0;

}.