Modul 2 - Schematics-NPC-2021/Tutorial-Schematics-NPC-Junior-2021 GitHub Wiki
Fungsi adalah sebuah kumpulan statement untuk melakukan tugas spesifik, yang bisa membutuhkan input ataupun tidak, untuk menghasilkan output yang sesuai.
Secara umum, fungsi dibedakan menjadi dua, yakni fungsi Standard Library dan fungsi yang dibuat pengguna. Fungsi Standard Library adalah fungsi bawaan yang telah disertakan dalam library standar, misal fungsi printf(), scanf() yang ada di dalam library <stdio.h>. Sedangkan fungsi yang dibuat oleh pengguna (user-defined) adalah fungsi yang sengaja dibuat oleh pengguna untuk memenuhi keperluan pengguna dalam membuat program.
Tujuan dibuatnya fungsi secara umum adalah untuk membuat program menjadi lebih modular. Fungsi digunakan ketika ingin menjalankan serangkaian perintah secara berulang kali, terkadang dengan input yang berbeda, dengan tujuan tidak mengulang penulisan kode berkali-kali, serta apabila nantinya program mengalami bug akan mempermudah proses perbaikan.
Sebelum fungsi dapat digunakan dan bisa dipanggil, perlu dilakukan pendefinisan terlebih dahulu. Pendefinisian ditujukan untuk mendefinisikan apa yang fungsi tersebut lakukan ketika fungsi tersebut dipanggil.
Berikut adalah sintaks untuk melakukan pendefinisan fungsi:
<return_type> <nama_fungsi>(<parameter1>, <parameter2>, ...)
{
statement;
statement;
...
...
...
}
Berikut adalah contoh fungsi untuk mencetak string "Aku Sebuah Fungsi.":
void cetak()
{
printf("Aku Sebuah Fungsi\n");
}
int main()
{
cetak();
return 0;
}Selain menggunakan pendefisian langsung seperti cara sebelumnya, fungsi juga dapat dibuat dengan prototipe. Prototipe fungsi (atau biasa disebut interface fungsi) adalah deklarasi dari sebuah fungsi tanpa definisinya. Deklarasi sebuah fungsi berisi return type, nama fungsi, dan parameter yang terlibat.
Untuk menuliskan prototipe fungsi, sintaksnya sebagai berikut:
// Deklarasi
<return_type> <nama_fungsi>(<parameter1>, <parameter2>, ...);
Contoh kode program menggunakan prototipe fungsi:
// Prototipe Fungsi
void cetak();
int main()
{
cetak();
return 0;
}
// Definisi Fungsi cetak()
void cetak()
{
printf("Aku Sebuah Fungsi\n");
}Parameter pada fungsi bersifat layaknya input yang diberikan kepada sebuah fungsi. Jumlah parameter pada sebuah fungsi bisa dibuat sebanyak-banyaknya sesuai kebutuhan.
Penulisan parameter fungsi sama dengan pendefinisian variabel dan tiap parameter dipisahkan oleh operator (,).
<tipe_data> <nama_parameter_1> , <tipe_data> <nama_parameter_2>, ...
Contoh:
void cetak(char str[])
{
printf("%s\n", str);
}
void jumlah(int a, int b)
{
int hasil = a + b;
printf("%d\n", hasil);
}Untuk memanggil fungsi, dilakukan dengan menulis nama fungsinya diikuti dengan tanda (). Apabila fungsi tersebut memiliki parameter maka di dalam tanda () dituliskan nilai/variabel/objek untuk dijadikan yang kita sebut dengan argumen dan dipisahkan tiap argumen dengan operator ,. Argumen-argumen yang dimasukkan harus sesuai dengan tipe data parameter fungsinya.
Contoh pemanggilan fungsi:
int main()
{
cetak();
tambahkan(2,5);
cetak("Halo, dunia");
}Jika kita menginginkan fungsi yang kita jalankan menghasilkan sebuah nilai atau sederhananya menghasilkan sebuah output, kita bisa menambahkan keyword return dan mendefinisikan return type dari fungsi tersebut. Fungsi yang memiliki return type bukan void pasti memiliki return value. Nilai yang dikembalikan oleh fungsi tersebut memiliki tipe data yang bersesuaian dengan return type-nya.
Saat menemui statement return pada fungsi, maka fungsi tersebut akan berhenti dari titik dimana return tersebut terdapat, kemudian kembali ke bagian kode yang memanggil fungsi tersebut.
Misal kita ingin mendapatkan hasil dari penjumlahan dua bilangan menggunakan fungsi bernama jumlah().
#include <stdio.h>
int jumlah(int a, int b);
int main()
{
int x = 2, y = 3, hasil;
hasil = jumlah(x, y);
printf("%d\n", hasil);
return 0;
}
int jumlah(int a, int b)
{
int hasil = a;
hasil += b;
return hasil;
}Rekursi merujuk kepada definisi suatu hal yang dilakukan secara berulang-ulang.
Gambar diatas juga merupakan salah satu representasi definisi dari rekursi. Di dalam dunia pemrograman istilah rekursi digunakan untuk menggambarkan fungsi yang bersifat rekursif.
Fungsi yang bersifat rekursif adalah fungsi yang memanggil dirinya sendiri didalam fungsi tersebut. Perhatikan contoh program di bawah:
#include <stdio.h>
void rekursi(int n)
{
printf("%d\n", n);
rekursi(n+1); // memanggil dirinya sendiri
}
int main()
{
rekursi(1);
return 0;
}Fungsi rekursi() merupakan fungsi yang bersifat rekusif karena didalamnya memanggil fungsi rekursi() itu sendiri.
Program sebelumnya akan terus mencetak tanpa henti karena fungsi tersebut tidak tahu kapan dirinya harus berhenti untuk memanggil dirinya sendiri. Karena dari itu kita perlu base case pada sebuah fungsi rekursif.
Base Case adalah sebuah kasus atau kondisi yang kita berikan kepada sebuah fungsi rekursif untuk berhenti memanggil dirinya lagi atau disebut juga terminating condition.
Recursive Case adalah kasus dimana sebuah fungsi diharuskan untuk memanggil dirinya sendiri, dalam kata lain sebuah fungsi tersebut belum mencapai base case-nya.
Kita ambil contoh fungsi rekursif untuk memangkatkan suatu bilangan bulat. Didefinisikan perpangkatan sebuah bilangan a pangkat m sebagai power(a, m), berarti dapat dituliskan:
Atau dapat didefinisikan sebagai fungsi rekursif:
Dengan base case-nya adalah:
Dapat diperhatikan bahwa base case dari fungsi power(a, m) adalah ketika power(a, 0) yang menghasilkan 1. Ketika sudah mencapai base case, maka tidak perlu melakukan pemanggilan fungsi itu lagi.
#include <stdio.h>
int power(int a, int m)
{
if (m == 0) return 1; // base case
return (a * power(a, m-1)); // recursive case
}
int main()
{
printf("%d\n", power(2,3));
return 0;
}
### Pass by Value
**_Pass by Value_** berarti saat kita memasukkan (_passing_) argumen pada fungsi, nilai dari argumen tersebut akan disalin ke variabel yang berada pada parameter fungsi. Karena hanya nilainya saja yang diterima oleh fungsi, perubahan yang terjadi pada variabel parameter fungsi tidak akan berpengaruh terhadap variabel asalnya.
Contoh:
```c
#include
void change(int a, int b)
{
a = a + 5;
b = b + 5;
}
int main()
{
int x = 10, y = 6;
change(x, y);
printf("%d %d\n", x, y);
return 0;
}
```
**Nilai pada variabel `x` dan `y` tidak berubah karena metode _passing_ yang digunakan adalah _Pass by Value_**.
### Pass by Address/Reference
Berbeda dengan sebelumnya, sesuai namanya, metode **Pass by Address** berarti argumen yang dimasukkan (_passing_) ke parameter fungsi adalah alamat memori variabel. **Segala perubahan yang terjadi pada variabel tersebut, juga mempengaruhi langsung ke variabel asalnya**. Hal ini terjadi karena argumennya adalah langsung berupa alamat memorinya.
```c
#include
void change(int *a, int *b)
{
*a = *a + 5;
*b = *b + 5;
}
int main()
{
int x = 10, y = 6;
change(&x, &y);
printf("%d %d\n", x, y);
return 0;
}
```
Karena parameternya menerima alamat memori, maka variabel parameternya harus berupa pointer.
Passing array sebagai parameter fungsi juga dapat dilakukan dengan pointer. Segala perubahan pada array akan berpengaruh pada array asalnya.
```c
#include
void printArr(int *arr)
{
// ...
// ...
}
int main()
{
int num[5] = {1, 2, 3, 4, 5}, i;
printArr(num);
// ...
// ...
return 0;
}
```
# Struct
## Pengenalan Struct
Dalam bahasa C, struct adalah salah satu tipe data turunan atau bisa disebut juga **user defined data type** yang dapat mengelompokkan beberapa variabel di bawah satu nama. Tidak seperti array yang hanya dapat menyimpan elemen dengan tipe data sama, **struct dapat mengelompokkan elemen dengan tipe data yang berbeda-beda**.
Contoh:
Perhatikan gambar di atas. Mahasiswa merupakan suatu entitas yang di dalamnya terdapat atribut-atribut berupa:
+ Nama
+ NRP
+ Umur
+ IPK
+ Semester
+ Status
Atribut-atribut inilah yang nantinya berperan sebagai member dari struct `Mahasiswa`.
### Deklarasi Struct
Seperti variabel, struct harus dideklarasikan terlebih dahulu sebelum bisa digunakan. Pendeklarasian struct menggunakan sintaks sebagai berikut.
```c
struct {
;
;
;
.
.
.
};
```
Berikut adalah contoh deklarasi struct berdasarkan kasus Mahasiswa di atas.
```c
struct Mahasiswa {
char nama[100];
char nrp[20];
int umur;
double ipk;
int semester;
int status;
};
```
### Variabel Struct
Setelah dideklarasikan, sebuah struct akan menjadi tipe data baru. Maka dalam kasus ini, struct `Mahasiswa` di sini menjadi tipe data baru dengan member-member berupa `nama`, `nrp`, `umur`, `ipk`, `semester`, dan `status`. Untuk membuat variabel dengan tipe data struct, dilakukan dengan sintaks berikut.
```c
struct ;
```
Contoh:
```c
struct Mahasiswa mhs1;
struct Mahasiswa mhs2;
```
Contoh di atas menunjukkan terdapat dua variabel `mhs1` dan `mhs2` bertipe struct `Mahasiswa`.
### Akses Member Struct
Lalu bagaimana cara untuk mengakses member dari variabel struct yang telah dibuat? Untuk mengakses member-member dari struct, digunakan operator dot (.) setelah nama variabelnya.
```c
.
```
Contoh:
```c
mhs1.umur = 19;
mhs1.semester = 3;
mhs2.umur = 20;
mhs2.semester = 5;
```
Contoh program untuk mendemonstrasikan Struct:
```c
#include
#include
struct Mahasiswa {
char nama[100];
char nrp[20];
int umur;
double ipk;
int semester;
int status;
};
int main(void)
{
struct Mahasiswa mhs1;
strcpy(mhs1.nama, "Ahmad");
strcpy(mhs1.nrp, "05111940000012");
mhs1.umur = 18;
mhs1.ipk = 3.94;
mhs1.semester = 3;
mhs1.status = 1;
printf("Nama\t: %s\n", mhs1.nama);
printf("NRP\t: %s\n", mhs1.nrp);
printf("Umur\t: %d\n", mhs1.umur);
printf("IPK\t: %.2lf\n", mhs1.ipk);
printf("Sem\t: %d\n", mhs1.semester);
printf("Status\t: %s\n", (mhs1.status == 1 ? "Aktif" : "Tidak Aktif"));
return 0;
}
```
### Array of Struct
Kita juga dapat membuat array dengan tipe data struct. Caranya sama persis dengan deklarasi array pada umumnya.
```c
#include
struct Point {
int x, y;
};
int main()
{
struct Point arr[3];
arr[0].x = 2, arr[0].y = 3;
arr[1].x = 5, arr[1].y = 3;
arr[2].x = 2, arr[2].y = 8;
printf("%d %d\n", arr[0].x, arr[0].y);
printf("%d %d\n", arr[1].x, arr[1].y);
printf("%d %d\n", arr[2].x, arr[2].y);
return 0;
}
```
# Soal Latihan
## Soal 1
Implementasikan fungsi bernama tambah berisi 3 parameter, di mana parameter pertama merupakan bilangan 1, parameter kedua merupakan bilangan 2, dan parameter terakhir adalah variabel tempat hasil output.
Contoh pemanggilan:
```c
int a = 1;
int b = 2;
int c;
tambah(a, b, &c);
printf(“%d”, c);
```
Output-nya:
```
3
```
## Soal 2
Buatlah struct untuk menyimpan data nilai UN mahasiswa yang berisi nama, nilai Matematika, nilai IPA, nilai Bahasa Indonesia, dan nilai Bahasa Inggris. Setelah itu buat program yang dapat memasukkan list data nilai UN lalu menampilkan data sesuai nama.
Keterangan: urutan pemasukan nilai adalah Matematika, IPA, Bahasa Indonesia, Bahasa Inggris. Berikut merupakan contoh input dan output. 4 kelompok data di awal merupakan jumlah data nilai UN yang akan dimasukkan. Angka 3 di akhir merupakan jumlah nama yang akan dicari.
Sample Input
```
4
Hope
100
90
20
90
Ricky
80
70
80
90
Maden
100
100
100
100
Tenten
90
80
99
100
3
Maden
Dennis
Tenten
```
Sample Output
```
Nilai Maden
Matematika : 100
IPA : 100
Bahasa Indonesia : 100
Bahasa Inggris : 100
Nilai Dennis tidak ditemukan
Nilai Tenten
Matematika : 90
IPA : 80
Bahasa Indonesia : 99
Bahasa Inggris : 100
```
## Soal 3
Buatlah fungsi bernama **reverse()** untuk me-reverse array of integer menggunakan pointer. Fungsinya dapat digunakan seperti berikut.
```c
int arr[5]
.
.
//input
reverse(arr, 5);
.
.
//print isi arr
```
Sample Input:
```
5
8 4 2 3 1
```
Sample Output:
```
1 3 2 4 8
```
***
# Algoritma Sorting
## Bubble Sort
Algoritma **Bubble Sort** merupakan proses pengurutan yang secara berangsur-angsur berpindah ke posisi yang tepat, karena itulah dinamakan Bubble yang artinya gelembung. Algoritma ini akan mengurutkan data dari yang terbesar ke yang terkecil (_ascending_) atau sebaliknya (_descending_).
Secara sederhana, **algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data di sebelahnya secara terus menerus hingga tidak ada lagi perubahan**. Bubble Sort adalah metode _sorting_ yang sederhana, namun merupakan metode pengurutan yang tidak efisien karena ketika mengurutkan data yang sangat besar akan sangat lambat prosesnya.
Sifat algoritma Bubble Sort adalah sebagai berikut:
1. Jumlah iterasi sama dengan banyaknya bilangan dikurang 1.
2. Di setiap iterasi, jumlah pertukaran bilangannya sama dengan jumlah banyaknya bilangan.
3. Dalam algoritma Bubble Sort, meskipun deretan bilangan tersebut sudah terurut, proses _sorting_ akan tetap dilakukan.
4. Tidak ada perbedaan cara yang berarti untuk teknik algoritma Bubble Sort _ascending_ dan _descending_.
**Implementasi Bubble Sort**:
```c
void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubbleSort(int arr[], int n) {
int i, j, swapped; // dioptimasi dengan bool `swapped`:
for (i = 0; i < n-1; i++) {
swapped = 0;
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(&arr[j], &arr[j+1]);
swapped = 1;
}
}
if (swapped == 0)
break;
}
}
```
## Insertion Sort
**Insertion Sort** merupakan salah satu jenis sort yang mirip seperti saat kalian melakukan pengurutan kartu remi di tangan. Algoritma ini dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Ide dasar dari algoritma ini adalah mencari tempat yang “tepat” untuk setiap elemen array.
Secara umum, langkah-langkah algoritma insertion sort adalah sebagai berikut.
1. Ambil elemen dari array ke-i.
2. Taruh di urutan sebelumnya ( arr[ …i-1] ) yang telah diurutkan di tempat yang sesuai.
**Implementasi Insertion Sort**:
```c
void insertionSort(int arr[]. int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
```
## Merge Sort
**Merge Sort** adalah algoritma sorting yang dilakukan secara rekursif dengan membagi array menjadi 2 bagian, melakukan merge-sort pada 2 bagian tersebut, lalu melakukan merge pada kedua array tersebut.
Secara formal, proses merge sort dapat dituliskan sebagai berikut:
```
Sort(L,R):
If(R > L):
1. M = (L + R) / 2
2. Sort(L,M)
3. Sort(M + 1,R)
4. Merge(L,R)
```
**Penjelasan lebih detail dan contoh implementasi**: [https://www.interviewbit.com/tutorial/merge-sort-algorithm/](https://www.interviewbit.com/tutorial/merge-sort-algorithm/)
Contoh alur rekursi untuk Merge Sort pada array dengan 8 elemen:
Pada setiap tahap, akan dilakukan proses _merge_. Proses _merge_ dilakukan dengan mengurutkan secara naif dengan memanfaatkan fakta bahwa kedua array hasil partisi sudah terurut.
Karena setiap kali rekursi ukuran array menjadi setengahnya, maka kedalaman maksimal rekursi adalah **log2(N)**.
Karena di setiap tahap rekursi total proses _merge_ yang dilakukan ada sebanyak N, maka total kompleksitas pengurutan menggunakan Merge Sort adalah **N log2(N)**.
## Quick Sort
Mirip seperti Merge Sort, **Quick Sort** adalah algoritma sorting yang dilakukan secara rekursif dan menggunakan prinsip Divide and Conquer.
Secara formal, proses Quick Sort dapat dituliskan sebagai berikut:
```
Sort(L,R)
If (R > L):
1. M = Partisi(L,R). //M adalah index yang posisinya sudah fix.
2. Sort(L,M - 1)
3. Sort(M + 1,R)
```
Sedangkan untuk bagian partisi dapat dituliskan sebagai berikut:
```
Partisi(L,R):
1. Pivot = arr[L]
2. storeIndex = L + 1
3. Iterasi i dari L + 1 sampai R, jika arr[i] < pivot, lanjut ke step 4.
4. swap(arr[i],arr[storeIndex])
5. storeIndex = storeIndex + 1
6. Jika i masih kurang dari atau sama dengan R, kembali ke step 3. Jika tidak, lanjut ke step 7
7. swap(arr[L],arr[storeIndex - 1])
8. Return storeIndex - 1
```
Terkait proses partisi, terdapat berbagai cara dalam pemilihan pivot. Bisa saja menggunakan data paling kiri (seperti di atas), data paling kanan, atau data _random_, tergantung implementasi masing-masing.
**Penjelasan lebih detail dan contoh implementasi**: [https://www.interviewbit.com/tutorial/quicksort-algorithm/](https://www.interviewbit.com/tutorial/quicksort-algorithm/)
---
Jika dirata-rata, total kompleksitas dari Quick Sort adalah **O(N log2(N))**. Meskipun begitu, kompleksitas terburuk dari Quick Sort adalah **O(N2)**. Proses partisi dengan cara memilih index random sebagai pivot terbukti cukup efisien untuk membuat **Quick Sort** dilakukan dalam kompleksitas **O(N log2(N))**.
Merge Sort dan Quick Sort adalah algoritma _sorting_ yang paling umum dipakai karena memiliki efisiensi yang sangat baik meskipun terdapat algoritma yang lebih efisien seperti Radix Sort. Sedangkan untuk Bubble Sort dan Insertion Sort hampir tidak pernah dipakai. Algoritma tersebut sebaiknya hanya dipelajari untuk pengetahuan saja.
Di antara Merge Sort dan Quick Sort, penggunaan Quick Sort sering kali lebih dipilih dikarenakan Quick Sort adalah algoritma pengurutan yang bersifat _in-place_ yang berarti tidak membutuhkan memori tambahan dalam implementasinya, tidak seperti Merge Sort yang membutuhkan memori tambahan dengan ukuran yang linear terhadap array yang akan di-_sort_.
# Algoritma Searching
## Linear Search
Algoritma searching yang paling mudah untuk dipahami dan diimplementasikan adalah **Linear Search** atau biasa juga disebut dengan **Sequential Search**. Linear Search bekerja dengan melakukan pengecekan kepada semua elemen yang ada.
Secara garis besar, cara kerja Linear Search adalah:
1. Memeriksa item satu per satu.
2. Apabila ditemukan, maka “ketemu”.
3. Jika sampai akhir belum ditemukan, maka item yang dicari tidak ada.
**Implementasi Linear Search**
```c
int linearSearch(int arr[], int n, int item) {
int i;
for(i = 0; i < n; ++i) {
if(item == arr[i])
return 1;
}
return -1;
}
```
## Binary Search
**Binary Search** adalah teknik pencarian di mana untuk setiap iterasinya kita membagi _space_ pencarian menjadi hanya setengah dari _space_ pencarian awal hingga kita menemukan yang kita cari.
Untuk menerapkan teknik ini, kita harus memastikan bahwa data yang kita punya memiliki properti monoton naik atau turun ([https://en.wikipedia.org/wiki/Monotonic_function](https://en.wikipedia.org/wiki/Monotonic_function)).
> Gambar kiri dan tengah memiliki properti monoton serta gambar kanan tidak.
### Contoh 1
Ada array ukuran N (N <= 10^5), elemennya bisa sampai 10^9, arraynya sorted secara _ascending_.\
Ada Q query (Q <= 10^5). Tiap query dikasih angka K, jawab kalau K ada di array atau tidak.
**Solusi**\
Kata kunci: **Sorted**\
Karena arraynya _sorted_, berarti array tersebut memiliki properti monoton.
**Contoh**\
[2,3,8,10,13,17,28,35]
Cukup jelas kalau array-nya monoton. Sekarang bagaimana melakukan Binary Search-nya?
Misalkan kita mau mengecek apakah angka 13 ada di array atau tidak. (i.e.: target = 13)
1. _Space_ pencarian kita adalah index [1,8].
2. Sekarang kita bagi array jadi 2 bagian, index [1,4] dan index [5,8]. Untuk tau target ktia ada di array pertama atau kedua, kita tinggal mengecek nilai tengah dari _space_ pencarian kita saat ini yaitu di index **(1 + 8) / 2 = 4**.
> Ini dibulatkan ke bawah karena index 4,5 tidak ada 🧐
3. Array pada index 4 bernilai 10. Karena kita tau bahwa array-nya _sorted_ secara _ascending_, berarti **index dari elemen 13 pasti berada di kanannya**.
4. Sekarang _space_ dari pencarian kita adalah index[5,8].
5. Bagi array menjadi 2 bagian lagi, [5,6] dan [7,8]. Lalu cek tengahnya lagi yaitu di index **(5 + 8) / 2 = 6**.
6. Array pada index 6 bernilai 17. Karena kita tahu bahwa array-nya _sorted_ secara _ascending_, berarti **index dari elemen 13 pasti berada di kirinya**.
7. Sekarang _space_ dari pencarian kita adalah index[5,5].
8. Karena hanya tinggal tersisa 1 index, **kita hanya perlu mengecek apakah index 5 bernilai 13 atau tidak**.
**Visualisasi dan contoh implementasi**: [https://csacademy.com/lesson/binary_search](https://csacademy.com/lesson/binary_search)
Perhatikan bahwa pada proses pencarian, kita selalu membagi _space_ pencarian kita menjadi setengahnya. Maka dari itu, pada kasus terburuknya, iterasi akan dilakukan sebanyak **log2(N)** kali.
### Contoh 2
Ada N segi empat berukuran a x b. Segi empatnya tidak dapat diputar. Tentukan ukuran persegi terbesar yang bisa memuat semua segi empat tadi.
**Solusi**
Pengisian segi empat yang optimal adalah seperti berikut.
Dengan begitu, kita dapat membuat sebuah fungsi sebagai berikut: