Analyze and Compare Several Searching (Optimization) Algorithms

Dalam dunia pemrograman, searching algorithm merupakan teknik penting yang digunakan untuk menemukan data tertentu di dalam kumpulan data. Ada beberapa metode searching algorithm yang dapat digunakan seperti Linear Search, Binary Search, Jump Search dan Interpolation Search.

Pada artikel ini, akan dijelaskan dan dibandingkan secara singkat perbandingan dari penggunaan keempat metode tersebut. Tujuan dari analisis ini adalah untuk mengetahui prinsip penggunaan dari masing-masing metode dan mengukur performa serta kompleksitasnya.

Linear Search

Linear search adalah metode pencarian yang memeriksa setiap elemen dalam dataset secara berurutan hingga menemukan data yang dicari. Jika seluruh elemen telah diperiksa dan tidak ditemukan kecocokan, maka data tersebut dianggap tidak ada dalam dataset.

def linear_search_enumerate(arr, target):
    for i, nilai in enumerate(arr):
        if nilai == target:
            return i
    return -1

data = [10, 25, 30, 45, 50]
print(linear_search_enumerate(data, 500))

Binary Search

Binary search adalah algoritma pencarian yang menemukan posisi nilai target dalam array yang sudah diurutkan. Binary search membandingkan nilai target dengan elemen tengah dari array.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1 

Jump Search

Algoritma ini merupakan optimasi dari Linear Search dengan cara melompati beberapa elemen sekaligus untuk mempercepat pencarian. Jump Search memiliki kompleksitas waktu O(√n) dan cocok untuk dataset yang besar dan sudah terurut.

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    while prev < n and arr[min(step, n)-1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    while prev < min(step, n):
        if arr[prev] == target:
            return prev
        prev += 1
    return -1

Interpolation Search

Interpolation search adalah algoritma untuk mencari kunci dalam sebuah array yang telah diurutkan berdasarkan nilai numerik yang diberikan pada kunci (nilai kunci).

def interpolation_search(arr, target):
    low = 0
    high = len(arr)-1
    while low <= high and target >= arr[low] and target <= arr[high]:
        pos = low + ((target-arr[low]) *
                     (high-low) //
                     (arr[high]-arr[low]))
        if arr[pos] == target:
            return pos
        if arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1

Analisis Uji Berdasarkan Ukuran Data Set

Analisis ini membandingkan uji performa keempat metode dengan ukuran data set yang berbeda yaitu data set kecil (1000) dan data set besar(100000) dengan cara mengukur waktu yang dibutuhkan dari masing-masing algoritma untuk mendapatkan hasil pencarian.

import timeit
import pandas as pd

# Dataset
small_data = list(range(1000))
large_data = list(range(100000))

target_small = 999
target_large = 99999

algorithms = {
    "Linear": linear_search,
    "Binary": binary_search,
    "Jump": jump_search,
    "Interpolation": interpolation_search
}

results = []

for name, func in algorithms.items():

    small_time = timeit.timeit(
        lambda: func(small_data, target_small),
        number=1000
    )

    large_time = timeit.timeit(
        lambda: func(large_data, target_large),
        number=1000
    )

    results.append([name, small_time, large_time])

df_result = pd.DataFrame(
    results,
    columns=["Algorithm", "Small Dataset", "Large Dataset"]
)

print(df_result)

Dari hasil implementasi algoritma tersebut didapatkan hasil sebagai berikut:

• Interpolation Search merupakan algoritma tercepat pada kedua ukuran dataset dengan waktu eksekusi hanya sekitar 0.0007 detik.
• Binary Search menjadi algoritma tercepat kedua dan menunjukkan performa yang sangat stabil ketika ukuran data meningkat.
• Jump Search memiliki performa yang lebih baik dibanding Linear Search, namun masih jauh lebih lambat dibanding Binary dan Interpolation Search.
• Linear Search menunjukkan peningkatan waktu eksekusi yang sangat signifikan saat ukuran dataset bertambah, dari 0.038 detik menjadi 6.745 detik.

Visualisasi Hasil Uji

Hasil analisis:

• Pada dataset berukuran kecil, perbedaan performa antar algoritma cenderung tidak terlalu signifikan karena jumlah elemen yang diperiksa masih sedikit. Bahkan Linear Search masih mampu memberikan waktu eksekusi yang kompetitif.
• Ketika ukuran data meningkat, perbedaan performa menjadi lebih terlihat dimana Linear Search mengalami peningkatan waktu eksekusi paling besar karena harus memeriksa elemen satu per satu, Binary Search tetap sangat efisien karena terus membagi ruang pencarian menjadi dua bagian, Jump Search lebih cepat dibanding Linear Search namun masih lebih lambat dari Binary Search dan Interpolation Search menjadi yang tercepat pada data numerik yang terdistribusi merata karena dapat memperkirakan posisi target secara langsung.

Analisis Uji Kompleksitas

Kesimpulan

Binary Search dan Interpolation Search menunjukkan performa terbaik pada dataset besar yang telah terurut, sedangkan Linear Search hanya cocok digunakan pada dataset kecil atau data yang belum terurut karena kompleksitasnya yang meningkat secara linear terhadap ukuran data.