Mengenal Quick Sort dan Penyelesaiannya Menggunakan Python

Feri Lukmansyah

Mengenal Quick Sort dan Penyelesaiannya Menggunakan Python – pesonainformatika.com pada studi kasus kali ini kita akan belajar tentang salah satu sorting algoritm setelah kitta belajar tentang Merge Sort dan Bubble Sort kali ini kita akan belajar tentang quick sort dan implemenrasinya menggunakan bahasa pemrograman python

Apa itu QuickSort

Quicksort adalah algoritma sorting yang cara kerjanya memilih pivot dari list dan memecah element lainya menjadi 2 bagian sublist

Ada beberapa versi quickSort yang memilih pivot dengan cara yang berbeda.

  1. Selalu Mengambil element pertama sebagai pivot
  2. Selalu mengambil element terakhir sebagai pivot
  3. mengambil item secara acak sebagai pivot
  4. mengambil median (nilai tengah) sebagai pivot

kali ini kita akan menggunakan element terakhir yang akan kita gunakan sebagai pivot (elemen yang akan dihitung)

Membuat Program

kali ini kita akan membuat program untuk mengurutkan suatu list buat file misalnya quicksort.py

sebelum membuat program kita perlu tau prosesnya untuk mengututkan dengan algoritma quicksort kita perlu memecah list nya menjadi beberapa bagian dan diurukan dahulu

disini kita perlu membuat fungsi untuk mengurutkanya misalkan namanya adalah partisi

def partisi(arr: list, low: int, high: int) -> int:
    i = low - 1
    pivot = arr[high]

    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

disini akan mengurutkan array (list) yang akan kita input dan ada berbagai parameter

  • arr adalah list yang akan diurutkan
  • low adalah parameter untuk awal index
  • high adalah parameter untuk akhir index

kemudian kita embuat fungsi untuk menerapkan algorima quicksort

def quicksort(arr: list, low: int, high: int):
    if len(arr) == 1:
        return arr
    if low < high:
        p1 = partisi(arr, low, high)
        # mengurutkan dengan quicksort
        quicksort(arr, low, p1 - 1)
        quicksort(arr, p1 + 1, high)

disini kita menggunakan recursive function untuk mengurutkan setiap liat yang tadi kita pecah dan menyatukan kembali di akhir

kemudian kita coba hitung sebuah list contoh 

array_list = [10, 7, 8, 9, 1, 5]

maka kita implementasi seperti ini

array_list = [10, 7, 8, 9, 1, 5]
n = len(array_list)
quicksort(array_list, 0, n - 1)
print(f'array yang sedang diurutkan')
for i in range(n):
    print(f'{array_list[i]}')

naka hasilnya

array yang sedang diurutkan
1
5
7
8
9
10
hasilnya

oke itu dia pembahasan studi kasus kali ini semoga bermanfaat, ikuti terus pesonainformatika, dan dapatkan studi kasus bahasa pemrograman lainya seperti  Java, Python  C++ semoga bermanfaat dan selamat mencoba source code dapat dilihat github