Algoritma - Sort Bubble

Sorting dalam algoritma adalah pengurutan data dengan proses menyusun elemen – elemen dengan tata urut tertentu sehingga bisa terimplementasi dalam bermacam aplikasi. Penyortiran ini mengacu pada pengaturan data dalam format tertentu. Pentingnya penyortiran dilakukan karena pada faktanya pencarian data dapat dioptimalkan ke tingkat yang sangat tinggi sehingga data dapat disimpan dalam cara yang disortir.

Penyortiran juga digunakan untuk merepresentasikan data dalam format yang lebih mudah dibaca. Beberapa aplikasi penyortiran dalam kehidupan real dapat anda temukan pada teknologi telekomunikasi seperti direktori telepon yang menyimpan nomor telepon orang yang disortir menurut nama mereka sehingga nama-nama tersebut dapat dicari dengan mudah. Atau pada kamus yang menyimpan kata-kata dalam urutan abjad sehingga pencarian kata apa pun menjadi mudah.

Semua algoritma penyortiran dalam algoritma menggunakan struktur data dari jenis tertentu untuk mendemonstrasikan penyortiran, mis. integer 32 bit sering digunakan sebagai terkait operasi (mis. <,>, dll) jelas dalam perilaku mereka. Atau algoritma yang dibahas dapat dengan mudah diterjemahkan ke dalam generic sorting algoritma rithms dalam bahasa pilihan masing-masing user.

Anda mungkin sering menjumpai pembahasan yang menyajikan beberapa algoritma yang memecahkan masalah sorting seperti

  • Input: Nomor urut n (a1,a2,a3,………,an)
  • Output: Permutasi (penataan ulang)(a’1,a’2,a’3,………a’n) dari urutan input tersebut dimana a’1 ≤ a’2 ≤ a’3……… ≤ a’n

Urutan input biasanya merupakan array n-elemen, meskipun mungkin diwakili dengan cara lain, seperti daftar tertaut.

Dalam prakteknya, angka yang akan diurutkan jarang merupakan nilai yang terisolasi. Setiap bagian biasanya merupakan kumpulan data yang disebut record. Setiap record berisi key, yang merupakan nilai yang akan disortir. Sisa dari record terdiri dari data satelit, yang biasanya dibawa berkeliling dengan key. Dalam prakteknya, ketika algoritma penyortiran mengubah key, itu juga harus mengubah data satelit. Jika setiap record mencakup sejumlah besar data satelit, kami sering mengonversi array pointer ke rekaman daripada catatan itu sendiri untuk meminimalkan pergerakan data.

Algoritma penyortiran menjelaskan metode yang digunakan untuk menentukan urutan yang diurutkan, terlepas dari apakah kita menyortir angka individu atau record besar yang berisi banyak byte data satelit. Jadi, ketika berfokus pada masalah penyortiran, kita biasanya berasumsi bahwa input hanya terdiri dari angka. Maka m enerjemahkan suatu algoritma untuk menyortir angka ke dalam program untuk menyortir record secara konseptual mudah.

Algoritma Sorting mungkin memerlukan beberapa ruang ekstra untuk perbandingan dan penyimpanan sementara dari beberapa elemen data. Algoritma ini tidak memerlukan ruang tambahan dan penyortiran dikatakan terjadi di tempat, atau misalnya, dalam array itu sendiri. Ini disebut penyortiran di tempat. Bubble sort adalah contoh penyortiran di tempat. Dan inilah yang akan kita bahas pada materi kali ini.

Namun sebelum masuk materi bubble sort, penting untuk diketahui mengapa perlu melakukan sorting? Banyak ilmuwan komputer menganggap sorting sebagai masalah paling mendasar dalam studi algoritma. Ada beberapa alasan:

Terkadang suatu aplikasi secara inheren perlu mengurutkan informasi. Misalnya, untuk menyiapkan laporan pelanggan, bank perlu menyortir cek dengan jumlah cek.

Algoritma sering menggunakan penyortiran sebagai kunci subrutin. Sebagai contoh, sebuah program yang membuat objek grafis yang berlapis di atas satu sama lain mungkin harus mengurutkan objek sesuai dengan “above” hubungan sehingga dapat menarik objek-objek ini dari bawah ke atas. Kita akan melihat banyak algoritma dalam teks ini yang menggunakan penyortiran sebagai subrutin.

Kita bisa menggambar dari berbagai macam algoritma penyortiran, dan mereka menggunakan serangkaian teknik yang kaya. Bahkan, banyak teknik penting yang digunakan di seluruh desain algoritma muncul di tubuh algoritma penyortiran yang telah dikembangkan selama bertahun-tahun. Dengan cara ini, sorting juga merupakan masalah kepentingan historis.

Sekarang kita masuk ke bubble sort, ini merupakan bentuk penyortiran yang paling sederhana dengan membandingkan setiap item dengan setiap item lain, setiap pasangan elemen yang berdekatan dibandingkan dan elemen-elemen bertukar jika mereka tidak berurutan. Algoritma ini tidak cocok untuk kumpulan data besar karena rata-rata dan kompleksitas kasus terburuknya adalah Ο (n2) dengan n adalah jumlah item. Di setiap mata kuliah algoritma atau struktur data, pasti ketemu sama algoritma sederhana yang satu ini. Kelebihan dari algoritma ini adalah mudah dipahami dan yang paling simpel.

Cara kerja algortima ini dengan menganalisis pasangan elemen dari kiri ke kanan, atau awal hingga akhir. Jika elemen paling kiri dalam pasangan kurang dari elemen paling kanan, pasangan akan tetap dalam urutan itu. Jika elemen paling kanan kurang dari elemen paling kiri, maka dua elemen akan dialihkan. Siklus ini berulang dari awal hingga akhir hingga terjadi kelulusan di mana tidak ada pergantian

Example A: 5, 12, 3, 9, 16 :
Pass 1
● 5, 12, 3, 9, 16
○ Daftarnya tetap sama karena 5 kurang dari 12.
● 5, 3,12, 9, 16
○ 3 dan 12 diganti karena 3 kurang dari 12
● 5, 3, 9, 12, 16
○ 9 dan 12 diganti karena 9 kurang dari 12
● 5, 3, 9, 12,16
○ 12 dan 16 tidak beralih karena 12 kurang dari 16

Pass 2
● 3, 5, 9, 12, 16
○ 3 kurang dari 5, jadi mereka beralih
● 3, 5 , 9, 12, 16
○ 5 kurang dari 9 sehingga tetap di tempat yang sama
● 3, 5, 9 , 12, 16
○ 12 lebih besar dari 9 sehingga mereka tidak bertukar tempat
● 3, 5, 9, 12,16
○ 12 dan 16 berada dalam urutan numerik sehingga mereka tidak beralih

Running Time dari Bubble Sort of Data Set Ukuran n

● Kasus-Terbaik: O (n). Ini adalah kasus urutan yang sudah diurutkan
   ○ (n)(1) = n
● Kasus Terburuk: O (n ^ 2). Maksimum, akan ada n melewati data, dan setiap pass/lewati data akan menguji pasangan n-1
   ○ (n)(n-1) = n^2
● Rata-rata: O (n ^ 2).

Mengoptimalkan Algoritma:

● Salah satu cara untuk membuat bubble sort lebih efisien adalah dengan mempertimbangkan fakta bahwa setelah itu pass/lewat, angka i terakhir akan menjadi di tempat yang benar
● Ini mengurangi waktu berjalan hingga setengahnya.
     ○ (n) (n / 2) = (n ^ 2) / 2
● Namun, banyak yang berpendapat bahwa sementara ini mengoptimalkan Running Time untuk skenario terburuk, ini menjadikan istilah "bubble sort" tidak valid untuk jenis algoritme ini

Algoritmanya anda bisa lihat seperti ini:

Kita menganggap daftar adalah array n elemen. Kami lebih lanjut mengasumsikan bahwa fungsi swap nilai-nilai elemen array yang diberikan.

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for

   return list

end BubbleSort

Kita amati dalam algoritma Bubble Sort membandingkan setiap pasangan elemen array kecuali seluruh array benar-benar disortir dalam urutan menaik. Ini dapat menyebabkan beberapa masalah yang rumit seperti bagaimana jika array tidak perlu lagi tertukar karena semua elemen sudah naik. Sehingga dalam mengatasi masalah ini, kita akan gunakan satu pertukaran variabel swapped yang akan membantu untuk melihat apakah swap telah terjadi atau tidak. Jika tidak ada swap yang terjadi, yaitu array tidak memerlukan lebih banyak proses untuk disortir, maka akan keluar dari loop.

Algoritma Pseudocode dari BubbleSort dapat ditulis sebagai berikut

procedure bubbleSort( list : array of items )

   loop = list.count;

   for i = 0 to loop-1 do:
      swapped = false

      for j = 0 to loop-1 do:

         /* bandingkan elemen yang berdekatan */   
         if list[j] > list[j+1] then
            /* tukar/swap objeknya */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if

      end for

      /* jika tidak ada nomor yang bertukar itu berarti
		array diurutkan sekarang, pecahkan loop.*/

      if(not swapped) then
         break
      end if

   end for

end procedure return list