Quicksort di Java Menggunakan LinkedList


Quicksort merupakan salah satu metode pengurutan data yang tercepat. Metode ini sebenarnya dapat dilakukan terhadap kumpulan data yang dikumpulkan di array maupun linkelist, namun saya akan memberikan ilmu saya yang sedikit dari pengurutan data pada linkedlist melalui metode ini.

Logikanya adalah pada awalnya kita akan memilih pivot sebagai data yang hendak kita pindahkan posisinya, pada program saya saya mengambil data pertama. Kemudian urut dari kanan ke kiri kita mencari nilai yang lebih kecil dari data pivot untuk kita tukar posisinya dengan pivot, kemudian urut dari kiri ke kanan kita cari nilai yang lebih besar dari pivot untuk kita tukar dengan pivot, terus kita lakukan hingga tidak ada lagi yang lebih kecil di sebelah kiri pivot dan lebih besar di sebelah kanan pivot. Kemudian dari pivot itu kita bagi dua kumpulan data tersebut menjadi sebelah kiri pivot dan sebelah kanan pivot, untuk kemudian kita lakukan hal serupa dengan kumpulan data sebelumnya yang merupakan gabungan dua kumpulan data tersebut.

Logikanya memang sedikit rumit. Perulangan yang dilakukan tidak dapat dilakukan dengan perulangan biasa sehingga menggunakan metode rekursif yang akan berhenti apabila data telah urut.

Source Code :

public void quicksort(int pivot,int kiri,int pospivot,int kanan)
{
while(true)
{
boolean knbenar = false;
boolean krbenar = false;
for(int i=kanan;i>=pospivot;i–)
{
if(i==pospivot)
knbenar = true;
else if(pivot<search(i))
{
add(search(i),pospivot);
add(pivot,i);
pospivot = i; //pivot di tukar dengan i yang merupakan lebih besar besar dari pivot
break;
}
}for(int i=kiri;i<=pospivot;i++)
{
if(i==pospivot)
krbenar = true;
else if(pivot>search(i))
{
add(search(i),pospivot);
add(pivot,i);
pospivot = i; //pivot di tukar dengan i yang merupakan lebih besar kecil dari pivot

break;
}
}
if(knbenar & krbenar)
break;
}
if(kiri<pospivot-1)
quicksort(search(kiri),kiri,kiri,pospivot-1);
if(kanan>pospivot+1)
quicksort(search(pospivot+1),pospivot+1,pospivot+1,kanan);
}

Nb : methode search() silakan anda buat sendiri dengan metode-metode yang menurut anda lebih baik

9 respons untuk ‘Quicksort di Java Menggunakan LinkedList

  1. akbarindonesia berkata:

    utk dancpm :
    keuntungan linkedlist dibandingin array, yaitu ga ada batas maksimum data yang disimpan,
    sedangkan array kan kita harus mengeset dari awal batas maksismumnya, ketika berlebihan bisa jadi ga efektif pengalokasian memori ketika kurang maka tidak semua data bisa disimpan.

    klo linkedlist bikin sendiri biasanya memang lebih lambat,
    klo make List(untuk C#) atau ArrayList(untuk java) insyaAllah bisa cepat…

  2. akbarindonesia berkata:

    utk kurt :
    Quicksort merupakan salah satu metode sorting data,
    dan konon sampai saat ini belum ada yang bisa menandingi kecepatannya dalam mengurutkan data dalam jumlah besar…

    kegunaan linkedlist tidak jauh beda dengan array,
    namun kelebihannya kita tidak perlu mengeset jumlah maksimum data sehingga data yang dapat disimpan tidak terhingga

  3. fjar berkata:

    mw nanya…
    dari source code yang ab buat itu..

    kira2 ada ga, worst case, average case and best case(maaf dalam bahsa londo…)??

    kasi tw donk…

    salam….

  4. akbarindonesia berkata:

    utk fjar :
    ada mas, tapi waktu membuat fungsi tersebut saya belum sempat meneliti kasus2 yang mungkin terjadi…

  5. budi berkata:

    apakah contoh kegunaanya seperti pada tree binary.. semisal list member di suatu mlm?
    __________________________________________________
    linkedlist berbeda dengan binary tree…
    linkedlist bersifat seperti manik2 yang disambung ke dalam sebuah benang secara berurutan,
    sedangkan binary tree layaknya pohon atau akar pohon yang terus bercabang dengan jumlah maksimal 2…

    list member bisa menggunakan kedua-duanya tergantung kepada desain aplikasi…

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google

You are commenting using your Google account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s