2 - Array
Prodi S1 Teknik Komputer
Apa itu Array?
▪ Array adalah struktur data yang terdiri dari sekumpulan elemen yang
memiliki tipe data yang sama, disimpan dalam memori secara berurutan.
▪ Karakteristik:
▪ Semua elemen dalam Array memiliki tipe data yang sama.
▪ Elemen-elemen disimpan dalam blok memori yang bersebelahan.
▪ Elemen diakses menggunakan indeks yang biasanya dimulai dari 0.
Deklarasi dan Inisialisasi Array dalam C
▪ Deklarasi Array
int arr[10]; // Deklarasi array dengan 10 elemen bertipe int
▪ Analisis Memori: Setiap elemen int memerlukan 4 byte (pada sistem 32-bit atau 64-bit), sehingga total
memori yang dialokasikan untuk array ini adalah 10 * 4 byte = 40 byte.
▪ Inisialisasi Array
int arr[5] = {1, 2, 3, 4, 5}; // Inisialisasi array dengan 5 elemen
▪ Analisis Memori: Memori yang digunakan tetap 5 * 4 byte = 20 byte, karena setiap elemen bertipe int.
▪ Mengakses Elemen Array
int firstElement = arr[0]; // Mengakses elemen pertama
arr[2] = 10; // Mengubah nilai elemen ketiga
▪ Time Complexity: O(1) karena akses ke elemen dilakukan secara langsung menggunakan indeks, tanpa
perlu mencari
Operasi Dasar pada Array
1. Traversal (Menelusuri Array)
▪ Operasi untuk mengunjungi setiap elemen dalam Array
▪ Contoh Program:
#include <stdio.h>
int main(){
int i;
for(int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
}
▪ Time Complexity: O(n) karena setiap elemen harus dikunjungi satu per satu.
2. Pencarian (Search)
▪ Operasi untuk menemukan elemen tertentu dalam Array
▪ Ada berbagai algoritma pencarian (searching) menggunakan array, salah satu yang paling
basic adalah Linear Search, yaitu mncari elemen dengan memeriksa setiap elemen dari
awal hingga akhir.
▪ Contoh Program Linear Search:
int search(int arr[], int size, int target) {
for(int i = 0; i < size; i++) {
if(arr[i] == target) {
return i; // Mengembalikan indeks elemen yang ditemukan
}
}
return -1; // Mengembalikan -1 jika elemen tidak ditemukan
}
▪ Time Complexity pada linear search: O(n) dalam kasus terburuk (elemen berada di akhir
array atau tidak ada).
3. Penyisipan (Insertion)
▪ Operasi untuk menambahkan elemen baru pada posisi tertentu dalam Array
▪ Contoh Program:
void insert(int arr[], int *size, int element, int position) {
for(int i = *size; i > position; i--) {
arr[i] = arr[i - 1]; // Geser elemen ke kanan
}
arr[position] = element;
(*size)++;
}
▪ Time Complexity: O(n) karena mungkin diperlukan penggeseran elemen-
elemen
4. Penghapusan (Deletion)
▪ Operasi untuk menghapus elemen dari Array
▪ Contoh Program:
void delete(int arr[], int *size, int position) {
for(int i = position; i < *size - 1; i++) {
arr[i] = arr[i + 1]; // Geser elemen ke kiri
}
(*size)--;
}
▪ Time Complexity: O(n) karena mungkin diperlukan penggeseran elemen-elemen
Space Complexity dan Time Complexity
pada Array
Space Complexity
▪ Ukuran Data
▪ Ukuran data dalam Array bergantung pada tipe data elemen dan jumlah elemen dalam
Array.
▪ Contoh:
▪ int arr[10] memerlukan 40 byte (10 elemen * 4 byte per elemen).
▪ char arr[10] memerlukan 10 byte (10 elemen * 1 byte per elemen).
▪ Alokasi Memori
▪ Memori untuk Array dialokasikan secara berurutan dalam blok memori yang
bersebelahan.
▪ Ini memungkinkan akses elemen dengan waktu konstan, tetapi juga berarti Array
memiliki ukuran tetap yang harus ditentukan saat deklarasi.
Space Complexity – lanj.
▪ Secara umum, kompleksitas memori pada Array adalah O(n), karena Array
memerlukan memori yang proporsional dengan jumlah elemen yang
disimpan
▪ Penggunaan Memori
▪ Memori yang dialokasikan untuk Array tidak bisa diubah setelah Array dibuat (kecuali
menggunakan Array dinamis).
▪ Efisiensi penggunaan memori bergantung pada seberapa banyak elemen dalam Array
yang benar-benar digunakan.
Time Complexity
1. Traversal: O(n)
2. Search:
▪ O(n) untuk linear search dalam kasus terburuk (elemen berada di akhir array atau
tidak ada),
▪ O(log n) jika array terurut dan menggunakan binary search.
3. Insertion: O(n) dalam kasus terburuk (penyisipan di awal) karena diperlukan
penggeseran elemen-elemen.
4. Deletion: O(n) dalam kasus terburuk (penghapusan di awal) karena
diperlukan penggeseran elemen-elemen
Latihan Soal
Latihan 1: Implementasi dan Traversal Array
▪ Buatlah program dalam C yang mendeklarasikan Array dengan 10
elemen bertipe integer, kemudian inisialisasi Array tersebut dengan
nilai 1 hingga 10. Cetak semua elemen Array.
▪ Lakukan analisis terhadap memori (space complexity) dan waktu
komputasi (time complexity) untuk traversal Array tersebut.
Latihan 2: Pencarian Linear dalam Array
▪ Buatlah program dalam C yang mencari elemen tertentu dalam Array
yang berisi 5 elemen menggunakan linear search. Program harus
meminta input dari pengguna untuk elemen yang dicari kemudian
menampilkan indeks elemen tersebut jika ditemukan
▪ Lakukan analisis terhadap memori (space complexity) dan waktu
komputasi (time complexity) untuk pencarian pada Array tersebut.
Latihan 3: Menghitung Rata-rata Elemen dalam
Array
▪ Buatlah program dalam C yang menghitung rata-rata dari semua
elemen dalam Array. Program harus meminta input dari pengguna
untuk jumlah elemen dalam Array dan nilai masing-masing elemen.
Tampilkan waktu komputasi untuk menghitung nilai rata-rata elemen,
terhitung setelah program menerima inputan dari pengguna.
▪ Lakukan analisis terhadap memori (space complexity) dan waktu
komputasi (time complexity) untuk pencarian pada Array tersebut.
Array Multidimensi
Apa itu Array Multidimensi?
▪ Array multidimensi adalah array yang memiliki lebih dari satu indeks atau dimensi
untuk mengakses elemen-elemennya.
▪ Array dua dimensi (2D array) adalah contoh paling umum dari array multidimensi,
yang sering digunakan untuk merepresentasikan data dalam bentuk tabel atau
matriks.
▪ Deklarasi array 2 dimensi:
int arr[baris][kolom];
▪ Deklarasi array 3 dimensi:
int arr[x][y][z]; // Array 3D dengan x, y, dan z dimensi
Deklarasi dan Inisialisasi Array Multidimensi
▪ Setelah dideklarasikan, array dua dimensi dapat diinisialisasi dengan 2 cara yaitu
secara langsung atau secara bertahap, seperti contoh berikut:
// Contoh deklarasi
int matrix[3][4]; // Array 3x4 (3 baris, 4 kolom)
// Inisialisasi langsung
int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
// Inisialisasi secara bertahap
int matrix[2][3];
matrix[0][0] = 1;
matrix[0][1] = 2;
matrix[0][2] = 3;
matrix[1][0] = 4;
matrix[1][1] = 5;
matrix[1][2] = 6;
Mengakses Elemen tertentu pada Array Multidimensi
▪ Untuk mengakses elemen array dua dimensi, kita menggunakan dua indeks: satu untuk
baris dan satu untuk kolom
int value = matrix[1][2]; // Mengakses elemen baris ke-2, kolom ke-3
▪ Akses ke elemen array tiga dimensi juga dilakukan dengan tiga indeks:
int value = array3D[1][2][3]; // Akses elemen baris ke-2, kolom ke-3, kedalaman ke-4
Space Complexity
▪ Array dua dimensi dengan ukuran 𝑛 baris dan 𝑚 kolom memiliki space
complexity sebesar 𝑂(𝑛 × 𝑚)
▪ Misalnya, array dua dimensi int matrix[3][4] membutuhkan space sebesar 3 × 4 ×
𝑠𝑖𝑧𝑒𝑜𝑓(𝑖𝑛𝑡).
▪ Jika sizeof(int) adalah 4 byte, maka total memory yang digunakan adalah 3×4×4=48
byte.
▪ Array tiga dimensi dengan ukuran 𝑛 baris 𝑚 kolom dan kedalaman 𝑝, space
complexity-nya sebesar 𝑂(𝑛 × 𝑚 × 𝑝) , dengan 𝑛, 𝑚, dan 𝑝 adalah ukuran
dari tiga dimensi array.
Space Complexity
▪ Untuk array dua dimensi int matrix[100][100], space complexity-nya
adalah:
𝑂(100×100) = 𝑂(10,000 elemen)
▪ Karena tipe datanya int, maka setiap elemen membutuhkan 4 byte,
sehingga total penggunaan memori adalah:
▪ 10,000 × 4 byte = 40,000 byte = 40 KB
Time Complexity
▪ Untuk akses elemen secara langsung: 𝑂(1)
▪ Traversal array dua dimensi: 𝑂(𝑛𝑥𝑚)
▪ Traversal array tiga dimensi: 𝑂(𝑛𝑥𝑚𝑥𝑝)
Latihan Soal
Latihan 1: Mencetak Elemen Array
▪ Lengkapi program yang mengisi dan mencetak elemen dari array dua
dimensi berikut ini.
#include <stdio.h>
int main() {
int i, j;
int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
// Menampilkan elemen array
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
return 0;
}
Latihan 2: Pencarian Linear dalam Array
▪ Buat program untuk menjumlahkan dua matriks berukuran 3x3 yang
diinput oleh pengguna.
▪ Lakukan analisis terhadap memori (space complexity) dan waktu
komputasi (time complexity) untuk pencarian pada Array tersebut.
Latihan 3: Menghitung Rata-rata Elemen dalam
Array
▪ Buatlah program yang mencari elemen terbesar dalam array dua
dimensi berukuran 4x4.
▪ Lakukan analisis terhadap memori (space complexity) dan waktu
komputasi (time complexity) untuk pencarian pada Array tersebut.