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