Algoritma Sorting (Quick Sort, Merge Sort) Pada bahasa Python

Sorting atau pengurutan merupakan proses dasar yang ada dalam sebuah algoritma dan struktur data. Dalam pemrograman , sorting merupakan bagian yang cukup sering digunakan. Tujuan utama dari proses pengurutan atau sorting adalah untuk mengurutkan data berdasarkan keinginan baik itu dari yang terendah maupun yang tertinggi, sehingga data yang dihasilkan akan lebih terstruktur, teratur dan juga sesuai dengan kebutuhan yang diinginkan.

Terdapat beberapa algoritma yang cukup populer untuk mengurutkan data, seperti bubble sort, selection sort, insertion sort, quick sort, merge sort, radix sort, shell sort dan lain sebagainya. Pada postingan kali akan menerapkan mengenai algoritma quick sort  dan merge sory menggunakan bahasa pemrograman Python. Cek juga postingan sebelumnya tentang penerapan bubble sort, selection sort dan insertion sort.

Quick Sort

Algoritma quick sort ini cara kerjanya berprinsip pada penekatan divide and conquer yakni dengan memilih satu elemen sebagai elemen pivot dan mempartisi array sehingga sisi kiri pada pivot mempunyai semua elemen dengan nilai yang lebih kecil dibandingkan dengan elmen pivot dan pada sisi kanan mempunyai semua elemen dengan nilai yang lebih besar dibandingkan dengan nilai elemen pivot.
Analogi algoritma quick sort :

• Mempunyai data A yang memiliki N elemen, pilih sembarang elemen dari data tersebut biasanya elemen pertama misalkan elemen x
• Kemudian semua elemen tersebut disusun dengan menempatkan x pada posisi j sedemikian rupa sehingga elemen ke satu sampai pada j-1 dan memiliki nilai yang lebih besar dari x
• Begitu seterusnya setiap sub data

def qs(list,awal,akhir):
    if awal < akhir:
        pindex = partisi(list,awal,akhir)
        qs(list,awal,pindex-1)
        qs(list,pindex+1,akhir)

def partisi(list,awal,akhir):
    tengah = int(akhir/2)
    pivot = list[tengah]
    pindex = awal
    for i in range(awal,tengah):
        if list[i]>=pivot:
            list[i],list[pindex]=list[pindex],list[i]
            pindex = pindex + 1
    list[pindex],list[tengah]=list[tengah],list[pindex]
    print(list)
    return pindex

list = [67,91,87,33,49,10,16,43,65,3]
print('Data yang akan di sort :', list)
print('Quick Sort :')
qs(list,0,len(list)-1)

Output dari penerapan quick sort di atas seperti pada gambar di bawah ini :

Output Quick Sort

Merge Sort

Algoritma merge sort merupakan salah satu pengurutan dengan metode memecah data kemudian mengolah untuk diselesaikan pada setiap bagian dan menggabungkan kembali sehingga data tersebut berhasil tersusun. Merge sort dalam menyelesaikan pengurutan membutuhkan fungsi rekursif.
Analogi algoritma merge sort :

• Data dipecah menjadi dua kelompok dimana kelompok pertama adalah setengah apabila data genap atau setengah kurang satu apabila data ganjil dari seluruh data.
• Kemudian dilakukan pemecahan kembali pada masing-masing kelompok hingga hanya terdapat satu data pada satu kelompok.
• Setelah digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar dari pada data ketengah ditambah satu, jika iya maka data ketengah ditambah satu dipindah menjadi data pertama.
• Kemudian data pertama tadi hngga data ketengah dipindah menjadi data kedua sampai data ketengah ditambah satu.
• Begitu seterusnya sehingga membentuk sebuah data yang tersusun dalam satu kelompok yang utuh.

def ms(list):
    print('Memecah List', list)
    n = len(list)
    if n < 2:
        return list
    else:
        mid=n//2
        left=list[:mid]
        right=list[mid:]

        ms(left)
        ms(right)
        i=0
        j=0
        k=0
        while i < len (left) and j < len (right):
            if left[i]>right[j]:
                list[k]=left[i]
                i=i+1
            else:
                list[k]=right[j]
                j=j+1
            k=k+1
        while i < len (left):
            list[k]=left[i]
            i=i+1
            k=k+1
        while j < len (right):
            list[k]=right[j]
            j=j+1
            k=k+1
    print('Menggabungkan List', list)

list = [2,5,60,43,27,10,89,17]
ms(list)

Output dari penerapan merge sort di atas seperti pada gambar di bawah ini :

Output Merge Sort

Referensi :
https://www.pythonindo.com/insertion-sort-di-python/
http://codinginpro.blogspot.com/2018/06/macam-macam-sorting-pada-python.html