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.
- Selalu Mengambil element pertama sebagai pivot
- Selalu mengambil element terakhir sebagai pivot
- mengambil item secara acak sebagai pivot
- 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
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
people who use linux and people who are friendly