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

Abstract

Understanding the efficiency of sorting algorithms cannot be reduced merely to theoretical analysis; rather, it depends heavily on interpreter execution within modern computing environments. Although Insertion Sort and Selection Sort share the same theoretical complexity of , their empirical performance exhibits significant divergence due to initial data characteristics and memory allocation mechanisms. This research evaluates the interaction between data structure distributions and the CPython interpreter's execution overhead on both algorithms. The experiments were conducted in an isolated Google Colab environment using a high-resolution timing instrument on dataset sizes ranging from  up to numerical elements. The tests were replicated through 10 independent iterations across three distribution scenarios: random, ascending, and descending. Quantitative analysis demonstrates that the O(n^2) label does not apply uniformly in the empirical realm. At , Insertion Sort achieved its highest efficiency at 1.24 ms in the ascending case, yet suffered a drastic performance collapse, reaching 3,842.60 ms in the descending case. Conversely, Selection Sort exhibited a rigid latency resistance, remaining constant in the range of 1,950–2,150 ms across all scenarios, completely unaffected by the advantages of pre-sorted data. This extreme performance disparity in the worst-case scenario is proven to not stem purely from algorithmic computation, but rather from the severe overhead of reference counting and Python's dynamic memory management when Insertion Sort executes massive index shifts (memory writes), as opposed to Selection Sort which minimizes memory mutations.