Kompleksitas waktu dan ruang

Kompleksitas Waktu:

• Kasus Terbaik: O(n)
  • Saat array sudah terurut, Insertion Sort hanya melakukan satu kali lintasan untuk memastikan urutannya sudah terurut.
• Kasus Rata-rata dan Terburuk: O(n²)
  • Dalam kasus rata-rata dan terburuk, prosesnya membutuhkan waktu kuadratik karena untuk setiap elemen, kita mungkin perlu membandingkan dan menggeser seluruh bagian yang sudah terurut.

Kompleksitas Ruang:

• O(1)
  • Insertion Sort adalah algoritma "in-place", artinya algoritma ini tidak memerlukan memori tambahan yang sebanding dengan ukuran input.
  • Ruang yang digunakan untuk pengurutan tetap konstan, terlepas dari ukuran input.

Ringkasan:

• Insertion Sort efisien untuk kumpulan data kecil atau array yang hampir terurut.
• Insertion Sort kurang cocok untuk kumpulan data besar karena kompleksitas waktunya kuadratik.
• Kompleksitas ruangnya konstan, sehingga hemat memori untuk ukuran input apa pun.