Bubble Sort

SORTING

Definisi

Sorting adalah proses pengurutan data yang sebelumnya disusun secara acaka atau tidak teratur menjadi terurut menurut suatu aturan tertentu.

Sorting terbagi 2, yaitu:

1. Ascending, pengurutan data menaik (dari data terkecil sampai data terbesar)

2. Descending, pengurutan data menurun (dari data terbesar sampai data terkecil)

Teknik penukaran data (swap)

Untuk menukar dua buah data dalam dua variabel, maka kita gunakan variabel sementara (temporary). Contoh:

temp = nilai[1];

nilai[1] = nilai[2];

nilai[2] = temp;

Terdapat banyak metode pengurutan data, diantaranya:

1.  Pengurutan berdasarkan perbandingan (comparison based-sorting)

Misal: buble sort, exchange sort

2.  Pengurutan berdasarkan prioritas (priority queuesorting method)

Misal: selection sort, heap sort (menggunakan tree)

3. Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)

Misal: insertion sort, tree sort

4.  Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)

Misal: quick sort, merge sort

5.  Pengurutan berkurang menurun (diminishing increment sort method)

Misal: shell sort (pengembangan insertion sort)

 

Buble sort  adalah metode pengurutan data dengan cara membandingkan elemen yang sekarang dengan elemen berikutnya. Jika elemen yang sekarang lebih besar dari elemen berikutnya, maka posisinya ditukar, jika tidak maka posisi akan tetap (tidak ada penukaran).

Ilustrasi buble sort

 

dan seterusnya sampai terurut seperti dibawah ini

Gambar yang terakhir diatas menunjukkan satu kali iterasi sudah selesai dilakukan. Disebut satu kali iterasi yaitu dimana proses membandingkan sudah dilakukan dari elemen yang pertama sampai elemen yang terakhir. Pengulangan untuk mengurutkan data akan dilakukan sebanyak maksimal n-1 kali pengulangan, dimana n adalah banyaknya data.

Contoh program:

#include

#include

#include

main()

{

   int bil[10] = {5, 34, 32, 24, 72, 45, 3, 15, 63, 33};

   int temp;

   cout << "Data sebelum diurutkan:" << endl;

   for(int i = 0; i < 10; i++)

         cout << setw(3) << bil[i];

   cout << endl;

   for(int j = 0; j < 9; j++)

         for(int k = 0; k < 9; k++)

            if(bil[k] > bil[k+1])

             {

                  temp = bil[k];

                   bil[k] = bil[k+1];

                   bil[k+1] = temp;

             }

   cout << "Data setelah diurutkan:" << endl;

   for(int m = 0; m < 10; m++)

         cout << setw(3) << bil[m];

   getch();

}

Tampilan

Referensi

1. Lafore, Robert. 1999. Data Structures and Algorithms in 24 Hours. Sams Publishing.
2. Rahmat, Antonius. Modul Struktur Data.