Teknik dalam pemrograman memilah: menyortir "bubble"

bubble sort tidak hanya dianggap sebagai metode tercepat, apalagi, menutup daftar cara paling lambat untuk mengatur. Namun, ia memiliki keuntungan. Dengan demikian, metode pengurutan gelembung - yang paling bahwa baik adalah solusi alami dan logis untuk masalah ini, jika Anda ingin mengatur item dalam urutan tertentu. Orang biasa secara manual, misalnya, ia akan menggunakan mereka - hanya dengan intuisi.

Mana nama seperti biasa?

nama metode datang, menggunakan analogi gelembung udara di dalam air. Ini metafora. Sama seperti gelembung udara kecil naik ke atas - karena kepadatan mereka lebih besar dari cairan (dalam hal ini - air), dan masing-masing elemen array, yang lebih kecil itu adalah nilai, cara yang lebih bertahap ke puncak nomor daftar.

Deskripsi dari algoritma

bubble sort dilakukan sebagai berikut:

• pertama lulus: elemen dari nomor array yang diambil oleh dua pasang dan juga dibandingkan. Jika beberapa elemen dari nilai pertama tim dua orang lebih besar dari yang kedua, program ini membuat mereka tempat pertukaran;
• akibatnya, jumlah terbesar merindukan akhir array. Sementara semua elemen lain tetap seperti mereka, dengan cara yang kacau, dan membutuhkan lebih menyortir;
• dan oleh karena itu memerlukan kedua lulus: itu dibuat oleh analogi dengan sebelumnya (sudah dijelaskan) dan memiliki jumlah perbandingan - minus satu;
• di nomor bagian tiga perbandingan, satu kurang dari yang kedua, dan dua, dari yang pertama. Dan sebagainya;
• disimpulkan bahwa setiap bagian memiliki (semua nilai dalam array, jumlah tertentu) minus (nomor bagian) perbandingan.

algoritma bahkan lebih pendek dari sebuah program dapat ditulis sebagai:

• array nomor diperiksa selama dua nomor yang ditemukan, kedua dari mereka terikat untuk menjadi lebih besar dari yang pertama;
• tidak benar diposisikan dalam hubungan satu sama elemen lain dari swap software larik.

Pseudocode berdasarkan algoritma yang dijelaskan

Pelaksanaan yang paling sederhana dilakukan sebagai berikut:

Prosedur Sortirovka_Puzirkom;

awal

siklus untuk j dari nachalnii_index ke konechii_index;

siklus untuk i dari nachalnii_index ke konechii_index-1;

jika massiv [i]> massiv [i + 1] (elemen pertama lebih besar dari satu detik), maka:

(Perubahan menempatkan nilai-nilai);

akhir

Tentu saja, kesederhanaan ini hanya memperburuk situasi: sederhana algoritma, semakin memanifestasikan semua kekurangan. Rasio investasi waktu terlalu besar bahkan untuk array kecil (di sini datang dalam relativitas: Jumlah waktu bagi orang awam mungkin tampak kecil, tetapi sebenarnya seorang programmer setiap detik atau bahkan milidetik).

Butuh pelaksanaan yang lebih baik. Misalnya, dengan mempertimbangkan pertukaran nilai-nilai di lokasi array yang:

Prosedur Sortirovka_Puzirkom;

awal

sortirovka = true;

siklus sampai sortirovka = true;

sortirovka = false;

siklus untuk i dari nachalnii_index ke konechii_index-1;

jika massiv [i]> massiv [i + 1] (elemen pertama lebih besar dari satu detik), maka:

(Mengubah elemen tempat);

sortirovka = true; (Mengidentifikasi bahwa pertukaran telah dibuat).

End.

keterbatasan

Kerugian utama - durasi proses. Berapa banyak waktu yang dilakukan algoritma sorting bubble?

lead time dihitung dari jumlah nomor persegi di array - hasil akhir itu sebanding.

Jika kasus terburuk array dilewatkan sebanyak karena memiliki unsur-unsur minus satu nilai. Hal ini terjadi karena pada akhirnya hanya ada satu unsur yang harus ada untuk membandingkan, dan lulus terakhir melalui array menjadi tindakan sia-sia.

Selain itu, metode yang efektif pemilahan pertukaran sederhana, seperti yang disebut, hanya untuk array dari ukuran kecil. data dalam jumlah besar dengan bantuan proses tidak akan bekerja: hasilnya akan terjadi kesalahan atau kegagalan program.

martabat

bubble sort sangat mudah dimengerti. Kurikulum universitas teknis dalam studi elemen memesan array yang lulus di tempat pertama. Metode ini mudah untuk menerapkan kedua bahasa Delphi pemrograman (L (Delphi), dan C / C ++ (C / C plus plus), sebuah nilai yang sangat sederhana algoritma lokasi dalam urutan yang benar dan pada Pascal (Pascal). Bubble sort sangat ideal untuk pemula.

Karena kelemahan dari algoritma tersebut tidak digunakan dalam tujuan ekstrakurikuler.

Prinsip penyortiran Visual

Tampilan awal dari 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

semacam gelembung contoh di Pascal

contoh:

kol_mas const = 10;

var massiv: array [1..kol_mas] dari integer;

a, b, k: integer;

mulai

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

untuk: = 1 ke kol_mas melakukan Readln (massiv [a ]);

untuk: = 1 ke kol_mas-1 lakukan mulai

untuk b: = a + 1 untuk kol_mas lakukan mulai

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

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

berakhir;

berakhir;

berakhir;

writeln ( 'setelah semacam');

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

end.

CONTOH gelembung menyortir 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, ff;

untuk (;;) {

ff = 0;

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

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

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

ff ++;

}

}

jika (ff == 0) break;

}

getch (); // tampilan delay

return 0;

}.