prinsip
Penyortiran gelembung mungkin merupakan algoritma yang dapat digunakan semua programmer dan juga salah satu algoritma yang paling akrab.
Idenya tidak rumit:
Misalkan array arr [] sekarang disortir, dan memiliki elemen N.
1. Jika n = 1: Jelas, tidak perlu mengantri. (Faktanya, diskusi ini tampaknya tidak perlu)
2. Jika n> 1:
(1) Kami mulai dengan elemen pertama dan membandingkan setiap dua elemen yang berdekatan. Jika elemen sebelumnya lebih besar dari yang berikutnya, maka yang pertama pasti akan diperingkat di belakang dalam hasil akhir. Jadi, kami bertukar dua elemen ini. Kemudian bandingkan dua elemen yang berdekatan berikutnya. Dengan cara ini, sampai sepasang elemen terakhir dibandingkan, putaran penyortiran pertama selesai. Sudah pasti bahwa elemen terakhir harus menjadi yang terbesar dalam array (karena yang relatif besar ditempatkan di belakang setiap waktu).
(2) Ulangi proses di atas, kali ini kami tidak perlu mempertimbangkan yang terakhir karena sudah diatur.
(3) Jadi sampai hanya ada satu elemen yang tersisa, elemen harus yang terkecil, dan kemudian penyortiran kami bisa berakhir. Rupanya, penyortiran N-1 dilakukan.
Dalam proses di atas, setiap kali (atau "roda" diurutkan, angka akan perlahan -lahan "melayang" dari posisi tertentu ke posisi akhir (gambar diagram skematis dan menggambar array secara vertikal), seperti gelembung, jadi disebut "metode penyortiran gelembung".
Implementasi Kode:
Public Class Bubblesort {public static void main (string [] args) {int skor [] = {67, 69, 75, 87, 89, 90, 99, 100}; untuk (int i = 0; i <skor.length -1; i ++) {// tidak hanya melakukan pemesanan n -1 untuk (int j = 0; j <skor.length -i -1; j ++) {// urutkan skor interval yang tidak terurut saat ini (0 ...... Panjang -i -1] (kisaran J sangat kritis, kisaran ini benar -benar skor {Jarak JAGA SCORE (J. nanti int temp = skor [j]; skor [j] = skor [j + 1]; skor [j + 1] = temp; }} System.out.print ("th" + (i + 1) + "Hasil penyortiran urutan:"); untuk (int a = 0; a <skor.length; a ++) {System.out.print (skor [a]+"/t"); } System.out.println (""); } System.out.print ("Hasil penyortiran akhir:"); untuk (int a = 0; a <skor.length; a ++) {System.out.print (skor [a]+"/t"); }}}
Kinerja/kompleksitas algoritma
Kami mengabaikan waktu ketika variabel loop secara otomatis meningkat dan diinisialisasi. Pertama menganalisis jumlah perbandingan algoritma. Mudah untuk melihat bahwa penyortiran gelembung di atas tanpa perbaikan akan dilakukan dalam putaran N-1 terlepas dari data input, dan berapa kali setiap putaran penyortiran perlu dibandingkan dengan penurunan dari n-1 menjadi 0. Kemudian, jumlah total perbandingan (n-1)+(n-2)+...+2+1 = (n-1) N/2 ipton (n^) (n-2)+2+2+1 = (n-1) N/2 ipt (n^2^). (Karena saya tidak tahu cara membuat kotak di sini, di sini, saya menggunakan n^2 untuk mewakili kotak, sama di bawah)
Mari kita lihat jumlah tugas. Tugas di sini mengacu pada operasi pertukaran. Untuk kode di atas, 1 pertukaran sama dengan tiga penugasan. Karena tidak setiap kali perlu ditukar, jumlah operasi penugasan terkait dengan data input. Dalam kasus terbaik, yaitu, ketika pesanan di awal, jumlah penugasan adalah 0. Dalam kasus terburuk, jumlah penugasan adalah (N-1) N/2. Dengan asumsi bahwa data input adalah distribusi rata -rata (atau "sepenuhnya acak"), kemudian sekitar setengah dari jumlah pertukaran. Dari hasil di atas, kita dapat memperoleh kasus rata -rata, dengan jumlah penugasan menjadi 3/2 * (n^2)/2 = 3/4 * (n^2).
Singkatnya, dalam hal apa pun, kompleksitas ruang penyortiran gelembung (ruang ekstra) selalu O (1).
memperbaiki
Kompleksitas waktu yang optimal ditunjukkan ketika data sepenuhnya dipesan, yaitu O (n). Dalam kasus lain, hampir selalu O (n^2). Oleh karena itu, algoritma berkinerja terbaik ketika data pada dasarnya dipesan.
Namun, bagaimana kode di atas dapat memiliki kompleksitas O (n)? Bahkan, karena hal di atas berfokus pada ide -ide dasar, itu hanya kasus paling sederhana. Untuk membuat algoritma memiliki kompleksitas O (n) dalam kasus terbaik, beberapa perbaikan perlu dilakukan. Kode yang ditingkatkan adalah:
public static void bubblesort (int [] arr) {int temp = 0; pertukaran boolean; untuk (int i = arr.length -1; i> 0; --i) {// Panjang masing -masing jenis perlu swap = false; untuk (int j = 0; j <i; ++ j) {// dari elemen pertama ke elemen i-th if (arr [j]> arr [j +1]) {temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = temp; swap = true; }} // loop j if (swap == false) {break; }} // loop i} // metode BubblesortFaktanya, karena penyortiran gelembung hampir tidak digunakan dalam kasus sejumlah besar data, variabel boolean yang ditambahkan saat menggunakan data kecil sebenarnya akan menyebabkan overhead tambahan. Jadi saya pribadi berpikir bahwa algoritma yang ditingkatkan di atas hanya murni teoretis. Biasanya, tulis saja yang sebelumnya dengan menggelegak penyortiran.
Stabilitas algoritma
Sangat mudah untuk melihat bahwa ketika elemen tetangga sama, kita tidak perlu menukar posisi mereka, jadi jenis gelembung adalah jenis yang stabil.
Algoritma skenario yang berlaku
Gagasan penyortiran gelembung sederhana dan kodenya sederhana, yang sangat cocok untuk menyortir data kecil. Namun, karena kompleksitas algoritma yang tinggi, tidak cocok untuk digunakan ketika volume data besar. Jika Anda harus menggunakannya ketika ada lebih banyak data, yang terbaik adalah meningkatkan algoritma, seperti memilih metode penyortiran.