Analisis Kompleksitas Waktu Eksekusi Algoritma Insertion Sort dan Selection Sort pada Berbagai Skenario Distribusi Data

Abstract

The efficiency of sorting algorithms cannot be understood through theoretical analysis alone, as it depends heavily on interpreter execution in modern computing environments. Although Insertion Sort and Selection Sort share the same theoretical complexity of O(n²), their empirical performance diverges significantly due to initial data characteristics and memory allocation mechanisms. This study evaluates the interaction between data distribution and the execution overhead of the CPython interpreter on both algorithms. Experiments were conducted in an isolated Google Colab environment using a high-resolution timer on datasets ranging from [n_min] to [n_max] numerical elements, replicated over 10 independent iterations across three distribution scenarios: random, ascending, and descending. Quantitative analysis shows that the O(n²) label does not apply uniformly in practice. At [n_max], Insertion Sort reached its highest efficiency at 1.24 ms in the ascending case but collapsed drastically to 3,842.60 ms in the descending case. Conversely, Selection Sort showed rigid latency, remaining within 1,950–2,150 ms across all scenarios and gaining no advantage from pre-sorted data. This extreme disparity in the worst case does not stem purely from algorithmic computation but from the heavy overhead of reference counting and Python’s dynamic memory management when Insertion Sort performs massive index shifts (memory writes), whereas Selection Sort minimizes memory mutations. The findings establish a quantitative threshold recommending that fundamental sorting algorithms relying on intensive memory swaps and shifts be avoided in standard Python interpreters for datasets exceeding [n_threshold] elements.