Tutorial on how to ask Python to sort a deck of playing cards. (I’m talking about sorting)

Bayangkan kamu punya deck yang isinya angka acak dan kamu terlalu malas mengurutkannya. Lalu kamu memberinya pada python untuk mengurutkannya. Pertanyaanya gimana caramu meminta python untuk mengurutkannya? perintah manusia seperti “tolong urutkan” tidak akan dipahami oleh python. Lagipula python tidak berbicara dalam bahasa Indonesia maupun Inggris

Untuk mengatasi masalahmu, ada beberapa cara atau tata cara berbahasa yang saya rekomendasikan agar python paham permintaanmu, siapkan catatan.

The Standard Library

Ini adalah cara memberi tau python dengan gaya paling simpel. Seolah kamu bilang “urutkan” kepada python. Terlihat simpel? Contohnya seperti ini

variable = [2,6,4,8,0,3,1,5,9,7]

how_to_sort = sorted(variable)      # function for sorting

print(f"before sort : {variable}")
print(f"after sort : {how_to_sort}")

Bubble Sort

Cara kedua akan lebih rumit dari cara pertama. Alih alih kamu meminta python mengurutkan, kamu malah meminta python mengecek tiap kartu (angka) yang kamu berikan padanya. Cara kerja logikanya seperti ini

1. Bayangkan ada kartu dengan urutan seperti ini [1, 5, 9, 10, ace, 6, 7, queen, 4, king, 2, jack, 3, 8]
2. kamu memberi tau python untuk membuat perulangan sebanyak jumlah kartu yang dibawa.
3. kamu memberi tau python untuk mulai mengecek apakah kartu pertama lebih besar dari kartu ke dua atau tidak. jika tidak maka kamu meminta python untuk bergeser ke kartu selanjutnya.
4. jika kartu saat ini lebih besar dari kartu yang python bandingkan setelahnya (misal ace dan 6) maka kamu meminta python untuk saling menukarkan posisi kartu. Jika kartu saat ini lebih besar, maka ditukar. Python akan terus melakukan ini sampai kartu terakhir di putaran tersebut.
5. Setelah sampai ujung, Python akan kembali ke awal untuk menyisir ulang sampai semua kartu benar-benar urut.

Simpelnya “Elemen yang lebih besar akan terus dibawa ke kanan hingga ujung atau hingga menemukan elemen yang lebih besar”

def bubble(array):
    how_many = len(array)       # calculating the amount of stored data

    for out_loop in range (how_many):     # set the number of iterations according to the amount of data stored
        sorting = True      # mark the out_loop iteration as correct

        for inner_loop in range(how_many - out_loop - 1):       # mark each iteration of the out_loop
            if array[inner_loop] > array[inner_loop + 1]:       # compare the data in the current row with the data in the adjacent row
                array[inner_loop], array[inner_loop + 1] = array [inner_loop + 1], array[inner_loop]        # swap the larger variable on the right with the smaller variable on the left
                sorting = False         # returns false if a position swap occurs

        if sorting == True:     # create a condition if the sequence is correct
            break       
    return array

jack = 11
queen = 12
king = 13
ace = 1
ex = [5, 9, 10, ace, 6, 7, queen, 4, king, 2, jack, 3, 8]
print("original :", ex)
bubble(ex)
print("after sorting :", ex)

Insertion Sort

Cara ketiga dinilai memiliki tingkat kesulitan yang mirip dengan Bubble Sort namun dengan logika yang lebih simpel. Logikanya bagaimana?

1. Bayangkan ada kartu dengan urutan seperti ini [4 ,2 ,5 ,6 ,ace ,1 ,9 ,queen ,8 ,king ,10 ,jack ,7 ,3 ]
2. Kamu meminta python untuk mengambil elemen ke dua (2)
3. Kamu meminta python untuk membandingkan elemen yang tadi dengan elemen (key) yang ada di sebelah kiri (4)
4. Kamu memberi tau python jika elemen di bagian terurut lebih besar dari key, geser elemen tersebut ke kanan. Setelah menemukan posisi yang pas (di mana elemen sebelumnya lebih kecil dari key), sisipkan key di sana.
5. Kamu memberi tau python untuk mengulanginya hingga semua terurut

Simpelnya “merapikan barisan kartu satu per satu dari kiri ke kanan”

def insertion(array):

    for repeat in range(1, len(array)):     # Count the number of data entries. The count starts at index 1 (the second entry).
        item_key = array[repeat]        # store a large amount of data 

        comparator = repeat - 1     # Determining the index of the element to the left of `item_key`

        while comparator >= 0 and array[comparator] > item_key:     # Check that the limit does not exceed index 0 and compare the element to the left
            array[comparator + 1] = array[comparator]       # Larger elements are copied or shifted one position to the right
            comparator -= 1     # Go to the previous number on the left to check it

        array[comparator + 1] = item_key        # reassign the previously saved value to the new one.
    return array

jack = 11
queen = 12
king = 13
ace = 1
example = [4 ,2 ,5 ,6 ,ace ,9 ,queen ,8 ,king ,10 ,jack ,7 ,3 ]
print("before :", example)
insertion(example)
print("after :", example)

Merge Sort

Ini adalah cara terahir yang bisa digunakan. Jika dibandingkan dengan cara sebelumya, mungkin cara ii dinilai lebih memiliki banyak langkah. Bagaimana logikanya?

1. Bayangkan ada kartu dengan urutan seperti ini [queen, 4, 8, 10, ace, 3, king, 6, 2, jack, 5, 9, 7]
2. Kamu meminta Python untuk langsung mengembalikan tumpukan kartu jika tumpukan itu kosong atau hanya tersisa 1 kartu (karena 1 kartu tidak perlu diurutkan lagi).
3. Kamu meminta python untuk menentukan titik tengah tumpukan kartu untuk membaginya menjadi dua bagian yang sama besar serta bantuan untuk mengurutkan separuh tumpukan kartu bagian kiri dengan cara yang sama (dibagi-bagi lagi sampai kecil). Kamu juga meminta bantuan untuk mengurutkan separuh tumpukan kartu bagian kanan
4. Kamu meminta python jika salah satu tangannya sudah kosong, maka dia langsung mengambil semua kartu yang tersisa di tangan satunya sebagai hasil urutan.
5. Kamu meminta python untuk menyiapkan sebuah meja kosong untuk menyusun kartu-kartu yang sedang dibandingkan.
6. Kamu meminta python untuk menandai posisi jari telunjukmu di kartu paling atas pada tumpukan kiri dan tumpukan kanan.
7. Kamu meminta python untuk terus melakukan perbandingan selama masih ada kartu di tangan kiri maupun tangan kanan yang belum diletakkan di meja.
8. Kamu meminta python untuk melihat dua kartu teratas; jika kartu di tangan kiri lebih kecil atau nilainya sama dengan kartu di tangan kanan, kamu mengambil kartu kiri tersebut.
9. Kamu meminta python untuk meletakkan kartu yang lebih kecil tadi ke meja dan menggeser jari telunjukmu ke kartu berikutnya di tumpukan tersebut.
10. Jika meminta python untuk tumpukan kanan sudah habis, kamu tidak perlu berpikir lagi — langsung sapu semua sisa kartu di tangan kiri dan tumpuk di atas meja, lalu selesai.

Intinya “memecah tiap data list yang berdiri sendiri lalu menggabungkan antar data yang bersebelahan menjadi 1 list (1 list berisi 2 data atau 1 jika ganjil) lalu diurutkan dalam waktu yang bersamaan”

def merge(left, right):
    if len(left) == 0: 
        return right    # If the left list is empty, return the right list
    if len(right) == 0:
        return left     # If the right list is empty, return the left list

    result = []     # A container for the merged results.
    index_l = index_r = 0       # Pointers indicating our position in the left and right lists.

    while len(result) < len(left) + len(right):     # The loop occurs if the number of data points in the `result` variable is fewer than the sum of the data points in the left and right parameters
        if left[index_l] <= right[index_r]:     # The code will be executed if the left side is less than or equal to the right side
            result.append(left[index_l])        # add the left side to the variable result
            index_l += 1        # shift the variable index
        else:
            result.append(right[index_r])      # add the right side to the variable result
            index_r += 1        # shift the variable index

        if index_r == len(right):
            result += left[index_l:]        # If the right list runs out first, the remaining elements in the left list are immediately appended to the result
            break
        if index_l == len(left):
            result += right[index_r:]       # If the left list runs out first, the remaining elements in the left list are immediately appended to the result
            break
    return result

def merge_sort(array):
    if len(array) < 2:      # Conditions when the list is empty or contains only one element
        return array

    mid = len(array) // 2       # finding the midpoint by dividing

    left_part = merge_sort(array[:mid])     # Split the left half and call this function again (recursively) until reach the base case.
    right_part = merge_sort(array[mid:])        # Split the right half and call this function again (recursively) until you reach the base case.

    return merge(left_part, right_part)

jack = 11
queen = 12
king = 13
ace = 1
example = [queen, 4, 8, 10, ace, 3, king, 6, 2, jack, 5, 9, 7]
print("before :", example)
example = merge_sort(example)
print("after  :", example)

Pada bagian ahir artikel, terdapat beberapa tugas yang dapat di coba. Seperti apa tugasnya?

Lakukan pengurutan array dengan nilai [64, 34, 25, 12, 22, 11, 90] menggunakan algoritma quicksort dengan bahasa pemrograman python dengan ilustrasi sebagai berikut :

Langkah 1: Pemilihan Pivotal

o Kita memilih elemen pivot. Dalam contoh ini, kita akan menggunakan elemen terakhir dari array sebagai pivot, yaitu 90.

Langkah 2: Pembagian Array Menggunakan Pivot

o Array dibagi menjadi dua bagian, dengan elemen-elemen yang lebih kecil dari pivot berada di sebelah kiri, dan elemen-elemen yang lebih besar berada di sebelah kanan.

o Array setelah pembagian: [34, 25, 12, 22, 11, 64, 90]

Langkah 3: Pengurutan Rekursif

o Kita ulangi proses ini pada kedua bagian array yang terbagi. Kita menerapkan langkah-langkah yang sama untuk setiap subarray hingga semua elemen terurut.

Langkah 4: Penggabungan Subarray

o Setelah semua subarray terurut, kita menggabungkan mereka menjadi array yang utuh.

o Array terurut: [11, 12, 22, 25, 34, 64, 90]

Bagaimana cara menjawabnya?

def tugas(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr.pop() 
    kiri = []
    kanan = []
    for elemen in arr:
        if elemen <= pivot:
            kiri.append(elemen) 
        else:
            kanan.append(elemen)  
    return tugas(kiri) + [pivot] + tugas(kanan)

ex = [64, 34, 25, 12, 22, 11, 90]
print("before :", ex)
hasil = tugas(ex)
print("Hasil pengurutan:", hasil)