Jadi , loop batin dapat menghindari melihat terakhir n-1 item ketika berjalan untuk waktu ke-n :procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do if A[i-1] > A[i] then swap(A[i-1], A[i]) swapped = true end if end for n = n - 1 until not swapped end procedure Secara umum , hal ini bisa terjadi bahwa lebih dari satu unsur ditempatkan pada posisi akhir mereka pada single pass .
Secara khusus , setelah setiap lulus , semua elemen setelah swap terakhir diurutkan , dan tidak perlu diperiksa lagi . Hal ini memungkinkan kita untuk melewatkan banyak elemen , sehingga tentang kasus terburuk peningkatan 50 % dibandingkan count ( meskipun tidak ada perbaikan dalam pertukaran penting ) , dan menambahkan sedikit kompleksitas karena kode baru subsumes " bertukar " variabel :Untuk mencapai hal ini dalam pseudocode kita menulis sebagai berikut :
procedure bubbleSort( A : list of sortable items ) n = length(A) repeat newn = 0 for i = 1 to n-1 inclusive do if A[i-1] > A[i] then swap(A[i-1], A[i]) newn = i end if end for n = newn until n = 0
end procedure Modifikasi alternatif , seperti cocktail pengocok semacam upaya untuk memperbaiki kinerja bubble sort sambil menjaga ide yang sama berulang kali membandingkan dan bertukar item yang berdekatan
In practice
Semacam gelembung, algoritma sorting yang terus langkah-langkah melalui daftar, bertukar item sampai mereka muncul dalam urutan yang benar. Daftar diplot dalam sistem koordinat Cartesian, dengan setiap titik (x, y) menunjukkan bahwa nilai y disimpan pada indeks x. Maka daftar akan diurutkan oleh Bubble sort sesuai dengan nilai setiap pixel. Perhatikan bahwa akhir terbesar akan diurutkan terlebih dahulu, dengan unsur-unsur yang lebih kecil waktu lebih lama untuk pindah ke posisi yang benar.Meskipun bubble sort yaitu salah satu dari yang paling sederhana algoritma pengurutan untuk memahami dan melaksanakan, O (n2) kompleksitas berarti bahwa efisiensi menurun secara drastis pada daftar lebih dari sejumlah kecil elemen. Bahkan di antara O sederhana (n2) algoritma pengurutan, algoritma seperti insertion sort biasanya jauh lebih efisien.Karena kesederhanaannya, bubble sort sering digunakan untuk memperkenalkan konsep algoritma, atau algoritma sorting, untuk pengantar siswa ilmu komputer. Namun, beberapa peneliti seperti Owen Astrachan telah berusaha keras untuk meremehkan bubble sort dan popularitasnya terus dalam pendidikan ilmu komputer, merekomendasikan bahwa bahkan tidak lagi diajarkan.
Jargon File, yang terkenal panggilan Bogosort "yang archetypical algoritma [sic] anehnya mengerikan", juga menyerukan bubble sort "algoritma buruk generik". Donald Knuth, dalam bukunya yang terkenal The Art of Computer Programming, menyimpulkan bahwa " bubble sort tampaknya memiliki apa-apa untuk merekomendasikan hal ini, kecuali nama yang menarik dan fakta yang mengarah ke beberapa masalah teoritis yang menarik ", beberapa di antaranya ia kemudian membahas. Bubble sort adalah asimtotik sama dalam menjalankan waktu untuk insertion sort dalam kasus terburuk, tetapi dua algoritma sangat berbeda dalam jumlah swap yang diperlukan. Hasil eksperimen seperti dari Astrachan juga menunjukkan bahwa insertion sort melakukan jauh lebih baik bahkan pada daftar acak. Untuk alasan ini banyak buku teks algoritma yang modern menghindari menggunakan algoritma bubble sort mendukung insertion sort.Bubble sort juga berinteraksi buruk dengan hardware CPU modern. Hal ini membutuhkan setidaknya dua kali lebih banyak menulis sebagai insertion sort, dua kali lebih banyak cache misses, dan mispredictions cabang asimtotik lagi.
Percobaan oleh Astrachan menyortir string di Jawa menunjukkan bubble sort menjadi sekitar seperlima secepat semacam penyisipan dan 70% secepat semacam seleksi. Dalam grafik komputer itu populer karena kemampuannya untuk mendeteksi kesalahan yang sangat kecil (seperti swap hanya dua elemen) dalam array hampir-disortir dan memperbaikinya dengan kompleksitas hanya linear (2n).
Sebagai contoh, digunakan dalam algoritma poligon mengisi, di mana melompat-lompat garis diurutkan menurut mereka koordinat x pada garis pemindaian tertentu (garis yang sejajar dengan sumbu x) dan dengan incrementing y perubahan pesanan mereka (dua elemen yang bertukar) hanya di persimpangan dari dua baris. Bubble sort merupakan algoritma semacam stabil, seperti insertion sort.
Itulah sedikit informasi semoga bermanfaat
Source = http://en.wikipedia.org/wiki/Bubble_sort
Jargon File, yang terkenal panggilan Bogosort "yang archetypical algoritma [sic] anehnya mengerikan", juga menyerukan bubble sort "algoritma buruk generik". Donald Knuth, dalam bukunya yang terkenal The Art of Computer Programming, menyimpulkan bahwa " bubble sort tampaknya memiliki apa-apa untuk merekomendasikan hal ini, kecuali nama yang menarik dan fakta yang mengarah ke beberapa masalah teoritis yang menarik ", beberapa di antaranya ia kemudian membahas. Bubble sort adalah asimtotik sama dalam menjalankan waktu untuk insertion sort dalam kasus terburuk, tetapi dua algoritma sangat berbeda dalam jumlah swap yang diperlukan. Hasil eksperimen seperti dari Astrachan juga menunjukkan bahwa insertion sort melakukan jauh lebih baik bahkan pada daftar acak. Untuk alasan ini banyak buku teks algoritma yang modern menghindari menggunakan algoritma bubble sort mendukung insertion sort.Bubble sort juga berinteraksi buruk dengan hardware CPU modern. Hal ini membutuhkan setidaknya dua kali lebih banyak menulis sebagai insertion sort, dua kali lebih banyak cache misses, dan mispredictions cabang asimtotik lagi.
Percobaan oleh Astrachan menyortir string di Jawa menunjukkan bubble sort menjadi sekitar seperlima secepat semacam penyisipan dan 70% secepat semacam seleksi. Dalam grafik komputer itu populer karena kemampuannya untuk mendeteksi kesalahan yang sangat kecil (seperti swap hanya dua elemen) dalam array hampir-disortir dan memperbaikinya dengan kompleksitas hanya linear (2n).
Sebagai contoh, digunakan dalam algoritma poligon mengisi, di mana melompat-lompat garis diurutkan menurut mereka koordinat x pada garis pemindaian tertentu (garis yang sejajar dengan sumbu x) dan dengan incrementing y perubahan pesanan mereka (dua elemen yang bertukar) hanya di persimpangan dari dua baris. Bubble sort merupakan algoritma semacam stabil, seperti insertion sort.
Itulah sedikit informasi semoga bermanfaat
Source = http://en.wikipedia.org/wiki/Bubble_sort