ANALISIS PERBANDINGAN EFISIENSI ALGORITMA INTROSORT DENGAN ALGORITMA TRADISIONAL BUBBLE SORT DAN SELECTION SORT

Abstract

Data sorting is a fundamental operation that significantly impacts the performance of various computing applications. In C++, developers can choose from traditional sorting algorithms, such as Bubble sort and Selection sort, as well as modern algorithms, such as Introsort. This study aims to analyze and compare the efficiency of the Introsort, Bubble sort, and Selection sort algorithms in terms of execution time and memory usage. The method used is a comparative experiment with three random data sizes: 100, 1,000, and 10,000 elements. Each scenario is tested three times using a recursive C++ implementation on a Lenovo Ideapad 1i laptop with an Intel Celeron N4020 processor, 8 GB of RAM, and a 477 GB SSD. Execution time is measured using the std::chrono library, while memory usage is measured using the getMemoryUsage() function. The results show that Introsort is consistently the fastest algorithm for all data sizes. At 10,000 elements, the average execution time of Introsort is about 2.88 ms, while Bubble sort and Selection sort are about 1,303 ms and 1,067 ms, respectively. Thus, Introsort is about 450 times faster than Bubble sort and 370 times faster than Selection sort on large datasets, while the difference in memory usage among the three algorithms is under 0.15 MB. These findings indicate that choosing a modern algorithm like Introsort is highly recommended for sorting large data sets in C++. In contrast, traditional algorithms are more appropriate for learning scenarios or small datasets.

Pengurutan data merupakan operasi dasar yang sangat memengaruhi kinerja berbagai aplikasi komputasi. Pada bahasa pemrograman C++, pengembang dapat memilih algoritma pengurutan tradisional seperti Bubble sort dan Selection sort, maupun algoritma modern seperti Introsort. Penelitian ini bertujuan menganalisis dan membandingkan efisiensi algoritma Introsort, Bubble sort, dan Selection sort berdasarkan waktu eksekusi dan penggunaan memori. Metode yang digunakan adalah eksperimen komparatif dengan tiga skala ukuran data acak, yaitu 100, 1.000, dan 10.000 elemen. Setiap skenario diuji sebanyak tiga kali menggunakan implementasi rekursif C++ pada laptop Lenovo Ideapad 1i dengan prosesor Intel Celeron N4020, RAM 8 GB, dan SSD 477 GB. Waktu eksekusi diukur menggunakan pustaka std::chrono, sedangkan penggunaan memori diukur dengan fungsi getMemoryUsage(). Hasil menunjukkan bahwa Introsort secara konsisten menjadi algoritma paling cepat untuk seluruh ukuran data. Pada 10.000 elemen, rata-rata waktu eksekusi Introsort sekitar 2,88 ms, sedangkan Bubble sort dan Selection sort masing-masing sekitar 1.303 ms dan 1.067 ms. Dengan demikian, Introsort sekitar 450 kali lebih cepat daripada Bubble sort dan 370 kali lebih cepat daripada Selection sort pada skala data besar, sementara perbedaan penggunaan memori di antara ketiga algoritma berada di bawah 0,15 MB. Temuan ini mengindikasikan bahwa pemilihan algoritma modern seperti Introsort sangat disarankan untuk pengurutan data berukuran besar di C++, sedangkan algoritma tradisional lebih tepat digunakan untuk skenario pembelajaran atau dataset kecil