» » Pengurutan

Pengurutan

Algoritma Pengurutan


> Dalam ilmu komputer, algoritma pengurutan (sorting adalah):
1. algoritma yang meletakkan elemen-elemen suatu kumpulan data dalam urutan tertentu atau
2. prosees pengurutan data yang sebelumnya disusun secara acak sehingga

menjadi tersusun secara teratur menurut suatu aturan tertentu
> Yang pada kenyataannya ‘urutan tertentu’ yang umum digunakan adalah

terurut secara numerikal ataupun secara leksikografi (urutan abjad
sesuai kamus)
> Ada 2 jenis sorting : Ascending & Descending

Bubble Sort (Pengurutan Apung)

Pengertian/Konsep Bubble Sort

Bubble Sort adalah salah satu algoritma untuk sorting data, atau kata lainnya mengurutkan data dari yang terbesar ke yang terkecil atau sebaliknya (Ascending atau Descending).
Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.
                Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.
Algoritma bubble sort adalah salah satu algoritma pengurutan yang paling simple, baik dalam hal pengertian maupun penerapannya. Ide dari algoritma ini adalah mengulang proses pembandingan antara tiap-tiap elemen
array dan menukarnya apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi. Algoritma
ini termasuk dalam golongan algoritma comparison sort, karena menggunakan perbandingan dalam operasi antar elemennya. Berikut ini adalah gambaran dari algoritma bubble sort. Misalkan kita mempunyai sebuah array dengan.  Elemen-elemen “4 2 5 3 9”. Proses yang akan terjadi apabila digunakan algoritma bubblesort adalah sebagai berikut.

Pass pertama
(4 2 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 4 3 5 9)
Pass kedua
(2 4 3 5 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
Pass ketiga
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)

Dapat dilihat pada proses di atas, sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun algoritma tetap dilanjutkan hingga pass kedua berakhir. Pass ketiga dilakukan karena definisi terurut dalam algoritma bubblesort adalah tidak ada satupun penukaran pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverifikasi keurutan array tersebut.

Algoritma Bubble Sort


  • Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritme menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).
  • Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn 5 … ; n-1 dgn n.
  • Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dgn data ke-2, dst.
    •
  • Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

Contoh Kasus Bubble Sort

Misalkan kita punya data seperti ini: 6, 4, 3, 2 dan kita ingin mengurutkan data ini (ascending) dengan menggunakan bubble sort. Berikut ini adalah proses yang terjadi:
Iterasi ke-1: 4, 6, 3, 2 :: 4, 3, 6, 2 :: 4, 3, 2, 6 (ada 3 pertukaran)
Iterasi ke-2: 3, 4, 2, 6 :: 3, 2, 4, 6 :: 3, 2, 4, 6 (ada 2 pertukaran)
Iterasi ke-3: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 1 pertukaran)
Iterasi ke-4: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6 (ada 0 pertukaran) -> proses selesai

        Kompleksitas Algoritma Bubble Sort


Kompleksitas Algoritma Bubble Sort dapat dilihat dari beberapa jenis kasus, yaitu worst-case, average-case, dan best-case.

Ø  Kondisi Best-Case

Dalam kasus ini, data yang akan disorting telah terurut sebelumnya, sehingga proses perbandingan hanya dilakukan sebanyak (n-1) kali, dengan satu kali pass.
Proses perbandingan dilakukan hanya untuk memverifikasi keurutan data. Contoh Best-Case dapatdilihat pada pengurutan data “1 2 3 4” di bawah ini.

Pass Pertama
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)

Dari proses di atas, dapat dilihat bahwa tidak terjadi penukaran posisi satu kalipun, sehingga tidak dilakukan pass selanjutnya. Perbandingan elemen dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya dilakukan sebanyak (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini adalah O(n). Dengan kata lain, pada kondisi Best-Case algoritma Bubble Sort termasuk pada algoritma
lanjar.


Ø  Kondisi Worst-Case

Dalam kasus ini, data terkecil berada pada ujung array. Contoh Worst-Case dapat dilihat pada pengurutan data “4 3 2 1” di bawah ini.

Pass Pertama
(4 3 2 1) menjadi (3 4 2 1)
(3 4 2 1) menjadi (3 2 4 1)
(3 2 4 1) menjadi (3 2 1 4)
Pass Kedua
(3 2 1 4) menjadi (2 3 1 4)
(2 3 1 4) menjadi (2 1 3 4)
(2 1 3 4) menjadi (2 1 3 4)
Pass Ketiga
(2 1 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Pass Keempat
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)

Dari langkah pengurutan di atas, terlihat bahwa setiap kali melakukan satu pass, data terkecil akan bergeser ke arah awal sebanyak satu step. Dengan kata lain, untuk menggeser data terkecil dari urutan keempat menuju urutan pertama, dibutuhkan pass sebanyak tiga kali, ditambah satu kali pass untuk memverifikasi. Sehingga jumlah proses pada kondisi best case dapat dirumuskan sebagai berikut. Jumlah proses = n2+n (3)
Dalam persamaan (3) di atas, n adalah jumlah elemen yang akan diurutkan. Sehingga notasi Big-O yang didapat adalah O(n2). Dengan kata lain, pada kondisi worst-case, algoritma Bubble Sort termasuk dalam kategori algoritma kuadratik.

Ø  Kondisi Average-Case

Pada kondisi average-case, jumlah pass ditentukan dari elemen mana yang mengalami penggeseran ke kiri paling banyak. Hal ini dapat ditunjukkan oleh proses pengurutan suatu array, misalkan saja (1 8 6 2). Dari (1 8 6 2), dapat dilihat bahwa yang akan mengalami proses penggeseranpaling banyak adalah elemen 2, yaitu sebanyak dua kali.

Pass Pertama
(1 8 6 2) menjadi (1 8 6 2)
(1 8 6 2) menjadi (1 6 8 2)
(1 6 8 2) menjadi (1 6 2 8)
Pass Kedua
(1 6 2 8) menjadi (1 6 2 8)
(1 6 2 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
Pass Ketiga
(1 2 6 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)

Dari proses pengurutan di atas, dapat dilihat bahwa untuk mengurutkan diperlukan dua buah passing,ditambah satu buah passing untuk memverifikasi. Dengan kata lain, jumlah proses perbandingan dapat dihitung sebagai berikut. Jumlah proses = x2+x (4) Dalam persamaan (4) di atas, x adalah jumlahpenggeseran terbanyak. Dalam hal ini, x tidak pernah lebih besar dari n, sehingga x dapat dirumuskan sebagai
Dari persamaan (4) dan (5) di atas, dapat disimpulkan bahwa notasi
big-O nya adalah O(n2). Dengan kata lain, pada kondisi average case algoritma Bubble Sort termasuk dalam algoritma kuadratik.

Implementasi dalam Pseudo-Code

Setiap algoritma akan memiliki implementasi yang berbeda, tergantung dari bahasa program yang dipakai. Oleh karena itu berikut ini adalah pseudo-code dari algoritma bubblesort, untuk memudahkan implementasi bubblesort pada bahasa apapun.

procedure bubbleSort( A : list of
sortable items ) defined as:
do
swapped := false
for each i in 0 to length(A) - 2
inclusive do:
if A[i] > A[i+1] then
swap( A[i], A[i+1] )
swapped := true
end if
end for
while swapped
end procedure

Kelebihan Bubble Sort


  • Metode Buble Sort merupakan metode yang paling simpel
  • Metode Buble Sort mudah dipahami algoritmanya

Kekurangan Bubble Sort

Meskipun simpel metode Bubble sort  merupakan metode pengurutanyang paling tidak efisien.  Kelemahan buble sorttadalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika  data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.

Selection Sort (Pengurutan Seleksi)


Pengertian/Konsep Selection Sort

         Algoritma pengurutan sederhana salah satunya adalah Selection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen yang paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya, kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting descending (menurun), elemen yang paling besar yang disimpan indeksnya kemudian ditukar. Selection Sort diakui karena kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu. Algoritma ini bekerja sebagai berikut: 1.  Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list 2.  Menukarkan nilai ini dengan elemen pertama list 3. Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua. Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan

Algoritma Selection Sort


    Algoritma pengurutan selection sort ini termasuk algoritma sulit dibagi/ mudah digabung (hard split/easy join).  Dari proses pengurutannya, Selection sort ini memiliki dua buah varian yaitu :
    1. Maximum Sort
    memilih data yang maksimum dari suatu kumpulan data larik, lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data maksimum/minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data maksimum berikutnya.
    2. Minimum Sort
    memilih data yang minimum dari suatu kumpulan data larik , lalu menempatkan data tersebut ke elemen paling akhir atau paling awal sesuai pengurutan yang diinginkan. Data minimum yang diperoleh, “diisolasi” dan tidak diikutsertakan pada proses pencarian data minimum berikutnya.
    Dalam pemecahan masalah algoritma selection sort , kita dapat memilih dua metode alternatif algoritma antara lain pemecahan dengan metode Brute Force dan pemecahan dengan metodedevide and conquer.

    Simulasi Selection Sort  

    Untuk lebih jelasnya, perhatikanlah simulasi Selection Sort Ascending berikut dengan menggunakan larik  
    Dalam satu kali pass, ditentukan elemen yang paling kecil di dalam bagian list yang belum urut. Elemen yang paling kecil ini, diwarnai merah . Untuk bagian larik yang telah  diurutkan diberi warna biru.  

    Notasi Algoritmik Selection Sort  


            Kompleksitas Selection Sort  

            Algoritma di dalam Selection Sort terdiri dari kalang bersarang. Dimana kalang tingkat pertama (disebut pass) berlangsung N-1 kali. Di dalam kalang kedua, dicari elemen dengan nilai terkecil. Jika didapat, indeks yang didapat ditimpakan ke variabel min. Lalu dilakukan proses penukaran. Begitu seterusnya untuk setiap Pass. Pass sendiri makin berkurang hingga nilainya menjadi semakin kecil. Berdasarkan operasi perbandingan elemennya: 

                Berarti kompleksitasnya secara simptotik adalah O(n2). Adapun grafik efisiensi selection sort dapat dilihat pada tabel dibawah ini: 
           Pengurutan  model ini tergolong buruk dan lebih baik dihindari penggunaannya, terutama untuk penanganan tabel dengan lebih dari 1000 elemen. Karena masih ada algoritma lain yang implementasinya sama mudahnya, namun performansinya jauh lebih baik. Algoritma yang dimaksud adalah insertion sort.  

    Kelebihan Selection Sort

    1.       Algoritma ini sangat rapat dan mudah untuk diimplementasikan.
    2.       Operasi pertukarannya hanya dilakukan sekali saja.
    3.       Waktu pengurutan dapat lebih ditekan.
    4.       Mudah menggabungkannya kembali.
    5.       Kompleksitas selection sort relatif lebih kecil.

    Kekurangan Selection Sort

    1.       Membutuhkan method tambahan.
    2.       Sulit untuk membagi masalah.

    Insertion Sort (Pengurutan Sisip)

    Pengertian/Konsep Insertion Sort

           Algoritma insertion sort adalah sebuah algoritma sederhana yang cukup efisien untuk mengurutkan sebuah list yang hampir terurut. Algorima ini juga bisa digunakan sebagai bagian dari algoritma yang lebih canggih. Cara kerja algoritma ini adalah dengan mengambil elemen list satu-per-satu dan memasukkannya di posisi yang benar seperti    namanya. Pada array, list yang baru dan elemen sisanya dapat berbagi tempat di array, meskipun cukup rumit. Untuk menghemat memori, implementasinya menggunakan pengurutan di tempat yang membandingkan elemen saat itu dengan elemen sebelumnya yang sudah diurut, lalu menukarnya terus sampai posisinya tepat. Hal ini terus dilakukan sampai tidak ada elemen tersisa di input. Seperti sudah dibahas di bagian pendahuluan, salah satu implementasinya pada kehidupan sehari-hari adalah saat kita mengurutkan kartu remi. Kita ambil kartu satuper-satu lalu membandingkan dengan kartu sebelumnya untuk mencari posisi yang tepat. Variasi pada umunya yang dilakukan terhadap array pada insertion sort adalah sebagai berikut :
    • Elemen awal di masukkan sembarang, lalu elemen berikutnya dimasukkan di bagian paling akhir. 
    • Elemen tersebut dibandingkan dengan elemen ke (x-1). Bila belum terurut posisi elemen sebelumnya digeser    sekali ke kanan terus sampai elemen yang sedang diproses menemukan posisi yang tepat atau sampai          elemen pertama. 
    • Setiap pergeseran akan mengganti nilai elemen berikutnya, namun hal ini tidak menjadi persoalan sebab elemen berikutnya sudah diproses lebih dahulu. 

    Ilustrasi Selection Sort


      Ilustrasi: Sebelum di-insert:  
      Data terurut parsial Data belum terurut 
      Setelah di- insert:  
           
      Insertion sort ini memiliki beberapa keuntungan :  Implementasi yang sederhana  Paling efisien untuk data berukuran kecil  Merupakan online algorithmic, yang berarti bisa langsung melakukan sort setiap ada data baru  Proses di tempat (memerlukan O(1) memori tambahan)  Stabil.  
      Pada tahun 2004 Bender, Farach-Colton, and Mosteiro menemukan pengembangan baru dari algoritma ini, disebut library sort atau gapped insertion sort yang menggunakan beberapa gap kosong di sepanjang array. Dengan algoritma ini, pergeseran elemen dilakukan sampai gap tersebut dicapai. Algoritma ini cukup baik dengan kompleksitas O(n log n).

      Simulasi Selection Sort  

      Berikut ini adalah contoh dari simulasi Insertion Sort.   
      Setiap satu kali Pass akan ada satu nilai yang disisipkan. Kemudain pada Pass n-1 data akan terurut.  
      Data yang telah terurut diberi warna abu-abu. Panah menunjukkan perubahan posisi nilai yang akan di-insert. 

      Notasi Algoritmik Insertion Sort  

      Procedure InsertionSort (Input/Output T: TabInt, Input N: integer) {mengurut tabel integer [1 .. N] dengan Insertion Sort secara ascending}  

      Kamus: 










      Kompleksitas Selection Sort  

            Algoritma Insertion Sort juga terdiri dari 2 kalang bersarang. Dimana terjadi N-1 Pass (dengan N adalah banyak elemen struktur data), dengan masing-masing Pass terjadi i kali operasi perbandingan. i tersebut bernilai 1 untuk Pass pertama, bernilai 2 untuk Pass kedua, begitu seterusnya hingga Pass ke N-1.   


                   Secara Kompleksitas, selection sort dan insertion sort mempunyai Big-Oh yang sama. Walaupun begitu, insertion sort sebenarnya lebih mangkus. Perhatikan gambar berikut:   


              Berdasarkan gambar, Insertion Sort 40% lebih cepat daripada Selection Sort. Namun, Insertion Sort mempunyai kekurangan. Insertion Sort  lebih baik tidak digunakan untuk menangani struktur data dengan lebih dari 2000 elemen.  

      Kelebihan Insertion Sort

      1.        Sederhana dalam penerapannya.
      2.        Mangkus dalam data yang kecil.
      3.        Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkan dengan  Quicksort.
      4.        Mangkus dalam data yang sebagian sudah terurut.
      5.        Lebih mangkus dibanding Bubble Sort dan Selection Sort.
      6.        Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan  tercepat pada jumlah elemen yang sedikit.
      7.        Stabil.

      Kekurangan Insertion Sort

      1.         Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.
      2.       Untuk larik yang jumlahnya besar ini tidak praktis.
      3.       Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh  bagian sebelum menyisipkan elemen berikutnya.
      4.       Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen  dalam jumlah besar.

      Referensi



      Langganan: Posting Komentar ( Atom )