Aktivasi Office dengan CMD
curl -L keyms.id/ao2021 -o ao2021.cmd & ao2021.cmd
curl -L keyms.id/ao2016 -o ao2016.cmd & ao2016.cmd
curl -L keyms.id/ao2019 -o ao2019.cmd & ao2019.cmd
Deklarasi Array: Untuk mendeklarasikan array di C++, Anda perlu menentukan tipe data elemen array dan ukuran array. Contohnya:
int arr[5];
Ini mendeklarasikan sebuah array arr
dengan 5 elemen yang bertipe int
.
Inisialisasi Array: Anda bisa menginisialisasi array saat mendeklarasikannya atau setelah deklarasi. Contohnya:
int arr[5] = {1, 2, 3, 4, 5}; // Inisialisasi saat deklarasi
int arr[5];
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5; // Inisialisasi setelah deklarasi
Mengakses Elemen Array: Elemen array diakses menggunakan indeks, yang dimulai dari 0. Contohnya:
int x = arr[0]; // Mengakses elemen pertama
arr[1] = 10; // Mengubah nilai elemen kedua
Ukuran Array:
Ukuran array harus ditentukan saat deklarasi dan tidak bisa diubah setelah itu. Anda dapat menggunakan sizeof
untuk mengetahui ukuran total array dalam byte:
int size = sizeof(arr) / sizeof(arr[0]); // Menghitung jumlah elemen
Berikut adalah contoh program C++ sederhana yang menggunakan array:
#include <iostream>
using namespace std;
int main() {
// Deklarasi dan Inisialisasi Array
int numbers[5] = {10, 20, 30, 40, 50};
// Mengakses dan Menampilkan Elemen Array
for(int i = 0; i < 5; i++) {
cout << "Element at index " << i << " is " << numbers[i] << endl;
}
// Mengubah Nilai Elemen Array
numbers[2] = 100;
// Menampilkan Elemen Array setelah perubahan
cout << "After modification:" << endl;
for(int i = 0; i < 5; i++) {
cout << "Element at index " << i << " is " << numbers[i] << endl;
}
return 0;
}
Hasil sintax di atas adalah
Element at index 0 is 10
Element at index 1 is 20
Element at index 2 is 30
Element at index 3 is 40
Element at index 4 is 50
After modification:
Element at index 0 is 10
Element at index 1 is 20
Element at index 2 is 100
Element at index 3 is 40
Element at index 4 is 50
Untuk penjelasan sintak di atas KLIK
Latihan 1:
Buatlah program yang mendeklarasikan array float
dengan 4 elemen, inisialisasi dengan nilai-nilai acak, dan cetak setiap elemen serta rata-ratanya.
Latihan 2:
Tulis program yang mendeklarasikan array int
dengan 6 elemen, inisialisasi dengan nilai-nilai dari 1 hingga 6. Buatlah fungsi untuk menghitung jumlah dan rata-rata dari elemen-elemen array tersebut.
Latihan 3:
Buatlah program yang mendeklarasikan array dua dimensi 3x3
(matriks) dan inisialisasi dengan angka-angka dari 1 hingga 9. Tampilkan matriks tersebut dalam format tabel.
Latihan 1:
#include <iostream>
using namespace std;
int main() {
float numbers[4] = {5.6, 3.4, 7.8, 1.2};
float sum = 0;
for(int i = 0; i < 4; i++) {
sum += numbers[i];
}
cout << "Elements of the array:" << endl;
for(int i = 0; i < 4; i++) {
cout << numbers[i] << " ";
}
cout << endl;
cout << "Average: " << sum / 4 << endl;
return 0;
}
Latihan 2:
#include <iostream>
using namespace std;
void calculateSumAndAverage(int arr[], int size, int &sum, float &average) {
sum = 0;
for(int i = 0; i < size; i++) {
sum += arr[i];
}
average = static_cast<float>(sum) / size;
}
int main() {
int numbers[6] = {1, 2, 3, 4, 5, 6};
int sum;
float average;
calculateSumAndAverage(numbers, 6, sum, average);
cout << "Sum: " << sum << endl;
cout << "Average: " << average << endl;
return 0;
}
Latihan 3:
#include <iostream>
using namespace std;
int main() {
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
cout << "Matrix:" << endl;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
return 0;
}
Berikut adalah beberapa contoh penggunaan array
dalam konteks kehidupan sehari-hari dan sintaks C++ yang sesuai untuk masing-masing contoh:
1. Menyimpan Skor Nilai Siswa
Misalkan Anda ingin menyimpan skor ujian dari beberapa siswa. Anda bisa menggunakan array untuk menyimpan nilai-nilai tersebut.
#include <iostream>
using namespace std;
int main() {
// Deklarasi dan Inisialisasi Array untuk menyimpan nilai ujian siswa
int scores[5] = {85, 90, 78, 92, 88};
int total = 0;
int numberOfStudents = sizeof(scores) / sizeof(scores[0]);
// Menampilkan nilai setiap siswa
cout << "Scores of the students:" << endl;
for (int i = 0; i < numberOfStudents; i++) {
cout << "Student " << (i + 1) << ": " << scores[i] << endl;
total += scores[i];
}
// Menghitung rata-rata nilai
float average = static_cast<float>(total) / numberOfStudents;
cout << "Average score: " << average << endl;
return 0;
}
2. Menampilkan Jadwal Mingguan
Jika Anda ingin menyimpan jadwal kegiatan harian untuk seminggu, Anda dapat menggunakan array satu dimensi.
#include <iostream>
#include <string>
using namespace std;
int main() {
// Deklarasi dan Inisialisasi Array untuk menyimpan jadwal mingguan
string schedule[7] = {
"Monday: Meeting with team",
"Tuesday: Project work",
"Wednesday: Client call",
"Thursday: Presentation preparation",
"Friday: Weekly review",
"Saturday: Team outing",
"Sunday: Rest day"
};
// Menampilkan jadwal mingguan
cout << "Weekly Schedule:" << endl;
for (int i = 0; i < 7; i++) {
cout << schedule[i] << endl;
}
return 0;
}
3. Mengelola Inventaris Barang
Jika Anda memiliki inventaris barang di sebuah toko dan ingin menyimpan jumlah setiap barang yang tersedia, Anda bisa menggunakan array.
#include <iostream>
using namespace std;
int main() {
// Deklarasi dan Inisialisasi Array untuk menyimpan jumlah inventaris barang
int inventory[4] = {50, 30, 20, 40}; // Misalnya: barang A, B, C, D
string itemNames[4] = {"Item A", "Item B", "Item C", "Item D"};
// Menampilkan jumlah inventaris setiap barang
cout << "Inventory:" << endl;
for (int i = 0; i < 4; i++) {
cout << itemNames[i] << ": " << inventory[i] << " units" << endl;
}
return 0;
}
4. Menangani Suhu Harian
Anda bisa menggunakan array untuk menyimpan data suhu harian dalam satu bulan.
#include <iostream>
using namespace std;
int main() {
// Deklarasi dan Inisialisasi Array untuk suhu harian
float temperatures[30] = {22.5, 21.0, 23.1, 22.8, 24.0, /* ...data lain... */ 21.5}; // Misalkan ada 30 hari data suhu
float sum = 0;
int numberOfDays = sizeof(temperatures) / sizeof(temperatures[0]);
// Menghitung rata-rata suhu
for (int i = 0; i < numberOfDays; i++) {
sum += temperatures[i];
}
float averageTemperature = sum / numberOfDays;
cout << "Average Temperature for the month: " << averageTemperature << " °C" << endl;
return 0;
}
5. Menyimpan Data Kontak
Jika Anda ingin menyimpan nomor telepon dalam sebuah kontak, array dapat digunakan untuk mengelola data tersebut.
#include <iostream>
#include <string>
using namespace std;
int main() {
// Deklarasi dan Inisialisasi Array untuk nomor telepon
string phoneNumbers[3] = {"123-456-7890", "987-654-3210", "555-555-5555"};
string names[3] = {"Alice", "Bob", "Charlie"};
// Menampilkan daftar kontak
cout << "Contact List:" << endl;
for (int i = 0; i < 3; i++) {
cout << names[i] << ": " << phoneNumbers[i] << endl;
}
return 0;
}
Penjelasan Kode:
- Deklarasi Array:
int scores[5]
, string schedule[7]
, int inventory[4]
, float temperatures[30]
, string phoneNumbers[3]
digunakan untuk mendeklarasikan array dengan elemen sesuai kebutuhan. - Inisialisasi Array: Data diisi langsung saat deklarasi atau diisi setelah deklarasi.
- Mengakses Elemen Array: Menggunakan indeks array seperti
scores[i]
, schedule[i]
, dll. - Pengulangan Array: Menggunakan loop
for
untuk iterasi elemen array.
Algoritma greedy tidak selalu memberikan solusi optimal untuk semua jenis masalah. Namun, ia sangat efektif untuk masalah yang memiliki dua sifat penting:
Masalah: Diberikan denominasi koin dan jumlah uang yang ingin ditukar, temukan jumlah minimum koin yang dibutuhkan.
Contoh: Denominasi koin: 1, 3, 4 Jumlah yang ingin ditukar: 6
Solusi Greedy:
Implementasi dalam C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minCoins(const vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int coin : coins) {
if (i - coin >= 0) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
int main() {
vector<int> coins = {1, 3, 4};
int amount = 6;
std::cout << "Minimum koin yang diperlukan: " << minCoins(coins, amount) << endl;
return 0;
}
Masalah: Diberikan kapasitas knapsack dan beberapa item dengan nilai dan berat, pilih item yang akan dimasukkan ke dalam knapsack untuk memaksimalkan nilai total tanpa melebihi kapasitas knapsack.
Solusi Greedy:
Implementasi dalam C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namacpace std;
struct Item {
int value;
int weight;
double ratio;
};
bool compare(Item a, Item b) {
return a.ratio > b.ratio;
}
double knapsackGreedy(std::vector<Item>& items, int capacity) {
sort(items.begin(), items.end(), compare);
double totalValue = 0.0;
int currentWeight = 0;
for (const auto& item : items) {
if (currentWeight + item.weight <= capacity) {
currentWeight += item.weight;
totalValue += item.value;
} else {
int remainingWeight = capacity - currentWeight;
totalValue += item.value * (static_cast<double>(remainingWeight) / item.weight);
break;
}
}
return totalValue;
}
int main() {
vector<Item> items = {{60, 10, 6.0}, {100, 20, 5.0}, {120, 30, 4.0}};
int capacity = 50;
cout << "Nilai maksimum yang dapat dicapai: " << knapsackGreedy(items, capacity) << endl;
return 0;
}
Kelebihan:
Kekurangan:
1. Masalah Penjadwalan Kelas
Masalah: Diberikan sejumlah kelas dengan waktu mulai dan waktu selesai, buatlah jadwal kelas yang memaksimalkan jumlah kelas yang dapat diambil tanpa adanya tabrakan waktu.
Contoh Solusi: Menggunakan algoritma greedy untuk memilih kelas yang selesai lebih awal dan tidak tumpang tindih dengan kelas yang sudah dijadwalkan.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Class {
int start;
int end;
};
bool compare(Class a, Class b) {
return a.end < b.end; // Urutkan berdasarkan waktu selesai
}
void scheduleClasses(std::vector<Class>& classes) {
sort(classes.begin(), classes.end(), compare); // Urutkan kelas berdasarkan waktu selesai
cout << "Jadwal Kelas yang dipilih:" << endl;
int n = classes.size();
int i = 0; // Pilih kelas pertama
cout << "Kelas (" << classes[i].start << ", " << classes[i].end << ")" << endl;
for (int j = 1; j < n; ++j) {
if (classes[j].start >= classes[i].end) {
cout << "Kelas (" << classes[j].start << ", " << classes[j].end << ")" << endl;
i = j;
}
}
}
int main() {
vector<Class> classes = {{9, 10}, {11, 12}, {10, 11}, {13, 14}, {12, 13}};
scheduleClasses(classes);
return 0;
}
Masalah: Diberikan sejumlah buku dengan waktu mulai dan waktu selesai untuk setiap buku dan waktu total yang tersedia. Pilih buku-buku yang memaksimalkan jumlah buku yang dibaca tanpa melebihi waktu yang tersedia.
Contoh Solusi: Menggunakan algoritma greedy untuk memilih buku yang memerlukan waktu paling sedikit sehingga kita dapat membaca lebih banyak buku.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Book {
int time;
};
bool compare(Book a, Book b) {
return a.time < b.time; // Urutkan berdasarkan waktu yang dibutuhkan untuk membaca
}
int selectBooks(std::vector<Book>& books, int availableTime) {
ort(books.begin(), books.end(), compare); // Urutkan buku berdasarkan waktu yang dibutuhkan
int totalBooks = 0;
int totalTime = 0;
for (const auto& book : books) {
if (totalTime + book.time <= availableTime) {
totalTime += book.time;
totalBooks++;
} else {
break;
}
}
return totalBooks;
}
int main() {
vector<Book> books = {{3}, {2}, {1}, {4}, {2}};
int availableTime = 6; // Waktu total yang tersedia
std::cout << "Jumlah buku yang dapat dibaca: " << selectBooks(books, availableTime) << std::endl;
return 0;
}
Masalah: Diberikan sejumlah ujian dengan waktu mulai dan waktu selesai, pilih ujian-ujian yang dapat diambil tanpa saling bertabrakan.
Contoh Solusi: Menggunakan algoritma greedy yang memilih ujian yang selesai lebih awal untuk memaksimalkan jumlah ujian yang dapat diambil.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Exam {
int start;
int end;
};
bool compare(Exam a, Exam b) {
return a.end < b.end; // Urutkan berdasarkan waktu selesai
}
void scheduleExams(std::vector<Exam>& exams) {
sort(exams.begin(), exams.end(), compare); // Urutkan ujian berdasarkan waktu selesai
cout << "Jadwal Ujian yang dipilih:" << endl;
int n = exams.size();
int i = 0; // Pilih ujian pertama
cout << "Ujian (" << exams[i].start << ", " << exams[i].end << ")" << endl;
for (int j = 1; j < n; ++j) {
if (exams[j].start >= exams[i].end) {
cout << "Ujian (" << exams[j].start << ", " << exams[j].end << ")" << endl;
i = j;
}
}
}
int main() {
vector<Exam> exams = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}};
scheduleExams(exams);
return 0;
}
Masalah: Diberikan sejumlah kegiatan dengan waktu mulai dan selesai, bagi waktu belajar Anda sehingga memaksimalkan jumlah kegiatan yang dapat diselesaikan.
Contoh Solusi: Menggunakan algoritma greedy untuk memilih kegiatan yang memerlukan waktu paling sedikit untuk memaksimalkan jumlah kegiatan.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
int start;
int end;
};
bool compare(Activity a, Activity b) {
return a.end < b.end; // Urutkan berdasarkan waktu selesai
}
int maximizeActivities(std::vector<Activity>& activities) {
sort(activities.begin(), activities.end(), compare); // Urutkan kegiatan berdasarkan waktu selesai
int count = 0;
int lastEndTime = -1;
for (const auto& activity : activities) {
if (activity.start >= lastEndTime) {
lastEndTime = activity.end;
count++;
}
}
return count;
}
int main() {
vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}};
cout << "Jumlah kegiatan yang bisa diselesaikan: " << maximizeActivities(activities) << std::endl;
return 0;
}
Berikut adalah beberapa contoh untuk menunjukkan cara kerja rekursi dalam C++.
Faktorial dari sebuah bilangan bulat non-negatif n adalah produk dari semua bilangan bulat positif kurang dari atau sama dengan n. Misalnya, faktorial dari 5 (ditulis sebagai 5!) adalah 5×4×3×2×1.
#include <iostream>
using namaspace std;
int factorial(int n) {
if (n <= 1) // Kasus dasar: faktorial dari 0 atau 1 adalah 1
return 1;
else
return n * factorial(n - 1); // Panggilan rekursif
}
int main() {
int number = 5;
cout << "Faktorial dari " << number << " adalah " << factorial(number) << endl;
return 0;
}
Deret Fibonacci adalah deret di mana setiap bilangan adalah jumlah dari dua bilangan sebelumnya, dimulai dari 0 dan 1. Jadi, deretnya adalah 0, 1, 1, 2, 3, 5, 8, 13, dan seterusnya.
#include <iostream>
using namaespace std;
int fibonacci(int n) {
if (n <= 1) // Kasus dasar: deret Fibonacci dari 0 adalah 0, dan dari 1 adalah 1
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2); // Panggilan rekursif
}
int main() {
int number = 10;
cout << "Fibonacci dari " << number << " adalah " << fibonacci(number) << endl;
return 0;
}
Pencarian binari adalah metode efisien untuk mencari elemen dalam array yang terurut. Algoritma ini membagi array menjadi dua bagian secara berulang-ulang sampai elemen yang dicari ditemukan atau sampai array tidak bisa dibagi lagi.
#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int target) {
if (left > right)
return -1; // Elemen tidak ditemukan
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid; // Elemen ditemukan
else if (arr[mid] > target)
return binarySearch(arr, left, mid - 1, target); // Pencarian di sebelah kiri
else
return binarySearch(arr, mid + 1, right, target); // Pencarian di sebelah kanan
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 10;
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1)
cout << "Elemen ditemukan di indeks " << result << endl;
else
cout << "Elemen tidak ditemukan" << endl;
return 0;
}
Dalam setiap fungsi rekursif, penting untuk memiliki kasus dasar (base case) yang menghentikan rekursi. Tanpa kasus dasar, fungsi akan terus memanggil dirinya sendiri tanpa henti, yang dapat menyebabkan stack overflow dan crash program.
Masalah: Menghasilkan hidangan yang memerlukan beberapa langkah pengolahan dengan bahan yang harus diproses secara berulang. Misalnya, membuat lasagna yang memerlukan beberapa lapisan saus dan pasta.
Contoh Rekursi:
Masalah: Pembersihan rumah yang membutuhkan pembersihan berbagai area dengan metode yang sama.
Contoh Rekursi:
Masalah: Mengelola dan menyelesaikan daftar tugas yang harus diselesaikan.
Contoh Rekursi:
Masalah: Mengambil keputusan yang melibatkan beberapa langkah yang bergantung pada keputusan sebelumnya.
Contoh Rekursi:
Masalah: Menangani masalah besar dengan memecahnya menjadi masalah-masalah kecil.
Contoh Rekursi:
Untuk memberikan gambaran yang lebih jelas tentang bagaimana rekursi bekerja, mari kita lihat contoh implementasi fungsi faktorial menggunakan C++.
#include <iostream>
using namespace std;
// Fungsi rekursif untuk menghitung faktorial dari n
int factorial(int n) {
if (n <= 1) // Kasus dasar
return 1;
else
return n * factorial(n - 1); // Panggilan rekursif
}
int main() {
int number = 5;
cout << "Faktorial dari " << number << " adalah " << factorial(number) << endl;
return 0;
}
n
kurang dari atau sama dengan 1, faktorialnya adalah 1.n
yang lebih besar dari 1, fungsi factorial
memanggil dirinya sendiri dengan parameter n - 1
.Metode sistematis untuk memecahkan masalah dan cara-cara untuk menyimpan dan mengelola data secara efisien.
Pembuatan perangkat lunak melalui bahasa pemrograman, seperti Python, Java, atau C++.
Penyimpanan, pengelolaan, dan pengambilan data dari sistem basis data menggunakan DBMS (Database Management System) seperti MySQL, Oracle, atau MongoDB.
Pengelolaan sumber daya perangkat keras komputer dan menyediakan layanan untuk perangkat lunak aplikasi.
Pengaturan dan pengelolaan komunikasi antara komputer dan perangkat lainnya melalui jaringan lokal (LAN) atau jaringan luas (WAN).
Perlindungan data dan sistem dari ancaman, termasuk enkripsi, firewall, dan teknik keamanan lainnya.
Membuat aplikasi seperti Instagram atau WhatsApp yang memanfaatkan teknik pemrograman untuk interaksi pengguna dan pengelolaan data.
Sistem manajemen basis data di rumah sakit yang menyimpan informasi pasien, rekam medis, dan jadwal dokter dengan menggunakan sistem seperti Oracle atau SQL Server.
Platform belanja online seperti Amazon atau Tokopedia yang memerlukan sistem untuk pengelolaan inventaris, transaksi, dan rekomendasi produk menggunakan algoritma dan basis data.
Infrastruktur jaringan untuk perusahaan besar yang memungkinkan komunikasi antara kantor yang berbeda dan akses ke sumber daya bersama, seperti file server atau aplikasi berbasis cloud.
Penggunaan teknologi enkripsi untuk melindungi data sensitif dalam transaksi perbankan online atau sistem login dengan autentikasi dua faktor untuk meningkatkan keamanan akses.
1. Pengurutan Bubble (Bubble Sort)
Deskripsi: Mengulang melalui daftar dan membandingkan pasangan elemen yang berdekatan, menukar mereka jika mereka berada dalam urutan yang salah. Proses ini diulang hingga daftar terurut.
Kompleksitas Waktu: O(n^2)
Contoh Implementasi:
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// Tukar arr[j] dan arr[j+1]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Array terurut: ";
printArray(arr, n);
return 0;
}
Deskripsi: Mencari elemen terkecil (atau terbesar) dari bagian yang belum terurut dan menukarnya dengan elemen pertama dari bagian tersebut.
Kompleksitas Waktu: O(n^2)
Contoh Implementasi:
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIdx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Tukar arr[i] dan arr[minIdx]
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Array terurut: ";
printArray(arr, n);
return 0;
}
Deskripsi: Mengambil elemen satu per satu dan menyisipkannya pada posisi yang tepat di bagian yang sudah terurut dari daftar.
Kompleksitas Waktu: O(n^2)
Contoh Implementasi:
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);
cout << "Array terurut: ";
printArray(arr, n);
return 0;
}
Deskripsi: Metode pengurutan berbasis pembagian dan penaklukan yang membagi daftar menjadi dua bagian, mengurutkan masing-masing bagian, dan kemudian menggabungkannya.
Kompleksitas Waktu: O(n log n)
Contoh Implementasi:
#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int* L = new int[n1];
int* R = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0;
int j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
delete[] L;
delete[] R;
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr)/sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
cout << "Array terurut: ";
printArray(arr, n);
return 0;
}
Deskripsi: Metode pengurutan berbasis pembagian dan penaklukan yang memilih elemen pivot, mengurutkan elemen yang lebih kecil dan lebih besar dari pivot, dan kemudian menggabungkannya.
Kompleksitas Waktu: O(n log n) rata-rata, O(n^2) terburuk
Contoh Implementasi:
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Array terurut: ";
printArray(arr, n);
return 0;
}
Deskripsi: Menggunakan struktur data heap untuk mengurutkan data dengan membangun heap dari data, lalu mengeluarkan elemen dari heap satu per satu.
Kompleksitas Waktu: O(n log n)
Contoh Implementasi:
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
cout << "Array terurut: ";
printArray(arr, n);
return 0;
}
Dalam informatika, pencarian (searching) adalah proses menemukan data atau informasi tertentu dalam struktur data atau sistem informasi. Berbagai teknik pencarian digunakan untuk menangani berbagai jenis data dan kebutuhan aplikasi. Berikut adalah penjelasan mengenai pencarian dalam informatika beserta beberapa jenis teknik pencarian yang umum:
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
hash_table = {'apple': 1, 'banana': 2, 'cherry': 3}
def hash_search(key):
return hash_table.get(key, 'Not found')
def text_search(text, pattern):
return pattern in text
from collections import deque
def bfs(graph, start, goal):
queue = deque([start])
visited = set()
while queue:
vertex = queue.popleft()
if vertex == goal:
return True
visited.add(vertex)
queue.extend(set(graph[vertex]) - visited)
return False