Contoh Soal Insertion Sort dan Jawabannya: Menguak Rahasia Pengurutan Data

Contoh soal insertion sort dan jawabannya – Pernahkah Anda membayangkan bagaimana komputer menyortir data dengan cepat dan efisien? Algoritma Insertion Sort hadir sebagai solusi yang mudah dipahami dan diterapkan untuk mengurutkan data secara terstruktur. Insertion Sort bekerja dengan cara mengambil setiap elemen data dan menempatkannya di posisi yang benar dalam array yang sudah terurut. Bayangkan seperti menata kartu remi, satu per satu kartu diambil dan diletakkan di posisi yang tepat sesuai urutannya.

Dalam artikel ini, kita akan membahas contoh soal Insertion Sort dan langkah-langkah penyelesaiannya secara detail. Anda akan mempelajari cara kerja algoritma ini, keuntungan dan kerugiannya, serta penerapannya dalam berbagai kasus nyata. Siap untuk menguasai Insertion Sort dan mengurutkan data dengan percaya diri? Mari kita mulai!

Pengertian Insertion Sort

Insertion Sort adalah algoritma pengurutan yang sederhana dan mudah dipahami. Algoritma ini bekerja dengan membagi data menjadi dua bagian: bagian yang sudah terurut dan bagian yang belum terurut. Data dari bagian yang belum terurut kemudian dimasukkan ke dalam bagian yang sudah terurut dengan cara yang tepat sehingga menghasilkan urutan yang benar.

Misalnya, bayangkan kamu sedang menyortir kartu remi. Kamu memegang tumpukan kartu yang belum terurut di tangan kiri dan tumpukan kartu yang sudah terurut di tangan kanan. Kemudian, kamu mengambil satu kartu dari tumpukan kiri dan membandingkannya dengan kartu-kartu di tumpukan kanan. Jika kartu yang kamu ambil lebih kecil dari kartu di tumpukan kanan, kamu akan memasukkan kartu tersebut di depan kartu yang lebih besar. Proses ini berulang hingga semua kartu di tangan kiri dimasukkan ke dalam tumpukan kanan yang sudah terurut.

Perbandingan dengan Algoritma Sorting Lainnya

Tabel berikut menunjukkan perbandingan Insertion Sort dengan algoritma sorting lainnya, seperti Bubble Sort dan Selection Sort.

Cara Kerja Insertion Sort

Insertion Sort merupakan algoritma pengurutan yang sederhana dan mudah dipahami. Prinsip kerjanya adalah dengan mengambil satu per satu elemen dari array yang belum terurut, lalu memasukkannya ke posisi yang tepat di dalam array yang sudah terurut.

Langkah-langkah Insertion Sort

Algoritma Insertion Sort bekerja dengan membagi array menjadi dua bagian: bagian kiri yang sudah terurut dan bagian kanan yang belum terurut. Proses pengurutan dilakukan dengan mengambil elemen pertama dari bagian kanan dan membandingkannya dengan elemen-elemen di bagian kiri, secara bertahap menggeser elemen-elemen yang lebih besar ke kanan sampai menemukan posisi yang tepat untuk elemen tersebut.

Berikut adalah langkah-langkah detail dari algoritma Insertion Sort:

• Mulai dengan elemen kedua dari array (indeks 1), karena elemen pertama dianggap sudah terurut.
• Ambil elemen saat ini dan bandingkan dengan elemen sebelumnya.
• Jika elemen saat ini lebih kecil dari elemen sebelumnya, geser elemen sebelumnya ke kanan.
• Ulangi langkah 3 sampai menemukan posisi yang tepat untuk elemen saat ini, yaitu posisi di mana elemen sebelumnya lebih kecil dari elemen saat ini.
• Masukkan elemen saat ini ke posisi yang tepat.
• Ulangi langkah 2-5 untuk setiap elemen yang tersisa di bagian kanan array.

Ilustrasi Proses Sorting dengan Insertion Sort

Misalkan kita memiliki array berikut: [5, 2, 4, 6, 1, 3]. Mari kita ilustrasikan proses sorting dengan Insertion Sort pada array ini.

Langkah 1: Elemen pertama (5) dianggap sudah terurut. Elemen kedua (2) dibandingkan dengan elemen pertama (5). Karena 2 lebih kecil dari 5, maka 5 digeser ke kanan, dan 2 ditempatkan di posisi pertama. Array sekarang menjadi: [2, 5, 4, 6, 1, 3].

Langkah 2: Elemen ketiga (4) dibandingkan dengan elemen kedua (5). Karena 4 lebih kecil dari 5, maka 5 digeser ke kanan. Kemudian, 4 dibandingkan dengan 2. Karena 4 lebih besar dari 2, maka 4 ditempatkan di posisi ketiga. Array sekarang menjadi: [2, 4, 5, 6, 1, 3].

Langkah 3: Elemen keempat (6) dibandingkan dengan elemen ketiga (5). Karena 6 lebih besar dari 5, maka 6 tetap di posisi keempat. Array sekarang menjadi: [2, 4, 5, 6, 1, 3].

Langkah 4: Elemen kelima (1) dibandingkan dengan elemen keempat (6). Karena 1 lebih kecil dari 6, maka 6 digeser ke kanan. Kemudian, 1 dibandingkan dengan 5. Karena 1 lebih kecil dari 5, maka 5 digeser ke kanan. Kemudian, 1 dibandingkan dengan 4. Karena 1 lebih kecil dari 4, maka 4 digeser ke kanan. Terakhir, 1 dibandingkan dengan 2. Karena 1 lebih kecil dari 2, maka 2 digeser ke kanan, dan 1 ditempatkan di posisi pertama. Array sekarang menjadi: [1, 2, 4, 5, 6, 3].

Langkah 5: Elemen keenam (3) dibandingkan dengan elemen kelima (6). Karena 3 lebih kecil dari 6, maka 6 digeser ke kanan. Kemudian, 3 dibandingkan dengan 5. Karena 3 lebih kecil dari 5, maka 5 digeser ke kanan. Kemudian, 3 dibandingkan dengan 4. Karena 3 lebih kecil dari 4, maka 4 digeser ke kanan. Kemudian, 3 dibandingkan dengan 2. Karena 3 lebih besar dari 2, maka 3 ditempatkan di posisi keempat. Array sekarang menjadi: [1, 2, 3, 4, 5, 6].

Array sekarang sudah terurut secara ascending.

Contoh Kode Program Insertion Sort dalam Bahasa Python

“`python
def insertion_sort(arr):
“””
Fungsi untuk mengurutkan array menggunakan Insertion Sort.

Args:
arr: Array yang akan diurutkan.

Returns:
Array yang sudah terurut.
“””
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i – 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr

# Contoh penggunaan
arr = [5, 2, 4, 6, 1, 3]
sorted_arr = insertion_sort(arr)
print("Array yang sudah terurut:", sorted_arr)
“`

Contoh Soal Insertion Sort

Insertion Sort adalah algoritma pengurutan yang sederhana dan mudah dipahami. Algoritma ini bekerja dengan membagi array menjadi dua bagian: bagian yang sudah terurut dan bagian yang belum terurut. Kemudian, elemen pertama dari bagian yang belum terurut diambil dan dimasukkan ke dalam posisi yang benar di bagian yang sudah terurut. Proses ini diulang hingga semua elemen dalam array terurut.

Contoh Soal

Misalkan kita memiliki array berikut:

[5, 2, 4, 6, 1, 3]

Langkah-langkah untuk mengurutkan array ini menggunakan Insertion Sort adalah sebagai berikut:

Langkah-langkah Penyelesaian

1. Pada iterasi pertama, elemen pertama (5) sudah dianggap terurut. Jadi, bagian yang sudah terurut adalah [5] dan bagian yang belum terurut adalah [2, 4, 6, 1, 3].
2. Pada iterasi kedua, elemen pertama dari bagian yang belum terurut (2) diambil dan dibandingkan dengan elemen di bagian yang sudah terurut (5). Karena 2 lebih kecil dari 5, maka 2 dimasukkan ke posisi pertama di bagian yang sudah terurut. Sekarang bagian yang sudah terurut adalah [2, 5] dan bagian yang belum terurut adalah [4, 6, 1, 3].
3. Pada iterasi ketiga, elemen pertama dari bagian yang belum terurut (4) diambil dan dibandingkan dengan elemen di bagian yang sudah terurut (2, 5). Karena 4 lebih besar dari 2 tetapi lebih kecil dari 5, maka 4 dimasukkan ke posisi kedua di bagian yang sudah terurut. Sekarang bagian yang sudah terurut adalah [2, 4, 5] dan bagian yang belum terurut adalah [6, 1, 3].
4. Pada iterasi keempat, elemen pertama dari bagian yang belum terurut (6) diambil dan dibandingkan dengan elemen di bagian yang sudah terurut (2, 4, 5). Karena 6 lebih besar dari 5, maka 6 dimasukkan ke posisi keempat di bagian yang sudah terurut. Sekarang bagian yang sudah terurut adalah [2, 4, 5, 6] dan bagian yang belum terurut adalah [1, 3].
5. Pada iterasi kelima, elemen pertama dari bagian yang belum terurut (1) diambil dan dibandingkan dengan elemen di bagian yang sudah terurut (2, 4, 5, 6). Karena 1 lebih kecil dari 2, maka 1 dimasukkan ke posisi pertama di bagian yang sudah terurut. Sekarang bagian yang sudah terurut adalah [1, 2, 4, 5, 6] dan bagian yang belum terurut adalah [3].
6. Pada iterasi keenam, elemen pertama dari bagian yang belum terurut (3) diambil dan dibandingkan dengan elemen di bagian yang sudah terurut (1, 2, 4, 5, 6). Karena 3 lebih besar dari 2 tetapi lebih kecil dari 4, maka 3 dimasukkan ke posisi ketiga di bagian yang sudah terurut. Sekarang bagian yang sudah terurut adalah [1, 2, 3, 4, 5, 6] dan bagian yang belum terurut adalah [].

Perubahan Array pada Setiap Iterasi

Keuntungan dan Kerugian Insertion Sort: Contoh Soal Insertion Sort Dan Jawabannya

Insertion Sort adalah algoritma pengurutan sederhana yang bekerja dengan membagi array menjadi dua bagian: bagian terurut dan bagian tidak terurut. Algoritma ini kemudian mengambil satu elemen dari bagian tidak terurut dan memasukkannya ke dalam posisi yang benar di bagian terurut. Proses ini berulang hingga semua elemen di bagian tidak terurut telah dimasukkan ke dalam bagian terurut.

Keuntungan Insertion Sort, Contoh soal insertion sort dan jawabannya

Insertion Sort memiliki beberapa keuntungan, terutama dalam situasi tertentu:

• Sederhana dan mudah dipahami: Algoritma ini sangat mudah dipahami dan diimplementasikan, membuatnya cocok untuk pemula dalam pemrograman.
• Efisien untuk array yang hampir terurut: Jika array hampir terurut, Insertion Sort akan sangat cepat karena hanya sedikit pergeseran yang diperlukan untuk menempatkan elemen dalam posisi yang benar.
• Membutuhkan sedikit ruang tambahan: Insertion Sort hanya membutuhkan ruang tambahan yang konstan, membuatnya cocok untuk kasus-kasus di mana memori terbatas.
• Stabil: Insertion Sort mempertahankan urutan relatif elemen yang memiliki nilai yang sama, yang penting dalam beberapa aplikasi.

Kerugian Insertion Sort

Meskipun memiliki keuntungan, Insertion Sort juga memiliki beberapa kerugian:

• Tidak efisien untuk array besar: Untuk array besar, Insertion Sort menjadi sangat lambat karena waktu eksekusi tumbuh secara kuadrat dengan ukuran array.
• Tidak cocok untuk array yang sangat tidak terurut: Jika array sangat tidak terurut, Insertion Sort akan membutuhkan banyak pergeseran elemen, yang membuatnya tidak efisien.

Tabel Perbandingan

Aplikasi Insertion Sort

Insertion Sort merupakan algoritma pengurutan yang sederhana dan efisien untuk dataset yang relatif kecil. Algoritma ini bekerja dengan membagi dataset menjadi dua bagian: bagian yang sudah terurut dan bagian yang belum terurut. Kemudian, elemen dari bagian yang belum terurut diambil satu per satu dan dimasukkan ke dalam posisi yang tepat di bagian yang sudah terurut.

Contoh Kasus Nyata

Salah satu contoh kasus nyata di mana Insertion Sort dapat diterapkan adalah dalam pengurutan kartu bermain. Bayangkan kamu memiliki setumpuk kartu yang belum terurut, dan kamu ingin mengurutkannya berdasarkan nilai kartu.

Contoh soal Insertion Sort dan jawabannya bisa membantu kamu memahami cara kerja algoritma ini dalam mengurutkan data. Mirip seperti menyusun kartu remi, algoritma ini mengambil satu data dan menempatkannya di posisi yang tepat dalam urutan yang sudah ada. Nah, kalau kamu mau latihan mengurutkan kata-kata, coba deh cari contoh soal kalimat acak di situs ini.

Setelah itu, kamu bisa kembali ke contoh soal Insertion Sort dan jawabannya untuk melatih kemampuanmu mengurutkan data secara sistematis.

Kamu dapat menggunakan Insertion Sort dengan mengambil satu kartu dari tumpukan yang belum terurut dan membandingkannya dengan kartu yang sudah terurut. Jika kartu yang diambil lebih kecil dari kartu yang sudah terurut, maka kartu yang diambil dimasukkan sebelum kartu tersebut. Proses ini diulang sampai semua kartu diurutkan.

Alasan Penggunaan Insertion Sort

Insertion Sort cocok digunakan dalam kasus ini karena:

• Sederhana: Algoritma Insertion Sort mudah dipahami dan diimplementasikan.
• Efisien untuk dataset kecil: Insertion Sort bekerja dengan baik untuk dataset yang relatif kecil karena memiliki kompleksitas waktu O(n^2) dalam kasus terburuk, tetapi O(n) dalam kasus terbaik.
• Stabil: Insertion Sort adalah algoritma yang stabil, artinya urutan elemen yang memiliki nilai yang sama akan dipertahankan setelah pengurutan.

Alternatif Algoritma Pengurutan

Ada beberapa alternatif algoritma pengurutan yang dapat digunakan dalam kasus ini, termasuk:

• Bubble Sort: Algoritma ini membandingkan elemen yang berdekatan dan menukarnya jika tidak dalam urutan yang benar. Bubble Sort memiliki kompleksitas waktu O(n^2) dalam kasus terburuk, tetapi O(n) dalam kasus terbaik.
• Selection Sort: Algoritma ini menemukan elemen terkecil dalam dataset dan menukarnya dengan elemen pertama. Proses ini diulang untuk elemen kedua, ketiga, dan seterusnya. Selection Sort memiliki kompleksitas waktu O(n^2) dalam semua kasus.
• Merge Sort: Algoritma ini membagi dataset menjadi dua bagian, mengurutkan kedua bagian secara terpisah, dan kemudian menggabungkan kedua bagian yang sudah terurut menjadi satu dataset yang terurut. Merge Sort memiliki kompleksitas waktu O(n log n) dalam semua kasus.
• Quick Sort: Algoritma ini memilih elemen pivot dan membagi dataset menjadi dua bagian: elemen yang lebih kecil dari pivot dan elemen yang lebih besar dari pivot. Proses ini diulang untuk kedua bagian hingga semua elemen terurut. Quick Sort memiliki kompleksitas waktu O(n log n) dalam kasus rata-rata, tetapi O(n^2) dalam kasus terburuk.

Perbandingan dengan Insertion Sort

Berikut adalah perbandingan Insertion Sort dengan alternatif algoritma pengurutan:

Implementasi Insertion Sort dalam Bahasa Pemrograman

Setelah memahami konsep dan cara kerja Insertion Sort, langkah selanjutnya adalah mengimplementasikan algoritma tersebut dalam bahasa pemrograman. Implementasi Insertion Sort dalam berbagai bahasa pemrograman memiliki kemiripan dalam struktur dan logika, tetapi terdapat perbedaan sintaks dan detail implementasi yang perlu diperhatikan. Berikut adalah contoh implementasi Insertion Sort dalam beberapa bahasa pemrograman populer.

Implementasi Insertion Sort dalam Bahasa Pemrograman Java

Contoh kode program Insertion Sort dalam bahasa pemrograman Java memberikan gambaran tentang bagaimana algoritma ini diterapkan dalam konteks pemrograman berorientasi objek. Kode ini menunjukkan langkah-langkah iterasi, perbandingan, dan penempatan elemen dalam urutan yang benar. Dengan menggunakan Java, Anda dapat memanfaatkan berbagai fitur bahasa seperti array, loop, dan operator perbandingan untuk mengimplementasikan Insertion Sort dengan efisien.

public class InsertionSort 
  public static void insertionSort(int[] arr) 
    int n = arr.length;
    for (int i = 1; i = 0 && arr[j] > key) 
        arr[j + 1] = arr[j];
        j = j - 1;
      
      arr[j + 1] = key;
    
  

  public static void main(String[] args) 
    int[] data = 12, 11, 13, 5, 6;
    insertionSort(data);
    System.out.println("Array yang telah diurutkan:");
    for (int i = 0; i < data.length; ++i) 
      System.out.print(data[i] + " ");
    
  

Implementasi Insertion Sort dalam Bahasa Pemrograman C++

Implementasi Insertion Sort dalam bahasa pemrograman C++ menunjukkan fleksibilitas algoritma ini dalam konteks pemrograman sistem dan aplikasi yang membutuhkan performa tinggi. Kode ini menunjukkan penggunaan loop, array, dan operator perbandingan dalam C++ untuk mengimplementasikan Insertion Sort. Dengan C++, Anda dapat mengoptimalkan kode untuk mencapai efisiensi yang lebih tinggi.

#include 

using namespace std;

void insertionSort(int arr[], int n) 
  int i, key, j;
  for (i = 1; i = 0 && arr[j] > key) 
      arr[j + 1] = arr[j];
      j = j - 1;
    
    arr[j + 1] = key;
  


int main() 
  int data[] = 12, 11, 13, 5, 6;
  int n = sizeof(data) / sizeof(data[0]);
  insertionSort(data, n);
  cout << "Array yang telah diurutkan: \n";
  for (int i = 0; i < n; i++) 
    cout << data[i] << " ";
  
  cout << endl;
  return 0;

Implementasi Insertion Sort dalam Bahasa Pemrograman JavaScript

Implementasi Insertion Sort dalam bahasa pemrograman JavaScript menunjukkan penerapan algoritma ini dalam konteks pengembangan web dan aplikasi berbasis browser. Kode ini menunjukkan penggunaan array, loop, dan operator perbandingan dalam JavaScript untuk mengimplementasikan Insertion Sort. JavaScript memungkinkan Anda untuk mengimplementasikan Insertion Sort dalam berbagai skenario, seperti pengurutan data yang dinamis dalam aplikasi web.

function insertionSort(arr) 
  let n = arr.length;
  for (let i = 1; i = 0 && arr[j] > key) 
      arr[j + 1] = arr[j];
      j = j - 1;
    
    arr[j + 1] = key;
  
  return arr;


let data = [12, 11, 13, 5, 6];
let sortedData = insertionSort(data);
console.log("Array yang telah diurutkan:", sortedData);

Analisa Kompleksitas Insertion Sort

Insertion Sort adalah algoritma pengurutan yang sederhana dan mudah dipahami. Cara kerjanya mirip dengan cara kita mengurutkan kartu remi: kita mengambil satu kartu dan menempatkannya pada posisi yang benar dalam tumpukan kartu yang sudah terurut. Dalam Insertion Sort, elemen-elemen dalam array diurutkan satu per satu. Setiap elemen diambil dan ditempatkan pada posisi yang tepat dalam sub-array yang sudah terurut.

Kompleksitas Waktu Insertion Sort

Kompleksitas waktu Insertion Sort berbeda-beda tergantung pada skenario kasusnya. Berikut adalah analisa kompleksitas waktu Insertion Sort untuk berbagai skenario kasus:

• Best Case: Ketika array sudah terurut, Insertion Sort hanya perlu melakukan perbandingan pada setiap elemen, tanpa perlu melakukan pertukaran. Dalam skenario ini, kompleksitas waktu Insertion Sort adalah O(n).
• Average Case: Dalam skenario rata-rata, Insertion Sort akan membutuhkan waktu yang lebih lama dibandingkan dengan best case. Dalam skenario ini, kompleksitas waktu Insertion Sort adalah O(n^2).
• Worst Case: Ketika array terurut terbalik, Insertion Sort akan membutuhkan waktu yang paling lama. Dalam skenario ini, Insertion Sort akan melakukan perbandingan dan pertukaran pada setiap elemen, sehingga kompleksitas waktunya adalah O(n^2).

Kompleksitas Ruang Insertion Sort

Insertion Sort adalah algoritma pengurutan *in-place*, artinya algoritma ini tidak membutuhkan ruang tambahan yang signifikan untuk menyimpan data sementara. Kompleksitas ruang Insertion Sort adalah O(1), karena hanya membutuhkan ruang tambahan yang konstan untuk menyimpan variabel sementara.

Grafik Kompleksitas Waktu Insertion Sort

Grafik berikut menggambarkan kompleksitas waktu Insertion Sort terhadap ukuran input:

[Grafik yang menunjukkan kompleksitas waktu Insertion Sort terhadap ukuran input. Grafik ini akan memiliki sumbu X yang mewakili ukuran input (n) dan sumbu Y yang mewakili waktu yang dibutuhkan (T(n)). Grafik akan menunjukkan bahwa kompleksitas waktu Insertion Sort adalah O(n) untuk best case, O(n^2) untuk average case, dan O(n^2) untuk worst case. ]

Variasi Insertion Sort

Insertion Sort adalah algoritma pengurutan sederhana yang bekerja dengan cara membangun urutan terurut satu per satu. Algoritma ini membagi array menjadi dua bagian: bagian terurut dan bagian yang belum terurut. Elemen pertama dari bagian yang belum terurut kemudian dimasukkan ke dalam bagian terurut pada posisi yang tepat sehingga bagian terurut tetap terurut. Proses ini diulang untuk setiap elemen di bagian yang belum terurut hingga semua elemen berada dalam bagian terurut.

Insertion Sort dengan Binary Search

Salah satu variasi Insertion Sort adalah dengan menggunakan binary search untuk menemukan posisi yang tepat untuk memasukkan elemen ke dalam bagian terurut. Binary search memungkinkan pencarian posisi yang tepat lebih efisien dibandingkan dengan pencarian linier yang dilakukan pada Insertion Sort biasa.

Berikut adalah langkah-langkah Insertion Sort dengan binary search:

• Bagilah array menjadi bagian terurut dan bagian yang belum terurut.
• Untuk setiap elemen di bagian yang belum terurut, lakukan binary search pada bagian terurut untuk menemukan posisi yang tepat untuk memasukkan elemen tersebut.
• Geser elemen-elemen dalam bagian terurut yang berada di sebelah kanan posisi yang ditemukan satu posisi ke kanan.
• Masukkan elemen yang sedang diproses ke dalam posisi yang ditemukan.

Perbandingan Kinerja Insertion Sort dan Variasinya

Insertion Sort dengan binary search umumnya memiliki kinerja yang lebih baik dibandingkan dengan Insertion Sort biasa, terutama untuk array yang besar. Hal ini karena binary search memungkinkan pencarian posisi yang tepat dengan lebih efisien dibandingkan dengan pencarian linier. Namun, untuk array yang kecil, Insertion Sort biasa mungkin lebih efisien karena overhead binary search mungkin tidak sepadan dengan keuntungannya.

Tabel Perbedaan Insertion Sort dan Variasinya

Berikut adalah tabel yang menunjukkan perbedaan antara Insertion Sort dengan variasi-variasinya:

Praktik Penerapan Insertion Sort

Insertion Sort adalah algoritma pengurutan sederhana yang bekerja dengan memasukkan setiap elemen ke posisi yang benar dalam subarray yang sudah terurut. Algoritma ini efektif untuk dataset kecil dan data yang hampir terurut.

Contoh Kasus Sederhana

Misalnya, kita ingin mengurutkan daftar nama teman: [“Rina”, “Doni”, “Ayu”, “Candra”]. Insertion Sort akan bekerja dengan mengambil setiap nama secara bergantian dan memasukkannya ke posisi yang benar dalam subarray yang sudah terurut.

Kode Program Insertion Sort

Berikut kode program Insertion Sort dalam bahasa Python untuk mengurutkan daftar nama teman:

def insertion_sort(arr):
  n = len(arr)
  for i in range(1, n):
    key = arr[i]
    j = i - 1
    while j >= 0 and key < arr[j]:
      arr[j + 1] = arr[j]
      j -= 1
    arr[j + 1] = key
  return arr

teman = ["Rina", "Doni", "Ayu", "Candra"]
teman_terurut = insertion_sort(teman)
print("Daftar teman terurut:", teman_terurut)

Output dan Analisis

Kode program di atas akan menghasilkan output berikut:

Daftar teman terurut: ['Ayu', 'Candra', 'Doni', 'Rina']

Output menunjukkan bahwa daftar nama teman berhasil diurutkan secara alfabetis menggunakan Insertion Sort. Algoritma bekerja dengan mengambil setiap nama secara bergantian dan memasukkannya ke posisi yang benar dalam subarray yang sudah terurut.

Evaluasi dan Kesimpulan

Insertion Sort adalah algoritma sorting yang sederhana dan mudah dipahami. Algoritma ini cocok untuk dataset kecil atau dataset yang hampir terurut. Namun, Insertion Sort memiliki kinerja yang buruk untuk dataset yang besar dan tidak terurut.

Efisiensi Insertion Sort

Insertion Sort dapat diimplementasikan dengan lebih efisien dengan menggunakan beberapa teknik:

• Penggunaan Binary Search: Untuk menemukan posisi yang tepat untuk memasukkan elemen, kita dapat menggunakan Binary Search. Hal ini dapat meningkatkan kinerja algoritma, terutama untuk dataset yang besar.
• Optimasi untuk Dataset yang Hampir Terurut: Jika dataset hampir terurut, Insertion Sort dapat diimplementasikan dengan sangat efisien. Kita dapat memulai dengan memeriksa elemen pertama dan kedua, dan jika sudah terurut, kita dapat melanjutkan dengan memeriksa elemen berikutnya.

Memilih Algoritma Sorting yang Tepat

Memilih algoritma sorting yang tepat tergantung pada kebutuhan dan karakteristik data. Berikut beberapa faktor yang perlu dipertimbangkan:

• Ukuran Dataset: Untuk dataset yang kecil, Insertion Sort dapat menjadi pilihan yang baik. Namun, untuk dataset yang besar, algoritma sorting yang lebih efisien seperti Merge Sort atau Quick Sort lebih cocok.
• Tingkat Ketidakurutan: Jika dataset hampir terurut, Insertion Sort dapat menjadi pilihan yang baik. Namun, jika dataset sangat tidak terurut, algoritma sorting yang lebih efisien seperti Merge Sort atau Quick Sort lebih cocok.
• Kebutuhan Stabilitas: Beberapa algoritma sorting seperti Insertion Sort adalah algoritma sorting yang stabil, artinya elemen yang sama akan tetap mempertahankan urutan relatifnya setelah sorting. Jika stabilitas diperlukan, Insertion Sort dapat menjadi pilihan yang baik.
• Kebutuhan Memori: Insertion Sort adalah algoritma sorting in-place, artinya tidak memerlukan memori tambahan untuk menyimpan data. Jika kebutuhan memori menjadi perhatian, Insertion Sort dapat menjadi pilihan yang baik.

Ulasan Penutup

Dengan memahami Insertion Sort, Anda telah membuka pintu menuju dunia algoritma pengurutan yang lebih luas. Meskipun memiliki kelemahan, Insertion Sort tetap menjadi pilihan yang efektif untuk data yang relatif kecil atau sudah hampir terurut. Kemampuannya untuk mengurutkan secara bertahap membuatnya mudah dipahami dan diterapkan, menjadikannya algoritma yang ideal untuk pembelajaran awal di bidang algoritma sorting.