BAHASA PEMROGRAMAN 1 (PERTEMUAN 3)

BAHASA PEMROGRAMAN 1 (PERTEMUAN 3) ARRAY KUMPULAN SOAL LATIHAN

PREPARED BY CHANDRA 092110187 05 – 06 – 2010 (REVISED)

PENGENALAN ARRAY Array dari Pesawat

Array dari Serangga

Array dari Kartu

Array dari Karakter

ARRAY  Seperti

yang Anda ketahui, variabel hanya bisa menampung 1 data saja. Jika ingin menampung data lebih banyak, maka variabel juga di-deklarasikan juga banyak. Oleh karena itu, dapat digunakan Array.  Array adalah sekelompok data yang bertipe sama.  Array bersifat Static, walaupun bisa diubah jadi Dynamic.

PERATURAN DALAM ARRAY  Peraturan

dalam penggunaan array:  Tidak ada assignment. Gunakan perulangan untuk memasukkan data ke tiap elemen array. A[0] = A[1]  Tidak ada perbandingan. Gunakan perulangan untuk membandingan antara 2 elemen. A[1] <= A[2]  Tidak ada operasi aritmatika. Gunakan perulangan untuk melakukan operasi aritmatika dalam array. A[3] = A[1] + A[2]

FORMAT UMUM ARRAY  Format

umum: [jumlah elemen];

 Contoh:

int n [20]; char nama [5]; float jumlah [50];

// n bisa menampung // 20 data (elemen). // nama bisa menampung // 5 elemen.

PENGISIAN NILAI ARRAY  Nilai

elemen array dapat diisi seperti konstanta.  Contoh: int n [5]; // deklarasi array n [0] = 0; // elemen pertama 0 n [4] = 15; // elemen kelima 15 int k [5] = {1,2,3,4}; // pengisian langsung char nama [ ] = “Hello”; // inisialisasi string Dan seterusnya…

PENGAKSESAN NILAI ARRAY  Misalkan

Anda telah mendeklarasikan dan mengisi nilai array seperti contoh: int n [5] = {1,2,3,4,5}; 0 1 2 3

 Maka

4

indeks

untuk mengakses nilai ke-3 dalam variabel n, dapat menggunakan n[2]. (Ingat! indeks array selalu dimulai dari 0)

KETIK PROGRAM (1) #include int main() { int jarak [ ] = {44, 720, 96, 468, 6}; cout << “Nilai posisi 2 = " << jarak [1] << endl; cout << “Nilai posisi 5 = " << jarak [4] << endl; system(“pause”); }

PENGGUNAAN ARRAY DENGAN PERULANGAN (KETIK PROGRAM) Pahami dan Apa hasil output dari program dibawah? #include int main() { int angka [5] = {4,6,1,7,3}; int k; for (k=0; k<5; k++) cout << angka [k] << “ “; system(“pause”); }

PEMBEDAHAN PROGRAM  int

angka [5] = {4,6,1,7,3}; Pendeklarasian variabel angka yang bertipe integer dan memiliki 5 elemen, yang mana indeks 0 bernilai 4 hingga indeks 4 bernilai 3.  int k; Variabel k digunakan untuk perulangan. Setiap perulangan, harus bertipe integer.

PEMBEDAHAN PROGRAM 



for (k=0; k<5; k++) for merupakan salah satu statement untuk perulangan. k=0 berarti perulangan dimulai dari 0. k<5 berarti perulangan berakhir hingga ke-4. k++ berarti perulangan akan bertambah 1. cout << angka [k] << “ “; cout akan mengeluarkan output dari indeks angka yang dihasilkan oleh perulangan (nilai k). Ketika k bernilai 0, maka akan ditampilkan 4. Ketika k bernilai 1, maka akan ditampilkan 6. Dst…

FLOWCHART PROGRAM START

int angka [5] = {4,6,1,7,3}; int k;

int angka [5] int k k=0

YES

k<5?

cetak angka [k] k++

NO

END

for (k=0;k<5;k++) cout << angka [k] << “ “;

INTERAKSI DENGAN USER  Kita

telah melihat bagaimana pendeklarasian array, cara mengisi nilai array, dan menampilkan output dari array (menampilkan output merupakan salah satu aspek untuk berinteraksi dengan user).  Ketika Anda ingin mendapatkan nilai array dari user, pertama sekali tentukan tipe data yang akan digunakan. Selanjutnya, tentukan seberapa banyak jumlah elemen yang akan dipakai oleh user.  Setiap elemen akan diletakkan di masingmasing index yang telah ditentukan.

KETIK PROGRAM (2) Perhatikan code listing dibawah! #include int main() { int page [5]; cout << “Masukkan jumlah halaman dari buku\n“; cout << "Buku 1: "; cin >> page [0]; cout << "Buku 4: "; cin >> page [3]; cout << "\nHasil Input Halaman Buku"; cout << "\nBuku 1: " << page [0] << “ halaman\n"; cout << "\nBuku 4: " << page [3] << " halaman\n"; system (“pause”); }

PEMBEDAHAN PROGRAM   



int page [5]; Pendeklarasian variabel array. cout << “Masukkan jumlah halaman dari buku\n“; cout << "Buku 1: "; cin >> page [0]; Program akan menampilkan output “Buku 1: “ yang mana akan menunggu input dari user. Hasil input user akan disimpan di variabel page indeks ke-1 (page [0]). cout << "Buku 4: "; cin >> page [3]; Sama seperti diatas, namun program akan menampilkan output “Buku 4: “. Hasil input akan disimpan di indeks ke-4 (page [3]).

PEMBEDAHAN PROGRAM  





cout << "\nHasil Input Halaman Buku"; cout << "\nBuku 1: " << page [0] << “ halaman\n"; Program akan menampilkan output “Buku 1: “ yang disertai hasil input user yang telah disimpan di page [0] dan diakhiri dengan output “ halaman”. cout << "\nBuku 4: " << page [3] << " halaman\n"; Sama seperti diatas, namun menampilkan output “Buku 4: “ yang juga disertai input user di page [3] dan diakhiri dengan “ halaman”. system(“pause”); Menahan layar agar tidak exit langsung.

ARRAY 2 DIMENSI  Data

yang disimpan dalam baris dan kolom biasanya disimpan dalam array 2 Dimensi.  Pendeklarasian array 2 dimensi: <jlh baris> <jlh kolom>; char nama [5] [5]; int nilai [10] [10]; int angka [2] [2] = {1,2,3,4};

CONTOH PENGGUNAAN ARRAY 2 DIMENSI (PENGISIAN & INDEKS) #include int main() { double distance [2] [4] = {44.14, 720.52, 96.08, 468.78, 6.28, 68.04, 364.55, 6234.12}; cout << "Members of the array"; cout << "\nDistance [0][0]" << ": " << distance[0][0]; cout << "\nDistance [0][1]" << ": " << distance[0][1]; cout << "\nDistance [0][2]" << ": " << distance[0][2]; cout << "\nDistance [0][3]" << ": " << distance[0][3]; cout << "\nDistance [1][0]" << ": " << distance[1][0]; cout << "\nDistance [1][1]" << ": " << distance[1][1]; cout << "\nDistance [1][2]" << ": " << distance[1][2]; cout << "\nDistance [1][3]" << ": " << distance[1][3]; cout << endl; system(“pause”); }

HASIL OUTPUT

KETIK PROGRAM (3) Pahami dan Apa output dari program dibawah? #include int main() { int bilangan [10] [10]; int baris; int kolom; for (baris = 0; baris < 10 ; baris++) for (kolom = 0; kolom < 10; kolom++) bilangan [baris] [kolom] = (baris+1) * (kolom+1); for (baris = 0; baris < 10 ; baris++) for (kolom = 0; kolom < 10; kolom++) cout << bilangan [baris] [kolom] << '\t'; system("pause"); }

HASIL OUTPUT

MASALAH UTAMA DALAM ARRAY 1.

2.

3.

Kelebihan elemen dalam array. Kelebihan elemen memakan memory yang cukup banyak. Fixed size. Kebanyakan array bersifat static, sehingga ukurannya tidak dapat berubah. Buffer overflow. Jika menambah data yang melebihi elemen array, maka akan terjadi buffer overflow error.

CONTOH 1

Buatlah program dengan array untuk menampilkan nilai seperti format dibawah: 1 2 3 4 5 6 7 8 9 10

DALAM BAHASA C

DALAM BAHASA C++

CONTOH 2 Buatlah program dengan array untuk mencetak 5 bilangan yang diinput oleh user! Contoh Output: Masukkan Bilangan: 90 Masukkan Bilangan: 70 Masukkan Bilangan: 10 Masukkan Bilangan: 45 Masukkan Bilangan: 1 Bilangan yang Anda input: 90 70 10 45 1

DALAM BAHASA C

DALAM BAHASA C++

CONTOH 3 ARRAY Ubahlah algoritma dibawah menjadi program kecil (tidak ada input user & deklarasi variabel): for i ← 1 to length [A] do for j ← length [A] downto i+1 do if A[j] < A[j-1] then exchange A[j] ↔ A[j-1]

DALAM BAHASA C / C++ for (i=0; i array [j]) { temp = array [j]; array [j] = array [j+1]; array [j+1] = temp; }

KUIS ARRAY Buatlah program dengan array untuk mencetak 3 nama dan jurusan dari input user! 2. Buatlah program dengan array untuk mencari bilangan terbesar dari n data yang diinput oleh user! 1.

KUIS ARRAY 3.

Modifikasilah contoh nomor 3 sehingga muncul output seperti dibawah:

JAWABAN 1 (DALAM BHS. C)

HASIL OUTPUT JAWABAN 1

JAWABAN 2 (DALAM BAHASA C++)

JAWABAN 3 (BAHASA C++)

BONUS 1 (SELECTION SORT)  Selection

Sort merupakan algoritma sorting yang kedua setelah Bubble Sort.  Selection Sort dikenal akan kemudahannya dan juga memiliki kemampuan yang lebih dibanding sorting yang lain dalam situasi tertentu.  Cara kerja selection sort: 1. 2. 3.

Cari nilai minimum dalam indeks array. Tukarkan nilainya di indeks pertama. Diulang terus kedua langkah diatas (dimulai dari posisi indeks kedua dan bertambah 1 setiap kali tukar posisi).

BONUS 1 (SELECTION SORT)  1.

2.

Fakta tentang Selection Sort: Selection sort memiliki kemampuan yang jauh lebih baik dibanding Bubble Sort dan Gnome Sort, tetapi secara umum, kalah dari Insertion Sort. Selection Sort kurang mampu menangani array dalam jumlah besar dan kalah dari Merge Sort.

BONUS 1 (SELECTION SORT) for (i = 0; i < n - 1; i++) { minIndex = i; for (j = i + 1; j < n; j++) { if (array [j] < array [minIndex]) minIndex = j; } if (minIndex != i) { temp = array [i]; array [i] = array [minIndex]; array [minIndex] = temp; } }

BONUS 2 (INSERTION SORT) 

Insertion sort merupakan algoritma sorting yang membandingkan elemen yang ada di dalam array hanya 1 kali cek saja.  Cara kerja Insertion Sort: 1. 2. 3.

4.

Tentukan index minimum. Bandingkan dengan elemen sebelumnya. Jika elemen sebelumnya lebih besar, maka isi nilai dengan nilai index minimum. Ulangi langkah diatas hingga terurut semua.

BONUS 2 (INSERTION SORT)  1.

2. 3.

Fakta tentang Insertion Sort: Lebih efektif untuk menangani data array yang berjumlah sedikit dan lebih baik dari Bubble Sort & Selection Sort. Langsung dilakukan sorting begitu data diterima. Kurang efisien dalam data array yang berjumlah banyak dibanding Quick Sort, Heap Sort, atau Merge Sort.

BONUS 2 (INSERTION SORT) for (i = 1; i < n; i++) { j = i; while (j > 0 && array [j - 1] > array [j]) { temp = array [j]; array [j] = array [j - 1]; array [j - 1] = temp; j--; } }

BONUS 3 (SHELL SORT)  Dikembangkan

tahun 1959 oleh Donald Shell, algoritma shell sort cepat dalam menangani array dan mudah di-coding.  Karena Shell Sort dibuat berdasarkan Insertion Sort yang telah diperbarui, maka cara kerjanya juga tidak jauh berbeda.  Shell Sort dapat menangani beberapa data sekaligus, sedangkan Insertion Sort hanya satu-persatu untuk pengurutan datanya.

BONUS 3 (SHELL SORT)  Cara

kerja dapat dilihat dari gambar :

BONUS 3 (SHELL SORT)  1. 2. 3.

Fakta tentang Shell Sort: Merupakan pengembangan dari Insertion Sort. Dapat menangani data hingga 5000 elemen. Masih lambat dalam menangani data banyak dibanding dengan Quick Sort, Heap Sort, atau Merge Sort.

BONUS 3 (SHELL SORT) d = length; do { d = (d + 1)/2; for (i =0; i < (length - d); i++) { if (array[i + d] > array[i]) { tmp = array[i+d]; array[i + d] = array[i]; array[i] = tmp; } } } while(d > 1);

BONUS 4 (HEAP SORT)  Heap

Sort merupakan pengembangan dari Selection Sort yang membandingkan antara tiap elemen.  Heap Sort akan mengecek data terbesar dan mengurutkannya dibagian belakang.  Heap Sort dapat membandingkan data lebih dari 1, sehingga dapat mempercepat pengurutan data.

BONUS 4 (HEAP SORT)  1. 2.

Fakta tentang Heap Sort: Heap Sort selalu bersaing dengan Quick Sort. Heap Sort kurang handal dalam menangani data di komputer yang lambat. Tidak seperti Merge Sort yang mudah beradaptasi dengan kemampuan komputer pengguna (user)

BONUS 4 (HEAP SORT) # heapify for i = n/2:1, sink(a,i,n) →invariant: a[1,n] in heap order # sortdown for i = 1:n, swap a[1,n-i+1] sink(a,1,n-i) →invariant: a[n-i+1,n] in final position end # sink from i in a[1..n] function sink(a,i,n): # {lc,rc,mc} = {left,right,max} child index lc = 2*i if lc > n, return # no children rc = lc + 1 mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc if a[i] >= a[mc], return # heap ordered swap a[i,mc] sink(a,mc,n)

BONUS 5 (MERGE SORT)  Merge

sort adalah algoritma sorting yang bersifat perbandingan. Dalam pelaksanaannya, sorting ini stabil, artinya menggantikan input order dari elemen yang sama dalam output yang telah terurut.  Merge Sort dikembangkan oleh John von Neumann tahun 1945.

BONUS 5 (MERGE SORT)  1.

2.

Fakta tentang Merge Sort: Merge Sort baik digunakan untuk mengurutkan data linked list dibanding Quick Sort dan Heap Sort. Merge Sort masih lambat dibanding Quick Sort dalam menangani data yang bersifat pointer array (RAM-Based Array).

BONUS 5 (MERGE SORT) # split in half m=n/2 # recursive sorts sort a[1..m] sort a[m+1..n] # merge sorted sub-arrays using temp array b = copy of a[1..m] i = 1, j = m+1, k = 1 while i <= m and j <= n, a[k++] = (a[j] < b[i]) ? a[j++] : b[i++] → invariant: a[1..k] in final position while i <= m, a[k++] = b[i++] → invariant: a[1..k] in final position