PERBANDINGAN EFISIENSI MEMORI DAN WAKTU KOMPUTASI ALGORITMA PENGURUTAN REKURSIF DAN ITERATIF DI PYTHON (MERGE SORT DAN QUICK SORT)

Abstract

This study aims to analyze and compare the computational time efficiency and memory usage of the recursive and iterative approaches in the Merge Sort and Quick Sort algorithms in Python. The method used is an experimental quantitative approach with performance testing on two data sizes, namely 10,000 and 1,000,000 random number elements. Execution time is measured using the time and timeit libraries, while memory usage is monitored using the psutil library. The results show that, in general, the iterative approach is more efficient in memory usage because it does not require a function call stack as in recursion. In terms of execution speed, recursive Quick Sort provides the fastest average time of 0.002 seconds on data of 10,000 elements, while on data of 1,000,000 elements, iterative Quick Sort shows better time performance than the recursive version. Iterative Merge Sort is consistently more memory efficient than recursive Merge Sort on both data sizes. The time difference between the recursive and iterative approaches is relatively small for medium-sized data, but memory consumption increases significantly with the recursive version as the data size increases. These findings indicate that the choice of implementation approach for sorting algorithms in Python requires considering the trade-off between speed and memory efficiency. The iterative approach is more suitable for applications with limited memory resources, while the recursive approach remains relevant for scenarios that prioritize simplicity of implementation and clarity of algorithm structure. The results of this study are expected to serve as a reference for software developers and algorithm researchers in determining optimal sorting implementation strategies in Python.

Penelitian ini bertujuan menganalisis dan membandingkan efisiensi waktu komputasi dan penggunaan memori antara pendekatan rekursif dan iteratif pada algoritma pengurutan Merge Sort dan Quick Sort menggunakan bahasa pemrograman Python. Metode yang digunakan adalah pendekatan kuantitatif eksperimental dengan pengujian kinerja pada dua ukuran data, yaitu 10.000 dan 1.000.000 elemen bilangan acak. Waktu eksekusi diukur menggunakan pustaka time dan timeit, sedangkan penggunaan memori dipantau dengan pustaka psutil. Hasil penelitian menunjukkan bahwa secara umum pendekatan iteratif lebih efisien dalam penggunaan memori karena tidak memerlukan tumpukan pemanggilan fungsi (call stack) sebagaimana pada rekursi. Dari sisi kecepatan eksekusi, Quick Sort rekursif memberikan waktu rata-rata tercepat sebesar 0,002 detik pada data 10.000 elemen, sedangkan pada data 1.000.000 elemen Quick Sort iteratif menunjukkan kinerja waktu yang lebih baik dibandingkan versi rekursif. Merge Sort iteratif konsisten lebih hemat memori dibandingkan Merge Sort rekursif pada kedua ukuran data. Perbedaan waktu antara pendekatan rekursif dan iteratif relatif kecil pada data berukuran menengah, namun konsumsi memori meningkat secara nyata pada versi rekursif seiring bertambahnya ukuran data. Temuan ini mengindikasikan bahwa pemilihan pendekatan implementasi algoritma pengurutan di Python perlu mempertimbangkan trade-off antara kecepatan dan efisiensi memori. Pendekatan iteratif lebih sesuai untuk aplikasi dengan keterbatasan sumber daya memori, sedangkan pendekatan rekursif tetap relevan untuk skenario yang mengutamakan kesederhanaan implementasi dan kejelasan struktur algoritma. Hasil penelitian ini diharapkan dapat menjadi rujukan bagi pengembang perangkat lunak dan peneliti algoritma dalam menentukan strategi implementasi pengurutan yang optimal pada Python