Pengurutan Data Secara Advanced Dengan Quick Sort

Ini adalah metode pengurutan terakhir yang akan saya tulis di blog ini.Karena untuk metode lain seperti Heap Sort, Counting Sort,Radix Sort dll mungkin itu udah terlalu susah untuk dipahami takutnya kepala anda meledak.Gak gak bercanda kok.Untuk metode yang saya sebutkan tadi butuh pemahaman lebih itu saja

Nah,kali ini kita akan bahas Quick Sort.Quick Sort ini mengandalkan titik pivot dan kemudian membandingkannya dengan elemen lain.Seperti apa sih cara menggunakannya ?


Misal saya punya data seperti 32,21,44,25,47,28,35 dan saya akan urutkan secara Ascending

1) Ambil titik sembarang sebagai titik pivot.Supaya 4gampang saya pilih elemen terakhir 35 sebagai titik pivot.Kita tempatkan 35 di tengah-tengah yang nantinya di isi elemen

32 21 44 25 47 28 35

                 35

2) Bandingkan elemen satu per satu dengan pivot.Jika lebih kecil,maka tempatkan di kiri pivot.Jika lebih besar,tempatkan di kanan pivot

32 21 44 25 47 28

32 35

32 21 44 25 47 28

32 21 35

32 21 44 25 47 28

32 21 35 44

32 21 44 25 47 28

32 21 25  35 44

32 21 44 25 47 28

32 21 25  35 44 47

32 21 44 25 47 28

32 21 25 28  35 44 47

3) Proses belum selesai di sini bagi jadi 2 partisi ada 7 elemen berarti 4 elemen untuk partisi kiri dan 3 elemen untuk partisi kanan.Tentukan pivot masing-masing partisi kemudian lakukan langkah seperti tadi

32 21 25 28 (Partisi kiri)

35 44 47 (Partisi kanan)

Partisi Kiri

32 21 25 28

28 32

32 21 25 28

21 28 32

32 21 25 28

21 25 28 32

Karena di kanan pivot hanya tinggal satu elemen berarti tidak usah dibagi lagi untuk partisi kiri kita mendapatkan 21 25 28 32

Partisi Kanan

35 44 47

Partisi kanan sudah urut di sini berarti tinggal digabungkan dengan partisi kiri untuk mendapatkan hasil pengurutan yaitu 21 25 28 32 35 44 47

PseudoCode Untuk QuickSort

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

Penerapan di Java dan Python

Java Quick Sort
class Contoh { void sort(int[]arr,int low, int high){ if (low < high){ int p = partition(arr,low,high); sort(arr,low,p-1); sort(arr,p+1,high); } } int partition(int[]arr,int low, int high){ int pivot = arr[high]; int i = low-1; for (int j=low;j<high;j++){ if(arr[j] < pivot){ i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } void printArray(int[]arr){ int n = arr.length-1; for(int i=0;i<n;i++){ System.out.print(arr[i]+ " "); } System.out.println(); } public static void main (String[]args){ int[] arr = {32,21,44,25,47,28,35}; int low = 0; int high = arr.length-1; System.out.println("Sebelum Quick Sort :"); Contoh ob = new Contoh(); ob.printArray(arr); System.out.println("Sesudah Quick Sort :"); ob.sort(arr, low, high); ob.printArray(arr); } }

Python Quick Sort


def sort(arr,low,high): if low < high: p = partition(arr,low,high) sort(arr,low,p-1) sort(arr,p+1,high) def partition(arr,low,high): pivot = arr[high] i = low for j in range(low,high): if arr[j] < pivot : temp = arr[i] arr[i] = arr[j] arr[j] = temp i= i+1 temp = arr[i] arr[i] = arr[high] arr[high]= temp return i def printArray(arr): for i in arr: print(i,end=" ") print() arr = [32,21,44,25,47,28,35] print("Sebelum Quick Sort:") printArray(arr) print("Sesudah Quick Sort:") low = 0 high = len(arr)-1 sort(arr,low,high) printArray(arr)