1738
Received June1 st ,2012; Revised June25 th , 2012; Accepted July 10 th , 2012

## Kombinasi Fisher Yates Shuffle dan Bubble Sort Pada Aplikasi Ujian Berbasis Web
Alen Prastya 1 , Fauziah, Ratih Titi Komala Sari 3 1, 2, 3 Program Studi Informatika Fakultas Teknologi Komunikasi dan Informatika Fakultas Teknologi Komunikasi dan Informatika Universitas Nasional, Jakarta e-mail: 1 alenprastya@gmail.com, 2 fauziah@civitas.unas.ac.id, 3 ratih.titi@civitas.unas.ac.id

## Abstrak
Abstrak  –  Masa  pandemi  sekarang  ini  institusi  pendidikan  yang  menerapkan  sistem pembelejaran secara online. Proses ujian juga sudah menggunakan sistem online, sehingga pada saat  ujian  pengawasan  tidak  bisa  dilakukan  secara  langsung.  Penelitian  ini  menerapkan algoritma Fisher Yates Shuffle (FYS) untuk pengacakan soal pada aplikasi ujian berbasis web dengan  tujuan  meminimalisir  terjadinya  kerjasama  antar  sisiwa.  Sedangkan  Bubble  Sort digunakan untuk mengurutkan soal secara descendning dengan tujuan memperoleh soal terbaru dari database.bentuk pengujian adalah mengukur waktu yang digunakan oleh kedua algoritma untuk melakukan proses pengacakan (FYS) dan pengurutan (Bubble Sort). Kecepatan data-rata dari pengacakan data dengan urutan 100, 200, 300,400, 500 soal adalah 343 ms, dan kecepatan rata-rata algoritma bubble sort dengan data yang sebanding adalah 433 ms.

## Kata kunci: fisher-yates shuffle, PHP, Bubble Sort

## Abstract
Abstract – During the current pandemic, educational institutions are implementing an online learning system. The exam process also uses an online system, so that during the exam supervision it cannot be done directly. This study applies the Fisher-Yates Shuffle (FYS) algorithm for the randomization of questions in a web-based exam application with the aim of minimizing collaboration  between  students.  While  Bubble  Sort  is  used  to  sort  the  questions  in  descending order  with  the  aim  of  getting  the  latest  questions  from  the  database.  The  form  of  testing  is  to measure  the  time  used  by  the  two  algorithms  to  perform  the  randomization  (FYS)  and  sorting (Bubble Sort) processes. The average data speed of randomizing data in the order of 100, 200, 300,400, 500 questions is 343 ms, and the average speed of the bubble sort algorithm with the same data is 433 ms.
Keywords i: fisher-yates shuffle, PHP, Bubble Sort

## 1. PENDAHULUAN
Pandemi covid-19 , proses belajar mengajar sudah mulai menerapkan sistem berbasis online . Selain untuk mengurangi penularan virus covid- 19 bentuk belajar jarak jauh juga merupakan suatu hal yang mustahil untuk dihindari karena tingkat kemajuan ilmu teknologi yang semakin berkembang, dan banyak sekali keuntungan yang di dapatkan dari pemanfaatan teknologi. Topik penelitian  ini  mengenai  ujian online ,  ujian  dilakukan  masing-masing  pelajar.  Pada  umumnya ujian dikerjakan oleh masih-masing pelajar, namun tidak sedikit yang masih bekerjasama dalam proses ujian. Sistem pengacakan soal sangat diperlukan dalam proses ujian, untuk meminimalisir terjadinya kerjasama antar pelajar. Dengan menggunakan Sistem ujian berbasis online berguna
P
1739
untuk  meningkatkan  kualitas,  pengurangan  penggunaan  kertas  [1].  Selain  menggunakan pengacakan soal, aplikasi  juga dapat mengurutkan soal dari id terbawah, sehingga soal terbaru dapat digunakan untuk ujian jika jumlah soal sudah melebihi ketentuan dalam ujian
Pengacakan  soal  yang  dilakukan  menggunakan  FYS  yang  merupakan  bentuk ubahan urutan soal. Pada algoritma FYS permutasi yang dihasilkan bersama probablitas setara. Dari hasil penelitian dengan menggunakan algortima FYS, tidak melakukan pengcakan soal berganda  [2]. Linier  Congruent  Method (LCM) Merupakan  Suatu  Algortima  yang  digunakan  untuk mengaktifkan  suatu numeric acak  yang  difungsikan  di  Dalam  program  komputer  [3]  LCM berfungsi sama dengan FYS namun memiliki perbedaan pada pola pengacaknnya .Penggunaan Algoritma  YSF  dan  LCM  menghasilkan  posisi  yang  sangat  acak  dari  urutan  soal  sebenarnya, meskipun diakses secara bersamaan algoritma tersebut tetap berjalan  [4]. Kelebihan Algortima FYS adalah tingkat kefektifitasan dan kompleksitas dalam proses pengacakan bilangan dengan menggunakan O(n ) [5].  Peneletian sebelumnya mengenai komparasi algortima FYS dan LCM untuk waktu akses,  hasil yang diperoleh dari perbandingan algortima FYS terbukti lebih cepat dibandingkan  dengan  LCM,  Dalam  pengujiannya  menggunakan  25000  data  algortima  FYS Selisih  lebih  cepat  11,768%  dari  pada  algoritma  LCM  [6].  Peneletian  sebelumnya  mengenai pengacakan  soal  ujian  menggunakan  algoritma  FYS  mendapatkan  hasil  algoritma  FYS  bisa membuat solusi acak tidak berganda secara objektif dan variatif [7]. Algortima FYS tidak cocok digunakan  untuk  ukuran  file  yang  sangat  besar  karena  performa  pengacakan  akan  semakin melambat  [8].  Penelitian  mengenai  pengacakan  soal  menggunakan  algoritma  FYS  memeroleh hasil  87%  dalam  proses  pengacakan  urutan  soal  [9].Pengujian  algoritma  FYS  menggunakan bahasa  pemrograman  PHP  menghasilkan  permutasi  soal  acak  sehingga  pada  tampilan  aplikasi siswa  mempunyai  nomer  terurut  namun  setiap  siswa  memiliki  soal  yang  berbeda  pada  nomor yang sama [10].
Pengurutan soal yang dilakukan secara descending menggunakan algoritma bubble sort , Algoritma bubble sort merupakan komparasi algoritma dengan pola penukaran antar elemen yang saling  berdekatan  bila  mana  elemen  lebih  kecil  dari  pada  elemen  setelahnya,  Pada  penelitian sebelumnya  perolehan  algoritma bubble  sort dengan  parameter  pengujian  kecepatan  dengan menggunakan 1000 data adalah 125 ms[11]. Bubble sort adalah salah satu algoritma pengurutan yang dilakukan secara mengulang proses perbandingan setiap elemen array jika pengurutannya salah,  salah  satu  metode bubble  sort yang  di  implementasikan  pada  penilitian  ini  adalah descending yaitu pengurutan dari nilai yang terbesar ke nilai terkecil   [12]. Bubble sort adalah cara  pengurutan  sederhana,  dan  arti  dari  katanya  sendiri  merupakan  gelembung  air,  dengan pengurutan ascending adalah data[i]>data[i]+1, dan untuk descending adalah data[i]<data[i]+1[13].
Tujuan dari  penelitian  kali  ini  adalah  bentuk  implementasi  algoritma  FYS  dan Bubble Sort untuk  pengolahan  soal  pada  aplikasi  ujian  berbasis  web,  parameter  yang  di  uji  adalah kecepatan  algoritma  FYS  dalam  mengacak  soal,  dan  kecepatan  algoritma bubble  sort dalam mengurutkan soal, jadi dalam aplikasi terdapat pilihan apakah soal akan diurutkan atau diacak, proses pengacakan soal dilakkan dari total element array yang ada dalam file database, sedangkan proses pengurutan soal dilakukan secara descending , seningga jika pembuatan ujian akan diambil dari soal terbaru dengan id soal terbesar.

## 2. METODE PENELITIAN
Dengan menggunakan kombinasi antara algoritma FYS dan bubble sort untuk mengelola soal  ujian  berbasis  web,  Algoritma  FYS  digunakan  untuk  pengacakan  soal  ujian,  sedangkan algoritma bubble sort digunakan untuk pengurutan soal ujian secara descending dengan tujuan untuk mengambil soal terbaru yang dibuat oleh user, dengan parameter id soal diurutkan dari yang terbsar  menuju  ke  yang  terkecil,  berikut  ini  adalah  metode  penlitian  yang  dilakukan  penliti tujukan pada gambar 1.
1740

## 2.1 Algoritma Fisher-yates Shuffle (FYS)
Algoritma  FYS  adalah  salah  satu  dari  sekian  banyak  algoritma  yang  memproses permutasi acak dari satu set terbatas [14]. Algoritma FYS berjalan pada kompleksistas waktu O (n) ) dimana n adalah panjang data tersebut, yang berarti proses pengacakan dimulai dari data paling akhir kemudian elemen tersebut diacak dengan data random , hal tersebut dilakukan sampai pada elemen  pertama,  sehingga  semua  data  dipastikan  teracak  [15]. Penelitian  dilakukan  dengan menggunakan algoritma FYS sebagai pengacakan data soal berupa pilihan ganda yang mengacak nomor  soal  dengan  melakukan  perpindahan  array  data,  bukan  mencoret  data  [16],  dan penerapannya pada aplikasi ujian berbasis web
Langkah-langkah untuk memperoleh permutasi secara acak
Gambar 1. Diagram Metode Penelitian
1741
1. Pembuatan data dari 1 sampai Jumlah data ( JD )
2. Pemilihan data Acak ( A ) dari keseluruhan jumlah data yang belum tercoret
3. Pemindahan data dari urutan terbawah, dan penulisan data yang belum tercoret di tempat lain
4. Melakukan pengulangan data setelah JD – 1 data
5. Pengulangan langkah 2 dan 3 sampai semua data tercatat

## 2. 2 Algoritma Bubble Sort
Algortima  Bubble  sort  adalah  salah  satu  algoritma  pengurutan  yang  dilakukan  secara mengulang proses perbandingan setiap elemen array jika pengurutannya salah, salah satu metode bubble sort yang di implementasikan pada penilitian ini adalah descending yaitu pengurutan dari nilai  yang  terbesar  ke  nilai  terkecil.  Pengururan  soal  yang  dilakukan  secara  descending menggunakan  algoritma  bubble  sort,  Algoritma  bubble  sort  merupakan  komparasi  algoritma dengan pola penukaran antar elemen yang saling berdekatan bila mana elemen lebih kecil dari pada elemen setelahnya

## Gambar 3. Flowchart Algoritma Bubble Sort
Gambar  3.  Flowchart  Algoritma  bubble  sort  dengan  proses  sorting  secara  descendant  yaitu pengurutan  yang  dilakukan  dari  yang  terbesar  atau  kebalikan  dari  ascendant.  Penjelasan  dari flowchart pada Gambar 3. Adalah pengulangan yang ke satu dilakukan dari 0 sampar ke n yaitu banyaknya  elemen  dan  pada pengulangan 2 dilakukan dengan  pengurangan  elemen  yang telah diurutkan dari keseluruhan elemen, berikutnya adalah proses pemilihan data secara descending jika data lebih kecil dari sebelumnya maka pertukaran data akan terjadi, dan proses tersebut terus berulang sampai statement terpenuhi dari total keseluruhan elemen.
1742
Gambar 6. Perbandingan Soal Nomor 20 Pada Aplikasi Ujian

## 3. HASIL DAN PEMBAHASAN
Hasil  dan  pembahasan  yang  dilakukan  oleh  penulis  adalah  pengujian  aplikasi  dan pengujian sistem. Pengujian aplikasi dilakukan dengan metode membandingkan nomor soal pada saat ujian antara 2 user yang berbeda yang melakukan proses ujian pada waktu yang bersamaan.

## 3.1 Pengujian Algoritma FYS pada Aplikasi Ujian
Gambar 4. Perbandingan Soal Nomor 1 Pada Aplikasi Ujian
Gambar 5. Perbandingan Soal Nomor 10 Pada Aplikasi ujian

## Gambar 7. Perbandingan Soal Nomor 30 Pada Aplikasi Ujian
Gambar  3,4,5,6  menunjukan hasil  pengujian  pada  aplikasi  ujian  berbasis  website,  proses  yang dilakukan dengan membandingkan nomor soal yang sama pada user yang berbeda saat melakukan ujian  diwaktu  yang  sama,  dari  hasil  pengujian  menunjukan  aplikasi  telah  melakukan  proses pengacakan  soal  pada  saat  proses  ujian  berlangsung,  masing-masing  user  mendapatkan  urutan soal yang berbeda.

## 3.2. Pengujian Algoritma Bubble Sort Pada Aplikasi Ujian
Gambar 8. Pengujian Aplikasi (bubble sort)
Gambar 9   .  Pengujian Aplikasi (bubble sort)

## Gambar 10. Pengujian Aplikasi (bubble sort)
Gambar 8,9,10  Merupakan hasil dari pengurutan soal yang dilakukan menggunakan  algoritma bubble  sort  dengan  melakukan  descending  id  soal  yang  berarti  urutan  yang  dilakukan  adalah pengurutan  dari  soal  terbaru  yang  dibuat  dengan  id  soal  terbesar,  tujuannya  adalah  untuk melakukan  ujian  dengan  soal  yang  paling  baru  dibuat  oleh  user(guru).  Hasilnya  adalah  soal berurutan sesuai dengan id terbesar dari dalam database.

## 3.4 Pengujian Algoritma FYS Pada SIstem
Proses pengujian sistem menggunakan aplikasi postman untuk menghitung waktu saat proses kompilasi  algoritma  FYS  dan  Bubble  Sort,  pengujian  dilakukan  menggunakan  data  yang bervariasi untuk mengetahui tingkat keefektifan algoritma FYS dan Bubble Sort, karena semakin banyak  data  semakin  lama  proses  pengacakan.  Saat  pengujian  memori  dalam  kondisi  kosong
1744
belum ada data yang tersimpan sehingga proses pengacakan dilakukan saat data belum tersimpan didalam memori ( register) . Hasil ditunjukan pada tabel 1 dan 2.
Tabel 1. Hasil Pengacakan Algoritma FYS Jumlah Data  Waktu Proses  Ukuran Database 100 165 ms 71,2 kb 200 262 ms 111 kb 300 272 ms 151 kb 400 315 ms 191 kb 500 510 ms 232 kb
Tabel  1.  Merupakan  hasil  pengujian  kecepatan  pengacakan  menggunakan  algoritma  FYS, pengujian dilakukan menggunakan Tools web browser, dengan kecepatan request API, data yang diperoleh adalah pada saat pengacakan soal 100 data soal memperoleh waktu 165 ms dan pada saat 200 data soal memperoleh waktu 262 ms, pada pengacakan 300 data memperoleh waktu 272 ms yang merupakan perbedaan yang tidak terlalu jauh pada saat pengacakan 200 data, dan pada saat pengacakan 400 data soal memperoleh waktu 315 ms, 500 soal adalah 510 ms. waktu Rata- rata yang dihasilkan pada hasilkan pada proses pengacakan sebanyak 500 data soal adalah 304,9 ms.
Gambar  10.  Menunjukan  Grafik  kecepatan  algoritma  FYS,  terlihat  peningkatan  waktu  proses pengacakan  dari  data  yang  terkecil  (100)  sampai  data  terbedar  (500),Kecepatan  terendah  pada 165 ms dengan penggunaan data sebanyak 100 data soal, dan kecepatan tertinggi pada 510 ms, saat  menggunakan 500 data  soal.  Semakin banyak data  semakin  lama  waktu pengacakan yang dilakukan oleh algoritma tersebut.
Tabel 2. Hasil Pengacakan Algoritma FYS Jumlah Data  Waktu Proses  Ukuran Database 100 142 ms 71,2 kb 200 222 ms 111 kb 300 271 ms 151 kb 400 287 ms 191 kb 500 303 ms 232 kb
Tabel 2. Adalah hasil pengujian kecepatan algoritma Bubble Sort menggunakan testing data 100, 200,300  dan  400  data  soal,  system  pengujian  sama  dengan  FYS  yaitu  menghitung  kecepatan dalam  mengurutkan  data  soal  secara  descending.  Hasil  yang  didapat  dalam  pengujian  dengan
Figure 10. Gambar Gafik Analisa Kecepatan FYS
1745
jumlah data 100 soal memperoleh waktu 142 ms, pada 200 soal meperolah waktu 222 ms, selisih yang didapat dari pengujian 100 dan 200 adalah ms. Pada pengujian 300 data memperoleh waktu 271 ms dan 400 data adalah 287 ms, dan waktu terlama pada saat pengujian 500 data yaitu 303 ms, waktu Rata-rata yang dihasilkan pada hasilkan pada proses pengacakan sebanyak 500 data soal adalah 245 ms.
Gambar  11.  Merupakan  Grafik  hasil  pengujian  algoritma  bubble  sort,  data  yang  diuji  dalam pengurutan data secara descending adalah 100, 200, 300, 400 dan 500 data. Kecepatan terendah pada 145 ms dengan penggunaan data sebanyak 100 data soal, dan kecepatan tertinggi pada 303 ms, saat menggunakan 500 data soal.Terjadi peningkatan saat pengujian perbedaan data, semakin banyak data yang diurutkan semakin lama waktu pengurutan.

## 4. KESIMPULAN
Kombinasi  Algoritma  FYS  dan  Bubbel  Sort  pada  aplikasi  ujian  berbasis  web,  FYS sebagai  algoritma  sederhana  yang  digunakan  untuk  melakukan  pengacakan  soal  ujian  berupa pilihan ganda, dan algoritma bubble sort digunakan untuk melakukan sorting data dengan metode descending atau melakukan pengurutan dari id terbesar yang diambil dari database
Hasil dari pengujian kedua algoritma tersebut adalah kecepatan yang dibutuhkan untuk melakukan  proses  pengacakan  data  soal  pada  FYS  dan  proses  pengurutan  pada  Bubble  Sort. Dimulai dari data pengujian terkecil  sebanyak 100 soal pada FYS membutuhkan waktu 165 ms, dan pengujian data terbanyak yaitu 500 soal memperoleh 510 ms, selisih yang dihasilkan adalah 345 ms, dan kecepatan rata-rata yang dihasilkan dari pengujian 100,200,300,400,500 data soal adalah 342 ms.
Pengujian  pada  algoritma  bubble  sort dengan  mengukur waktu  yang dibutuhkan untuk melakukan proses pengurutan data secara descending. Dari perolehan hasil pengujian dengan data 100,200,300,400,500 soal memperoleh kecepatan rata-rata 432 ms.

## 5. SARAN
Dalam  penelitian  hanya  mengkombinasikan  2  algoritma  untuk  diterapkan  pada  satu aplikasi  yang  sama,  saran  dari  penilit  untuk  penelitian  selanjutnya  adalah  mengkomparasi algoritma FYS dengan algoritma pengacakan yang lain, begitu juga untuk bubble sort agar dapat di komparasi dengan algoritma yang lain, untuk dapat menghasilkan kecepatan yang maksimum dalam implementasi di dalam system aplikasi.

## Gambar 11. Grafik Analisa Kecepatan Bubble Sort
1746
Bahasa pemrograman yang digunakan dalam penelitian kali ini adalah PHP. Penlis juga memberikan saran untuk mengkomparasi bahasa pemrograman lain untuk penerapan algoritma FYS  dan  bubble  sort.  Untuk  mengetahui  tingkat  keefektifan  bahasa  yang  digunakan  untuk membangun aplikasi ujian berbasi web.

## DAFTAR PUSTAKA
[1] C.  Kirana,  B.  Wijaya,  and  A.  Holil,  “Implementation  of  the  Fisher-Yates  Shuffle Algorithm  in  Exam-Problem  Randomization  on  M-Learning  Applications,” Khazanah Inform. J. Ilmu … , 2021.
[2] I. Haditama, C. Slamet, and D. Fauzy, “Implementasi Algoritma Fisher-Yates Dan Fuzzy Tsukamoto Dalam Game Kuis Tebak Nada Sunda Berbasis Android,” J. Online Inform. , vol. 1, no. 1, p. 51, 2016.
[3] G. Gunawan and D. A. Prabowo, “Sistem Ujian Online Seleksi Penerimaan Mahasiswa Baru Dengan Pengacakan Soal Menggunakan Linear Congruent Method  (Studi Kasus di Universitas Muhammadiyah Bengkulu),” J.  Inform.  Upgris ,  vol.  3,  no. 2, pp.  143–151, 2017, doi: 10.26877/jiu.v3i2.1872.
[4] F.  Ahmad,  “Penerapan  Algoritma  Fisher  Yates  Shuffle  dan  Linear  Congruent  Method Pada Simulasi Ujian Toefl Berbasis Android,” JURIKOM (Jurnal Ris. Komputer) , 2018.
[5] F. P. Juniawan and H. Hengki, “Pengacakan Soal Ujian Penerimaan POLRI Menggunakan Algoritme Fisher Yates Shuffle,” Telematika , 2019.
[6] F.  P.  Juniawan,  H. A.  Pradana,  and ...,  “Performance  comparison  of  Linear  Congruent method and Fisher-Yates Shuffle for data randomization,” J. Phys. … , 2019.
[7] A. Y. Ananta, K. S. Batubulan, and ..., “Implementasi Game Kuis Tebak Tangga Nada Jawa  Dengan  Metode  Fisher-Yates  Shuffle  dan  Fuzzy  Tsukamoto  Berbasis  Android,” Semin. Inform. … , 2020.
[8] Z. Phyo and E. C. Htoon, “Text Based Shuffling Algorithm in Digital Watermarking,” 2019 Int. Conf. … , 2019.
[9] J.  Febriansyah, Penerapan  Algoritma  Fisher-Yates  Shuffle  Pada  Aplikasi  Soal  Latihan Siswa Kelas X Teknik Komputer Jaringan Smkn 1 … . repository.atmaluhur.ac.id, 2020.
[10] G.  Aji, Implementasi  Algoritma  Fisher  Yates  Shuffle  untuk  Test  Harian  Siswa  (Studi Kasus: SMP Negeri 4 Ngaglik) . eprints.uty.ac.id, 2019.
[11] D.  Kumalasari,  “Analisis  Perbandingan  Kompleksitas  Algoritma  Bubble  Sort,  Cocktail Sort dan Comb Sort dengan Bahasa Pemrograman C++,” J. Speed , 2017.
[12] H.  Triansyah,  “Implemetasi  Metode  Bubble  Sort  dalam  Pengurutan  Indeks  Prestasi Mahasiswa,” J. Ilm. Inform. , 2019.
[13] R. R. Sitepu, M. Yusman, and F. E. Febriansyah, “Implementasi Algoritma Bubble Sort Dan  Selection  Sort  Menggunakan  Arraylist  Multidimensi  Pada  Pengurutan  Data  Multi Prioritas,” J. Komputasi , 2017.
[14] A. Maulana, F. Fauziah, and ..., “Penerapan Algoritma Fisher-Yates Untuk Mengacak Soal Penerimaan Forum Studi Mahasiswa Informatika Universitas Nasional,” JIPI (Jurnal … , 2020.
[15] S.  Gonjari,  “Music  Playlist  Manager  Using  Fisher-Yates  Shuffling  Algorithm  and Sorting,” World Wide J. Multidiscip. Res. Dev , 2017.
[16] A. Asriyanik and W. Apriyandari, “Implementation of the Algorithm Fisher Yates Shuffle on Game Quiz Environment,” J. Informatics … , 2020.