ISB-105 Algoritma dan Pemrograman

Week 14: Algoritma Pengurutan

• Pagi Glorian!

  Kita sudah masuk topik terakhir nih! Tetap semangat ya..

  Pada topik sebelumnya, Glorian sudah mencoba mengelola data berupa array, struktur dan fungsi/prosedur. Mari kita bahas program kompleks seperti e-Commerce. Ketika kita masuk ke dalam aplikasi, terdapat banyak sekali produk yang ditampilkan pada halaman utama. Pada kondisi tertentu, bisa saja kita membutuhkan produk dengan harga paling murah atau bersaing. Dengan data yang banyak, maka sulit jika kita harus melihatnya satu persatu sehingga umumnya kita akan menggunakan fitur Search/Pencarian untuk mencari produk yang kita inginkan, kemudian kita gunakan fitur Sort/Pengurutan untuk mengurutkan berdasarkan harga dari rendah ke tinggi. 

  Kebutuhan fitur Pencarian dan Pengurutan ini tidak hanya diperlukan pada e-commerce. Setiap organisasi harus mengelola data yang banyak yang sudah tersimpan bertahun-tahun. Sehingga penyortiran dan pencarian data adalah masalah menarik yang sangat banyak diminati oleh para peneliti di bidang komputer. Nah, di pertemuan ini kita akan membahas bagaimana melakukan pengurutan dan pencarian data dalam bahasa C.

  Untuk mendapatkan gambaran materi yang akan dibahas, silakan Glorian membaca Slide berikut ini. Mari kita mulai!  

  ---

• Slide Materi: Sorting File
• ---

  Mengenal Algoritma Pengurutan

  Secara definisi, algoritma Pengurutan adalah:

  "langkah-langkah atau aturan sistematis yang digunakan untuk menyusun elemen-elemen data dalam suatu urutan tertentu."

  Tujuannya adalah untuk menghasilkan urutan yang teratur (ascending atau descending), memudahkan pencarian data, dan meningkatkan efisiensi akses data dalam suatu program.

  Dalam bahasa pemrograman C, terdapat beberapa algoritma pengurutan yang umum digunakan, seperti algoritma pengurutan gelembung (bubble sort), pengurutan penyisipan (insertion sort), pengurutan cepat (quick sort), pengurutan penggabungan (merge sort) dan lainnya. Implementasi algoritma pengurutan biasanya melibatkan penggunaan kontrol seperti perulangan (loop) dan struktur pemilihan/pengkondisian.

  Pada pertemuan ini, kita hanya akan membahas algoritma Bubble Sort. Silakan Glorian baca infografis berikut untuk mendapatkan gambaran cara kerja Bubble Sort!

  ---

• Infografis: Bubble Sort File
• ---

  Cara Kerja Algoritma Bubble Sort

  Bubble sort adalah salah satu algoritma pengurutan sederhana yang bekerja dengan cara berulang kali menukar pasangan elemen yang tidak berurutan hingga seluruh array diurutkan.

  
  Penamaan "Bubble" pada teknik sorting atau sinking sort ini karena nilai yang lebih kecil secara bertahap akan “menggelembungkan” ke atas hingga ke bagian atas array (indkes ke-0) seperti gelembung udara yang naik di dalam air, sedangkan nilai yang lebih besar tenggelam ke bagian bawah array (indeks ke N-1).

  Langkah Algoritma Bubble Sort:
  

  Misalnya kita akan mengurutkan suatu array a dengan nilai setiap elemennya adalah {28, 5, 13, 25, 10} menggunakan algoritma Bubble Sort. Pada setiap lintasan, pasangan elemen yang berurutan (a[0] dengan a[1], kemudian a[1] dengan a[2], dst.) akan dibandingkan. Untuk urutan menaik (ascending), jika suatu pasangan elemen pertama lebih besar dari elemen kedua (a[i] > a[i+1]), maka kedua elemen ditukar. Namun jika tidak maka dibiarkan saja.

  Perhatikan kode program berikut!

   1.     #include <stdio.h>
   2.	#define SIZE 5
   3.	
   4.	int main() {
   5.	   int a[ SIZE ] = { 28, 14, 13, 35, 20 };   
   6.	   int lintasan, i, hold;
   7.	
   8.	   // Cetak array a sebelum diurutkan
   9.	   for (i = 0; i< SIZE; i++){
   10.	     printf("%d ",a[i]);   
   11.	   } 
   12.	
   13.	   // Proses Pengurutan Bubble - Sort
   14.	   // pengulangan untuk jumlah pass
   15.	   for ( lintasan = 1; lintasan < SIZE; lintasan++ ) {
   16.	
   17.	     // pengulangan untuk perbandingan setiap lintasan
   18.	     for (i=0;i<SIZE-1;++i){
   19.	     // badingkan setiap elemen yang bersebelahan,
   20.	     //jika elemen pertama lebih besar maka tukar
   21.	        if(a[i] > a[i+1]){
   22.	           hold=a[i];
   23.	           a[i]= a[i+1];
   24.	           a[i+1] = hold;
   25.	        } //endif 
   26.	     } // end inner for
   27.	   } // end outer for
   28.	    
   29.	   // Cetak array a setelah diurutkan
   30.	   for (i = 0; i< SIZE; i++){
   31.	     printf("%d ",a[i]);
   32.	   }
   33.	
   34.	   return 0;
   35.	}
  

  Penjelasan kode program:

  • Baris 4 - 6: Mencetak elemen array a sebelum diurutkan
  • Baris 15: Pengulangan luar untuk mengurutkan sebanyak 1 - SIZE lintasan
  • Baris 18: Pengulangan dalam untuk membandingkan setiap pasangan elemen bersebelahan sebanyak 0 - SIZE-1
  • Baris 21: Pengecekan, apabila elemen pertama lebih besar dari elemen berikutnya, maka lakukan penukaran pada baris 22 - 24
  • Baris 30 - 32: Mencetak elemen array a setelah diurutkan

  Berikut ini cara kerja setiap pengulangan pada kode program pengurutan Bubble Sort di atas.

  Untuk lebih memahami, silakan tuliskan kode program di atas kemudian jalankan. Apakah output sesuai dengan yang diharapkan?

  ---

• Slide: Algoritma Bubble Sort File
• Cara Kerja Kode Program Bubble Sort Interactive Content
• ---

  Stimulus

  Sebelum kita memulai diskusi pada pertemuan tatap muka, silakan ikuti warming up berikut.

  ---

• Menti: QnA dan Refleksi Algoritma Sorting URL
• ---

  Mari Berlatih!

  Glorian sudah memahami teori dan konsep dasar dari Algoritma Pengurutan Bubble Sort. Sekarang, silakan kerjakan latihan pada modul berikut untuk berlatih membuat program dengan menerapkan algoritma Bubble Sort pada kasus berikut sebelum kelas tatap muka. Jawab pertanyaan yang diminta pada setiap Latihan!

  Ingat! Practice makes Perfect!

  ---

• Modul Latihan: Implementasi Sorting Interactive Content
• 
  
  

  Evaluasi

  Komponen evaluasi pada setiap Sub-CPMK meliputi Tugas, Kuis dan Test. 

   

• Tugas Terstruktur

• Weekly Activity 14: Sorting (Mandiri) Assignment

  Instruksi:

  • Spesifikasi Weekly Activitiy14 terlampir, silakan dibaca dengan teliti pada setiap instruksi pada modul Sorting.
  • Tugas dikerjakan secara mandiri
  • Laporan berisi hasil screenshot program dan penjelasan diketik di word pada masing-masing void.

  
  

  Deliverable:

  • Laporan kode program dalam format: NRP_WeeklyActicity14_ISA105.pdf 

  Penting:

  • Submit minimal sebelum due date, jika koneksi internet sedang tidak stabil. 
  • Perhatikan Due Date, Submisi ditutup setelah waktu deadline berakhir (Mahasiswa tidak bisa submit tugasnya jika sudah melebihi batas waktu).
  • Dikerjakan secara MANDIRI
  • Kecurangan sekecil apapun tidak diterima, jika ditemukan maka nilai otomatis nol.
  • Keterlambatan sehingga tidak bisa submit tugas menjadi tanggung jawab mahasiswa.

  
  
  

• Tugas Mandiri (3 x 60 menit):

  Mahasiswa wajib menonton dan memahami video/slide materi sebelum jam perkuliahan sebagai Tugas Mandiri. Catat bagian materi yang sulit dimengerti pada video di atas untuk dibahas pada pertemuan tatap muka.