APLIKASI PERMAINAN SUSUN KATA UNTUK PEMBELAJARAN BAHASA INGGRIS DENGAN ALGORITMA KNUTH–MORRIS–PRATT DAN FISHER-YATES SHUFFLE

Abstrak - Proses pembelajaran bahasa Inggris tentu perlu mempelajari tentang tata bahasa Inggris ( grammar ). Dengan definisi, rumus, dan contohnya yang cukup rumit, aplikasi komputer interaktif ( game ) yang memuat konten edukasi bahasa Inggris ini hadir sebagai hiburan yang mendidik. Penggunaan game susun kata sebagai sarana edukasi dikarenakan sifatnya yang interaktif sekaligus menghibur. Pemain diminta aktif untuk merangkai kata menjadi kalimat yang sesuai dengan tata bahasa tertentu. Permainan dibangun dengan mengimplementasikan metode Knuth–Morris–Pratt pada proses koreksi susunan kata dan metode Fisher–Yates shuffle pada proses membangkitkan permutasi susunan soal . Hasil uji coba metode Knuth–Morris–Pratt didapatkan hasil akurasi sebesar 100% dengan konsumsi waktu rata-rata adalah  detik menunjukkan proses koreksi susunan kata pada permainan berjalan efektif dari segi akurasi dan konsumsi waktu. Hasil uji coba metode Fisher–Yates shuffle didapatkan frekuensi permutasi dengan nilai rata-rata range sebesar 1,61% menunjukkan permutasi acak dari suatu himpunan terhingga terdistribusi secara hampir merata sehingga susunan soal yang ditampilkan permainan seimbang dan lebih bervariasi.