Metode - Metode Algoritma Sorting Dalam Pemrograman

 Kali ini kita akan membahas metode - metode Algoritma Sorting yang digunakan pada Bahasa Pemrograman pada umumnya termasuk Python.


1. Bubble Sort

Bubble Sort merupakan metode sorting yang paling sederhana namun paling tidak efisien. Cara kerja Bubble Sort meliputi membandingkan dan menukar pasangan elemen yang berdekatan berulang kali hingga seluruh array terurut. Metode ini seringkali digunakan pada data yang berjumlah kecil dan akan memakan waktu yang sangat lama jika digunakan pada data yang berjumlah besar.


2. Selection Sort

Cara kerja Selection Sort meliputi mencari elemen terkecil/terbesar dari bagian yang belum diurutkan berulang kali dan menukarnya ke posisi yang benar di awal/akhir array. Metode ini melakukan sedikit pertukaran dibandingkan Bubble Sort.


3. Insertion Sort

Metode Insertion Sort mirip dengan cara orang bermain kartu. Caranya menyisipkan kartu lembar demi selembar kartu dan menyisipkannya ke tempat atau urutan yang seharusnya. Insertion Sort menganggap elemen pertama sudah terurut, kemudian menyisipkan elemen berikutnya ke posisi yang tepat di bagian yang sudah terurut. Sangat efisien untuk data yang berjumlah kecil dan hampir terurut.


4. Merged Sort

Merged Sort menggonakan metode Divide and Conquer (Bagi dan Taklukan). Cara kerjanya ialah memecah list menjadi dua dari titik tengah list hingga sublist hanya berisikan satu elemen kemudian menggabungkan sublist secara terurut.


5. Quick Sort

Quick Sort adalah metode yang paling efisien dan paling sering digunakan pada saat ini. Cara kerjanya kurang lebih sama seperti Merged Sort tetapi memilih sebuah elemen sebagai pivot dan mempartisi array menjadi dua sub-array yakni elemen yang lebih kecil dari pivot dan elemen yang lebih besar dari pivot. Kemudian mengurutkan sub-array secara rekursif.


Contoh Program Python beserta outputnya

#data awal
data = [6, 2, 9, 1, 3, 5, 7, 2]

#untuk pengoperasian fungsi merge sort dan quick sort
step = 1
global step

#bubble sort
def bubble_sort(arr):
  a = arr.copy()
  n = len(a)
  print("\nBubble Sort --- Visualisasi Proses\n")
  print("Data awal:", a, "\n")

  step_count = 1 #agar tidak bertabrakan dengan dengan 'step' milik merge sort dan quick sort
  for i in range(n):
    for j in range(0, n - i - 1):
      print(f"Step {step_count}")
      print(a)
      print(" " * (j*3) + " ^  ^ (bandingkan)")
      if a[j] > a[j+1]:
        a[j], a[j+1] = a[j+1], a[j]
        print("Swap >", a, "\n")
      else:
        print("Tidak swap\n")
      step_count += 1

    print("Hasil akhir:", a)
#selection sort
def selection_sort(arr):
  a = arr.copy()
  print("Selection Sort --- Visualisasi Proses\n")
  print("Data awal:", a, "\n")

  step_count = 1
  n = len(a)

  for i in range(n):
    min_idx = i
    print(f"Mulai dari indeks {i}, cari nilai minimum...")

    for j in range(i+1, n):
      print(f"Bandingkan {a[j]} dengan {a[min_idx]}")
      if a[j] < a[min_idx]:
        min_idx = j
        print(f"-> Update minimum sekarang {a[min_idx]}")
    a[i], a[min_idx] = a[min_idx], a[i]
    print(f"Step {step_count}: Swap -> {a}\n")
    step_count += 1
  print("Hasil akhir:", a)

#insertion sort
def insertion_sort(arr):
  a = arr.copy()
  print("Insertion Sort --- Visualisasi Proses\n")
  print("Data awal:", a, "\n")

  step_count = 1
  for i in range(1, len(a)):
    key = a[i]
    print(f"Ambil kunci ({key}) dari inndeks {i}")
    j = i - 1

    while j >= 0 and key < a[j]:
      print(f"Step {step_count}: geser {a[j]}")
      a[j + 1] = a[j]
      print(a, "\n")
      step_count += 1
      j -= 1
    a[j + 1] = key
    print(f"Tempatkan kunci -> {a}\n")
    step_count +=1

  print("Hasil akhir:", a)

#merged sort
def merge(arr, depth=0):
  global step

  indent = " " * depth
  print(f"{indent}Pisah: {arr}")

  if len(arr) <= 1:
    print(f"{indent} Kembali -> {arr}")
    return arr

  mid = len(arr) // 2
  left = merge(arr[:mid], depth+1)
  right = merge(arr[mid:], depth+1)

  merged = []
  i = j = 0
  print(f"{indent}Gabungkan {left} + {right}")

  while i < len(left) and j < len(right):
    if left[i] < right[j]:
      merged.append(left[i])
      i += 1
    else:
      merged.append(right[j])
      j += 1

  merged.extend(left[i:])
  merged.extend(right[j:])
  return merged

def merge_sort(data_arr):
    global step
    step = 1
    print("\nMerge Sort --- Visualisasi Proses\n")
    print("Data awal:", data_arr, "\n")
    hasil = merge(data_arr)
    print("\nHasil akhir:", hasil)

#quick sort
def quick(arr, depth=0):
  global step
  indent = " " * depth

  if len(arr) <= 1:
    print(f"{indent}Kembali -> {arr}")
    return arr

  pivot = arr[len(arr)//2]
  left = [x for x in arr if x < pivot]
  mid = [x for x in arr if x == pivot]
  right = [x for x in arr if x > pivot]

  print(f"{indent}Step {step}: Pivot={pivot}")
  print(f"{indent}Left ={left}")
  print(f"{indent}Mid ={mid}")
  print(f"{indent}Right={right}\n")
  step += 1

  return quick(left, depth+1) + mid + quick(right, depth+1)

def quick_sort(data_arr):
  global step
  step = 1
  print("\nQuick Sort --- Visualisasi Proses\n")
  hasil = quick(data_arr)
  print("\nHasil akhir:", hasil)

#exit
def exit():
  print("Sampai jumpa lagi!")
  return 0

#halaman utama
def menu():
  print("Data: ")
  print(data)
  print("\n")
  print("Menu")
  print("1. Bubble Sort")
  print("2. Selection Sort")
  print("3. Insertion Sort")
  print("4. Merge Sort")
  print("5. Quick Sort")
  print("6. Exit")

  pilihan = input("Silahhkan pilih operasi: ")

  if pilihan == "1":
    bubble_sort(data)

  elif pilihan == "2":
    selection_sort(data)

  elif pilihan == "3":
    insertion_sort(data)

  elif pilihan == "4":
    merge_sort(data)

  elif pilihan == "5":
    quick_sort(data)

  elif pilihan == "6":
    exit()

menu()

Output:

Data: [6, 2, 9, 1, 3, 5, 7, 2] Menu 1. Bubble Sort 2. Selection Sort 3. Insertion Sort 4. Merge Sort 5. Quick Sort 6. Exit Silahhkan pilih operasi: 1 Bubble Sort --- Visualisasi Proses Data awal: [6, 2, 9, 1, 3, 5, 7, 2] Step 1 [6, 2, 9, 1, 3, 5, 7, 2] ^ ^ (bandingkan) Swap > [2, 6, 9, 1, 3, 5, 7, 2] Step 2 [2, 6, 9, 1, 3, 5, 7, 2] ^ ^ (bandingkan) Tidak swap Step 3 [2, 6, 9, 1, 3, 5, 7, 2] ^ ^ (bandingkan) Swap > [2, 6, 1, 9, 3, 5, 7, 2] Step 4 [2, 6, 1, 9, 3, 5, 7, 2] ^ ^ (bandingkan) Swap > [2, 6, 1, 3, 9, 5, 7, 2] Step 5 [2, 6, 1, 3, 9, 5, 7, 2] ^ ^ (bandingkan) Swap > [2, 6, 1, 3, 5, 9, 7, 2] Step 6 [2, 6, 1, 3, 5, 9, 7, 2] ^ ^ (bandingkan) Swap > [2, 6, 1, 3, 5, 7, 9, 2] Step 7 [2, 6, 1, 3, 5, 7, 9, 2] ^ ^ (bandingkan) Swap > [2, 6, 1, 3, 5, 7, 2, 9] Hasil akhir: [2, 6, 1, 3, 5, 7, 2, 9] Step 8 [2, 6, 1, 3, 5, 7, 2, 9] ^ ^ (bandingkan) Tidak swap Step 9 [2, 6, 1, 3, 5, 7, 2, 9] ^ ^ (bandingkan) Swap > [2, 1, 6, 3, 5, 7, 2, 9] Step 10 [2, 1, 6, 3, 5, 7, 2, 9] ^ ^ (bandingkan) Swap > [2, 1, 3, 6, 5, 7, 2, 9] Step 11 [2, 1, 3, 6, 5, 7, 2, 9] ^ ^ (bandingkan) Swap > [2, 1, 3, 5, 6, 7, 2, 9] Step 12 [2, 1, 3, 5, 6, 7, 2, 9] ^ ^ (bandingkan) Tidak swap Step 13 [2, 1, 3, 5, 6, 7, 2, 9] ^ ^ (bandingkan) Swap > [2, 1, 3, 5, 6, 2, 7, 9] Hasil akhir: [2, 1, 3, 5, 6, 2, 7, 9] Step 14 [2, 1, 3, 5, 6, 2, 7, 9] ^ ^ (bandingkan) Swap > [1, 2, 3, 5, 6, 2, 7, 9] Step 15 [1, 2, 3, 5, 6, 2, 7, 9] ^ ^ (bandingkan) Tidak swap Step 16 [1, 2, 3, 5, 6, 2, 7, 9] ^ ^ (bandingkan) Tidak swap Step 17 [1, 2, 3, 5, 6, 2, 7, 9] ^ ^ (bandingkan) Tidak swap Step 18 [1, 2, 3, 5, 6, 2, 7, 9] ^ ^ (bandingkan) Swap > [1, 2, 3, 5, 2, 6, 7, 9] Hasil akhir: [1, 2, 3, 5, 2, 6, 7, 9] Step 19 [1, 2, 3, 5, 2, 6, 7, 9] ^ ^ (bandingkan) Tidak swap Step 20 [1, 2, 3, 5, 2, 6, 7, 9] ^ ^ (bandingkan) Tidak swap Step 21 [1, 2, 3, 5, 2, 6, 7, 9] ^ ^ (bandingkan) Tidak swap Step 22 [1, 2, 3, 5, 2, 6, 7, 9] ^ ^ (bandingkan) Swap > [1, 2, 3, 2, 5, 6, 7, 9] Hasil akhir: [1, 2, 3, 2, 5, 6, 7, 9] Step 23 [1, 2, 3, 2, 5, 6, 7, 9] ^ ^ (bandingkan) Tidak swap Step 24 [1, 2, 3, 2, 5, 6, 7, 9] ^ ^ (bandingkan) Tidak swap Step 25 [1, 2, 3, 2, 5, 6, 7, 9] ^ ^ (bandingkan) Swap > [1, 2, 2, 3, 5, 6, 7, 9] Hasil akhir: [1, 2, 2, 3, 5, 6, 7, 9] Step 26 [1, 2, 2, 3, 5, 6, 7, 9] ^ ^ (bandingkan) Tidak swap Step 27 [1, 2, 2, 3, 5, 6, 7, 9] ^ ^ (bandingkan) Tidak swap Hasil akhir: [1, 2, 2, 3, 5, 6, 7, 9] Step 28 [1, 2, 2, 3, 5, 6, 7, 9] ^ ^ (bandingkan) Tidak swap Hasil akhir: [1, 2, 2, 3, 5, 6, 7, 9] Hasil akhir: [1, 2, 2, 3, 5, 6, 7, 9]

Komentar

Posting Komentar

Postingan populer dari blog ini

Matriks dan NumPy dalam Python

 Kali ini kita akan membuat program dengan matriks dan NumPy. Sebelumya kita telah membuat sebuah program dengan matriks, matriks juga tegabung dalam array 2 dimensi dan array 3 dimensi. Kita telah membuat sebuah program array 2 dimensi sebelumnya dan sekarang kita akan membuat array 3 dimensi. Sebelum itu kita harus mengenal NumPy. Apa itu NumPy? NumPy adalah singkatan dari Numerical Python, dan merupakan package atau pustaka fundamental yang digunakan untuk komputasi ilmiah di Python. NumPy adalah inti dari hampir semua pustaka analisis data di Python (seperti Pandas, SciPy, dan Scikit-learn) karena menyediakan struktur data yang sangat cepat dan efisien. Definisi dan Kegunaan Matriks dalam Python: Matriks adalah sekumpulan informasi yang setiap individu elemennya terdefinisi dua buah indeks (baris dan kolom). Matriks juga dapat diakses secara langsung jika baris dan kolom diketahui. Matriks berupa homogen yang berarti panjang setiap baris harus sama dengan panjangnya kolom misa...
Baca selengkapnya

Mengenal Abu Ja'far Muhammad Ibnu Musa Al-Khwarizmi

Gambar
Abu Ja'far Muhammad Ibnu Musa Al-Khwarizmi Adalah sebuah muslim   ahli dalam berbagai bidang seperti matematika, astronomi, astrologi, dan geografi yang berasal dari Kufah, Irak. Lahir sekitar tahun 780 masehi di Khwarezmia (sekarang Khiva, Uzbekistan) dan wafat sekitar tahun 850 di Bagdad. Hampir sepanjang hidupnya, ia bekerja sebagai guru di Sekolah Kehormatan di Bagdad yang didirikan oleh Khalifah Bani Abbasiyah Ma'mun Ar-Rasyid, tempat ia belajar ilmu alam dan matematik, termasuk mempelajari terjemahan naskah Sanskerta dan Yunani. Wikipedia.com Penemu Angka Nol dan Bapak Aljabar Dunia Selain menjadi seorang ahli Matematika, Al-Khawarizmi juga ahli dalam bidang ilmu, seperti astronomi, musik, filsafat, geografi, dan kimia. Sejak kecil, Khawarizmi tinggal di Selatan kota Baghdad. Di Baghdad ia menjadi anggota di Bayt Al-Hikmah, yaitu lembaga penerjemah, pusat penelitian ilmu pengetahuan, dan perpustakaan besar yang didirikan oleh Harun Al-Rasyid. Sepanjang hidupnya, Al-Khawar...
Baca selengkapnya