Menyusun teknik dalam pengaturcaraan: sorting "gelembung"

isih gelembung bukan sahaja dianggap sebagai kaedah yang paling cepat, lebih-lebih lagi, ia menutup senarai satu cara yang paling perlahan untuk menganjurkan. Walau bagaimanapun, ia mempunyai kelebihannya. Oleh itu, kaedah menyusun gelembung - yang paling bahawa tidak adalah penyelesaian semula jadi dan logik kepada masalah ini, jika anda mahu untuk menyusun barangan di dalam susunan tertentu. Orang biasa secara manual, sebagai contoh, ia akan menggunakan mereka - hanya dengan gerak hati.

Di mana apa-apa nama yang luar biasa?

nama kaedah datang, menggunakan analogi gelembung udara di dalam air. Ia metafora. Sama seperti buih udara kecil meningkat ke atas - kerana ketumpatan keduanya lebih besar dari cecair (dalam kes ini - air), dan setiap elemen array, yang lebih kecil itu adalah nilai, cara lebih beransur-ansur ke atas nombor senarai.

Keterangan algoritma

isih gelembung dilakukan seperti berikut:

• pas pertama: unsur-unsur nombor mudah diambil oleh kedua-dua pasangan dan juga dibandingkan. Jika beberapa unsur-unsur nilai dua orang pasukan pertama adalah lebih besar daripada yang kedua, program ini menjadikan mereka tempat pertukaran;
• akibatnya, bilangan terbesar tersasar akhir array. Walaupun semua unsur-unsur yang lain tetap kerana mereka, dengan cara yang huru-hara, dan memerlukan lebih banyak menyusun;
• dan oleh itu memerlukan lulus kedua: ia dibuat oleh analogi dengan sebelumnya (yang telah diterangkan) dan mempunyai beberapa perbandingan - minus one;
• di nombor laluan tiga perbandingan, satu kurang daripada yang kedua, dan kedua-dua, daripada yang pertama. Dan sebagainya;
• merumuskan bahawa setiap laluan mempunyai (semua nilai dalam array, jumlah tertentu) tolak (nombor laluan) perbandingan.

algoritma lebih pendek daripada program yang boleh ditulis sebagai:

• pelbagai nombor disemak selagi mana-mana dua nombor yang ditemui, kedua mereka adalah terikat untuk menjadi lebih besar daripada yang pertama;
• kedudukan yang tidak betul berhubung dengan setiap unsur-unsur yang lain daripada swap perisian tatasusunan.

Pseudokod berdasarkan algoritma yang diterangkan

Pelaksanaan mudah dijalankan seperti berikut:

prosedur Sortirovka_Puzirkom;

bermula

kitaran untuk j dari nachalnii_index untuk konechii_index;

kitaran untuk i dari nachalnii_index untuk konechii_index-1;

jika massiv [i]> massiv [i + 1] (unsur pertama lebih besar daripada yang kedua), maka:

(Perubahan meletakkan nilai-nilai);

akhir

Sudah tentu, kesederhanaan ini hanya memburukkan keadaan: mudah algoritma, semakin ia menjelma semua kelemahan. nisbah pelaburan masa itu lebih besar walaupun di lokasi yang kecil (di sini datang dalam kerelatifan: Jumlah masa untuk orang biasa mungkin kelihatan kecil, tetapi sebenarnya seorang programmer setiap tuduhan kedua atau milisaat).

Ia mengambil masa pelaksanaan yang lebih baik. Sebagai contoh, dengan mengambil kira pertukaran nilai dalam lokasi mudah:

prosedur Sortirovka_Puzirkom;

bermula

sortirovka = true;

kitaran sehingga sortirovka = true;

sortirovka = palsu;

kitaran untuk i dari nachalnii_index untuk konechii_index-1;

jika massiv [i]> massiv [i + 1] (unsur pertama lebih besar daripada yang kedua), maka:

(Menukar unsur-unsur tempat);

sortirovka = true; (Dikenal pasti bahawa pertukaran itu dibuat).

End.

had

Kelemahan utama - tempoh proses. Berapa banyak masa yang dilakukan menyusun algoritma gelembung?

Menyebabkan masa dikira dari bilangan nombor persegi dalam array - keputusan akhir itu adalah berkadar.

Jika kes yang paling teruk lokasi itu diluluskan sebanyak yang ia mempunyai unsur-unsur tolak satu nilai. Ini berlaku kerana pada akhirnya hanya ada satu elemen, yang mempunyai apa-apa untuk membandingkan, dan pas lepas melalui array menjadi tindakan sia-sia.

Di samping itu, kaedah yang berkesan menyusun pertukaran yang mudah, kerana ia dipanggil, hanya untuk tatasusunan saiz kecil. jumlah data yang besar dengan bantuan proses tidak dapat dilakukan: hasilnya akan terjadi kesalahan atau kegagalan program ini.

maruah

isih gelembung adalah sangat mudah difahami. Kurikulum universiti teknikal dalam kajian unsur-unsur pesanan array yang lulus dalam tempat pertama. Kaedah ini mudah dilaksanakan sebagai bahasa pengaturcaraan Delphi (D (Delphi), dan C / C ++ (C / C plus plus), algoritma sangat mudah untuk lokasi nilai dalam susunan yang betul dan pada Pascal (Pascal). Bubble jenis adalah sesuai untuk pemula.

Oleh kerana kelemahan algoritma tidak digunakan dalam tujuan kurikulum.

prinsip pengasingan Visual

Pandangan awal array 8 22 4 74 44 37 1 7

Langkah 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

Langkah 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

Langkah 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

Langkah 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

Langkah 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

Langkah 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Langkah 7 1 4 7 8 22 37 44 74

gelembung contoh semacam dalam Pascal

contoh:

kol_mas const = 10;

var massiv: lokasi [1..kol_mas] daripada integer;

a, b, k: integer;

mula

writeln ( 'input', kol_mas, 'elemen array');

yang: = 1 untuk kol_mas melakukan readln (massiv [a ]);

yang: = 1 untuk kol_mas-1 melakukan mula

untuk b: = a + 1 untuk kol_mas jangan mula

jika massiv [a]> massiv [ b] kemudian mula

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

berakhir;

berakhir;

berakhir;

writeln ( 'selepas jenis');

yang: = 1 untuk kol_mas melakukan writeln (massiv [a ]);

akhir.

CONTOH gelembung menyusun dalam bahasa C (C)

contoh:

#include

#include

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

{

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

untuk (;;) {

ff = 0;

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

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

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

ff ++;

}

}

jika (ff == 0) akan dipatahkan;

}

getch (); // kelewatan paparan

kembali 0;

}.