Algoritma Sorting (Bubble Sort, Seletion Sort, Insertion Sort) Pada Python

Pengurutan atau sorting merupakan proses dasar yang ada dalam sebuah algoritma dan struktur data. Pada pemrograman , sorting merupakan bagian yang cukup sering dipergunakan. 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 sesuai dengan kebutuhan.

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 membahas mengenai algoritma bubble sort, selection sort dan insertion sort yang akan diimplimentasikan menggunakan bahasa pemrograman Python. Pada postingan berikutnya akan membahasa quick sort dan merge sort.

Bubble Sort

Algoritma bubble sort cukup populer dan sederhana. Proses pada bubble sort dilakukan dengan penukaran data disebelahnya secara terus menerus hingga dalam suatu iterasi tertentu tidak ada lagi perubahan atau pertukaran. Algoritma bubble sort termasuk ke dalam kategori algoritma comparison sort, karena menggunakan perbandingan pada operasi antar elemenya.
Analogi algoritma bubble sort :

• Bandingkan nilai pada data ke satu dengan data ke dua
• Apabila nilai data ke satu lebih besar dari data ke dua maka tukar posisinya
• Kemudian data yang lebih besar tersebut dibandingkan lagi dengan data ketuga
• Apabila data ke tiga lebih kecil dari data ke dua maka tukar posisinya
• Dan begitu seterusnya hingga semua data yang ada menjadi terurut

def bs(list):
    iterasi = 0
    for j in range (len(list)-1):
        for i in range(len(list)-1-j):
            if list[i]>list[i+1]:
                list[i],list[i+1]=list[i+1],list[i]
        iterasi+=1
        print(iterasi, list)

list = [9,17,2,42,1,7,3,4,67]
print('Data yang akan di sort :', list )
print('Bubble Sort :')
bs(list)

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

Output Bubble Sort

Selection Sort

Algoritma selection sort merupakan pengurutan dengan konsep memilih elemen dengan nilai paling rendah dan menukar elemen tersebut dengan elemen ke –i. Nilai dari i dimulai dari 1 ke n, yang dimana n merupakan jumlah total elemen dikurangi satu.
Analogi algoritma selection sort :

• Memulai pengecekan data dari data ke 1 hingga data ke n.
• Menentukan bilangan dengan index terkecil dari data pada bilangan tersebut.
• Menukar bilangan index terkecil dengan bilangan pertama.
• Begitu seterusnya hingga data berhasil diurutkan semuanya.

def ss(list):
    iterasi = 0
    for i in range(len(list)-1):
        minimal = i
        for j in range(i+1,len(list)):
            if list[j] < list[minimal]:
                minimal = j
        iterasi += 1
        list[minimal],list[i]=list[i], list[minimal]
        print(iterasi, list)
list=[98,6,33,11,57,33,44,55,29,76,60,81]
print('Data yang akan di sort :', list )
print('Selection Sort :')
ss(list)

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

Output Selection Sort

Insertion Sort

Algoritma insertion sort merupakan suatu metode pengurutan data dengan melakukan penempatan setiap elemen data pada pisisina dengan membandingkan dengan data-data yang telah ada. Prinsip dari insertion sort adalah dengan membagi data yang akan diurutkan menjadi dua kelompok, satu kelompok yang belum diurutkan dan yang satunya lagi sudah diurutkan, Elemen yang pertama diambil dari kelompok list yang belum diurutkan dan kemudian ditempatkan sesuai posisinya pada bagian lain yang belum diurutkan.
Analogi Algoritma insertion sort

• Membandingkan data kedua dengan data kesatu
• Apabila data ke dua lebih kecil maka tukar posisinya
• Data ketiga dibandingkan dengan data kesatu dan kedua
• Apabila data ketiga lebih kecil tukar lagi posisinya
• Data keempat dibandingkan dengan data ketiga hingga kesatu
• Apabila data keempat lebih kecil dari ketigana maka letakkan data keempat ke posisi paling depan
• Begitu seterusnya hingga tidak ada lagi data yang dapat dipindahkan.

def insertion(list):
    for j in range(len(list)-1,-1,-1):
        value = list[j]
        hole = j
        while hole <(len(list)-1) and list[hole+1]>list[hole]:
            list[hole] = list[hole+1]
            hole = hole+1
            list[hole] = value
        print(list)
list = [2,54,38,76,23,56,84,90]
print("Data yang akan di sort", list)
print("Insertion Sort :")
insertion(list)

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

Output Insertion Sort

Cek juga postingan penerapan quick sort dan merge sort pada bahasa Python.

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