Jumlah Perulangan dalam Insertion Sort

Python
#1 
def insertionsort(S):
  n = len(S)
  for i in range(1, n):
    print(S)
    x = S[i]  
    j = i - 1
    while j >= 0 and S[j] > x:
      S[j + 1] = S[j]
      j -= 1
    S[j + 1] = x

Fungsi insertion sort di atas memiliki dua loop, yaitu sebuah for loop dan sebuah while loop yang nested di dalamnya. Asumsi saya ketika kita ingin menyortir array [5, 3, 4, 1, 2] maka berikut langkah yang terjadi setiap perulangan:

  1. [(kiri > x)?] (x saat ini) → [keputusan] (x saat ini)

  2. [5, 3, 4, 1, 2] (3) → [3, 5, 4, 1, 2] (3)

  3. [3, 5, 4, 1, 2] (4) → [3, 4, 5, 1, 2] (4)

  4. [3, 4, 5, 1, 2] (1) → [3, 4, 5, 5, 2] (1)

  5. [3, 4, 5, 5, 2](1) → [3, 4, 4, 5, 2] (1)

  6. [3, 4, 4, 5, 2] (1) → [3, 3, 4, 5, 2] (1) → [1, 3, 4, 5, 2] (1)

  7. [1, 3, 4, 5, 2] (2) → [1,3, 4, 5, 5] (2)

  8. [1, 3, 4, 5, 5] (2) → [1,3, 4, 4, 5] (2)

  9. [1, 3, 4, 4, 5] (2) → [1, 3, 3, 4, 5] (2) → [1, 2, 3, 4, 5] (2)

sehingga ada 8 iterasi.

Versi ChatGPT (yang aku juga setuju):

  1. Iterasi 1: Membandingkan 30 dengan 50 (1 perulangan)
  • [30, 50, 40, 10, 20]
  1. Iterasi 2: Membandingkan 40 dengan 50 dan 30 (2 perulangan)
  • [30, 40, 50, 10, 20]
  1. Iterasi 3: Membandingkan 10 dengan 50, 40, dan 30 (3 perulangan)
  • [10, 30, 40, 50, 20]
  1. Iterasi 4: Membandingkan 20 dengan 50, 40, 30, dan 10 (4 perulangan)
  • [10, 20, 30, 40, 50]
    Jadi, total perulangan yang terjadi saat menyortir list tersebut menggunakan insertion sort adalah 1 + 2 + 3 + 4 = 10 perulangan.

Namun, sepertinya SkilVul hanya mempertimbangkan perulangan luar (for loop) saja, di mana kalau begitu kasusnya, maka jumlah perulangan selalu sama dengan n-1 (n adalah jumlah elemen list). Ini buktinya:

image
image709×440 19 KB

Mohon bantuannya.

Terima kasih sebelumnya.