Kasus 8.1 : Pencarian Linear (Linear Search).Assalamu’alaikum wr.wb
Pada kesempatan ini saya akan memposting Program dari materi SEARCHING AND SORTING , program ini akan dibuat dalam bentuk Flowchart dan C++ . Program yang akan di buat yaitu : Tentang : Pencarian Linear (Linear Search).
Algoritma :
function pencarian Linier (input aray : larik; kunci, ukuran : integer) : integer
Deklarasi
ketemu : boolean
i, n : integer
Deskripsi
ketemu <-- false;
n <-- 1
while ((n < ukuran) and (not ketemu)) do
if (aray[n] = kunci) then
ketemu <-- true { data ketemu }
i <-- n { pada posisi ke-i }
endif
else n <-- n+1 { cek data berikutnya }
endwhile
if ketemu then pencarianLinier <-- i { data ketemu pada posisi ke-i }
else pencarianLinier <-- -1 { data tidak ketemu }
endif
end
Berikut ini adalah Gambar Program Flowchart yang menggunakan Aplikasi RAPTOR :
Output/hasil compiler dari program tersebut :
Dan ini Gambar Program C++ yang Menggunakan Aplikasi Dev C++ :
#include <iostream>
#define UKURAN 100
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int pencarianLinier(int array[], int kunci, int ukuran){
int i;
for (i=0; i<=ukuran-1; ++i)
if (array[i] == kunci)
return i;
return -1;
}
int main(int argc, char** argv) {
int a[UKURAN], x, kunciPencarian, elemen;
for (x=0; x<=UKURAN-1; x++) a[x] = 2*x;
cout<<"Bilangan yang mau dicari : ";
cin>>kunciPencarian;
elemen = pencarianLinier(a,kunciPencarian,UKURAN);
if (elemen != -1)
cout<<kunciPencarian<<" Ditemukan pada posisi elemen ke " << elemen;
else
cout<<kunciPencarian<<" Tidak ada.";
return 0;
}
Kasus 8.2 : Pencarian Biner (Binary Search). Algoritma :
function pencarianBiner(input aray : larik; kunci, low, high : integer) : integer
Deklarasi
ketemu : boolean
i, middle : integer
Deskripsi
ketemu <-- false
while (low <= high) and (not ketemu) do
middle <-- (low+high) div 2
if (kunci = aray[middle]) then ketemu <-- true { data pencarian = data di tengah }
else if (kunci < aray[middle]) then high <-- middle – 1 {data akan dicari lagi di sebelah kiri}
else low <-- middle + 1 {data akan dicari lagi di sebelah kanan}
endif
endwhile
if ketemu then pencarianBiner := middle
else pencarianBiner := -1;
endif
Dan ini kodingan Program C++ yang Menggunakan Aplikasi Dev C++ :
#include <iostream>
#define UKURAN 15
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
void cetakHeader(void){
int i;
cout<<"\nSubscript : \n";
for (i=0;i<=UKURAN-1;i++) cout<<i<<" ";
cout<<"\n";
for (i=1; i <= 4*UKURAN; i++) cout<<"-";
cout<<"\n";
}
void cetakBaris(int b[], int low, int mid, int high){
int i;
for (i=0; i<=UKURAN-1; i++)
if (i<low || i>high) cout<< " ";
else if (i==mid) cout<< "*" <<b[i];
else cout<<b[i] << " ";
cout<<"\n";
}
int pencarianBiner(int b[], int kunciPencarian, int low, int high){
int i, middle;
while (low <= high) {
middle = (low+high) / 2;
cetakBaris(b, low, middle, high);
if (kunciPencarian == b[middle])
return middle;
else if (kunciPencarian < b[middle])
high = middle - 1;
else low = middle + 1;
}
return -1;
}
int main(int argc, char** argv) {
int a[UKURAN], i, kunci, hasil;
for (i=0; i<=UKURAN-1; i++) a[i] = 2*i;
cout<<"Masukkan bilangan antara 0-28 : ";
cin>>kunci;
cetakHeader();
hasil=pencarianBiner(a,kunci,0,UKURAN-1);
if (hasil != -1) cout<<kunci<<" ditemukan pada posisi : "<< hasil;
else
cout<<kunci<<" tidak ditemukan";
return 0;
}
Kasus 8.3 : (Bubble Sort) Algoritma :
Procedure Bubble_Sort (input/output x : larik, input n : byte)
Deklarasi
larik = array [1..100] of integer
i, a : byte
k : larik
j, bantu : integer
Deskripsi
for i <-- 1 to n-1 do
for j <-- i+1 to n do
if x[i] > x[j] then
tukar(x[i], x[j])
endif
endfor
endfor
Berikut ini adalah Gambar Program Flowchart yang menggunakan Aplikasi RAPTOR :
Output/hasil compiler dari program tersebut :
Dan yang ini Gambar Program C++ yang Menggunakan Aplikasi Dev C++ :
#include <iostream>
#include <cstdlib>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
void baca_data(int A[], int n) {
int i;
for (i = 0; i < n; i++){
cout<<"Data ke-" <<i+1<< " : ";
cin>>A[i];
}
}
void cetak_data(const int A[], int n) {
int i;
for (i = 0; i < n; i++)
cout<<A[i]<< " ";
cout<<"\n";
}
void tukar (int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void buble_sort (int x[], int n){
int i, j;
for (i = 0; i<n-1; i++)
for (j = i+1; j<n; j++)
if (x[i] > x[j]) tukar(&x[i], &x[j]);
}
int main(int argc, char** argv) {
int data[10], n;
cout<<"Banyak data : ";
cin>>n;
baca_data(data,n);
cetak_data(data,n);
buble_sort(data,n);
cetak_data(data,n);
return 0;
}
kasus 8.4 (Insertion Sort)
Algoritma :
procedure insertion_sort(input/output data:larik; input n:integer)
Deklarasi
k, j, temp : integer
Deskripsi
for k <-- 2 to n do
temp := data [k];
j := k-1;
while (temp <= data [j]) and (j > 1) do
data [j+1] := data [j];
j := j-1;
endwhile
if (temp >= data [j]) then data [j+1] := temp
else
data [j+1] := data [j];
data [j] := temp;
endif
endfor
Berikut ini adalah Gambar Program Flowchart yang menggunakan Aplikasi RAPTOR :
Dan yang ini Gambar Program C++ yang Menggunakan Aplikasi Dev C++ :
#include <iostream>
#include <conio.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
class Sorting {
friend istream& operator>>(istream& in, Sorting& a);
friend ostream& operator<<(ostream& out, Sorting& a);
public:
void baca_data();
void cetak_data();
void buble_sort();
void insertion_sort();
void selection_sort();
private:
void minimum(int , int, int&);
void tukar (int&, int&);
int data[10], n;
};
istream& operator>>(istream& in, Sorting& a) {
cout<<"Banyak data : ";
in>>a.n;
for (int i = 0; i < a.n; i++) {
cout<<"Data ke-" <<i+1<< " : ";
in>>a.data[i];
}
return in;
}
ostream& operator<<(ostream& out, Sorting& a) {
for (int i = 0; i < a.n; i++)
out<<a.data[i] << " ";
out<<"\n";
return out;
}
void Sorting::tukar (int &a, int &b){
int temp;
temp = a;
a = b;
b = temp;
}
void Sorting::insertion_sort(){
int i, j, temp;
cout<<"Data pertama sudah ada ditangan kiri, yaitu : " << data[0] << '\n';
for(j = 1; j < n; j++){
temp = data[j];
cout<<"\nData ke-" << j+1 << " yaitu " << data[j] << " diambil dari meja\n";
cout<<"Dilakukan penggeseran elemen :\n";
for(i = j - 1; (i >= 0) && (data[i] > temp); i--){
cout<<"data pd posisi ke-[" << i+1 << "] digeser ke posisi [" << i+2 << "]\n";
data[i+1] = data[i];
}
cout<<"Data baru masuk pada posisi ke-[" << i+2 << "]\n";
data[i+1] = temp; //Insert key into proper position
cout<<"Data saat ini adalah : ";
for (int k=0; k<=j; k++) cout << data[k] << " ";
getch();
}
}
int main(int argc, char** argv) {
Sorting angka;
cin>>angka;
angka.insertion_sort();
cout<<"\nHasil akhir adalah : \n";
cout<<angka;
return 0;
}
Kasus 8.5 (Selection Sort)Algoritma :
Procedure selection_sort(output A : larik; input n : integer)
Deklarasi
i, t : integer
Deskripsi
for i <-- 1 to n do
minimum(A, i, n, t);
tukar(A[i], A[t]); {tukar tempat elemen saat ini j dengan elemen terkecil yang ditemukan t}
endfor
Berikut ini adalah Gambar Program Flowchart yang menggunakan Aplikasi RAPTOR :
Dan yang ini Gambar Program C++ yang Menggunakan Aplikasi Dev C++ :
#include <iostream>
#include <cstdlib>
using namespace std;
void baca_data(int A[], int n){
int i;
for (i = 0; i < n; i++){
cout << "Data ke-%d : ",i+1);
cin >> A[i]);
}
}
void cetak_data(const int A[], int n){
int i;
for (i = 0; i < n; i++)
cout << "%d ",A[i]);
cout << "\n");
}
void tukar (int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void minimum(int A[], int dari, int n, int * tempat){
int i, min;
min = A[dari];
*tempat = dari;
for (i = dari+1; i<n; i++)
if (A[i] < min){
min = A[i];
*tempat = i;
}
}
void selection_sort(int A[], int n){
int i, t;
for (i = 0; i<n; i++){
minimum(A, i, n, &t);
tukar(&A[i], &A[t]);
}
}
int main(int argc, char** argv) {
int data[10], n;
cout << "Banyak data : ");
cin >> n);
baca_data(data,n);
cetak_data(data,n);
selection_sort(data,n);
cetak_data(data,n);
return 0;
}
Kasus 8.6 (Merge Sort)
Dev C++ :
#include <iostream>
#include <cstdlib>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef int larik[10];
void masuk_data(int A[], int n){
int i;
for (i = 0; i < n; i++){
cout << "Data ke-%d : ",i+1;
cin >> A[i];
}
}
void cetak_data(const int A[], int n) {
int i;
for (i = 0; i < n; i++)
cout << "%d ",A[i];
cout << "\n";
}
void merge(larik a, int kiri, int tengah, int kanan){
int bagianKiri, posTemp, banyakElemen, i;
larik temp;
bagianKiri = tengah - 1;
posTemp = kiri;
banyakElemen = kanan - kiri + 1;
while ((kiri <= bagianKiri) &&(tengah <= kanan))
if ((a[kiri] <= a[tengah])){
temp[posTemp] = a[kiri];
posTemp = posTemp + 1;
kiri = kiri + 1;
}
else{
temp[posTemp] = a[tengah];
posTemp = posTemp + 1;
tengah = tengah + 1;
}
/* kopi bagian kiri */
while ((kiri <= bagianKiri)) {
temp[posTemp] = a[kiri];
posTemp = posTemp + 1;
kiri = kiri + 1;
}
/* kopi bagian kanan */
while ((tengah <= kanan)) {
temp[posTemp] = a[tengah];
posTemp = posTemp + 1;
tengah = tengah + 1;
}
/* kopi kembali ke array asal */
for (i = 1; i <= banyakElemen; i++){
a[kanan] = temp[kanan];
kanan = kanan - 1;
}
}
void merge_sort(larik A, int kiri, int kanan){
int tengah;
if ((kiri < kanan)){
tengah = (kiri + kanan) / 2;
merge_sort(A, kiri, tengah);
merge_sort(A, tengah + 1, kanan);
merge(A, kiri, tengah + 1, kanan);
}
}
int main(int argc, char** argv) {
int n;
larik data;
cout << "Berapa data array : ";
cin >> n;
masuk_data(data, n);
cetak_data(data, n);
merge_sort(data, 0, n-1);
cetak_data(data, n);
return 0;
}
Kasus 8.7 (Quick Sort)Algoritma :
procedure quick_sort(output data : larik; input L, R : integer)
Deklarasi
i, j, p : integer
Deskripsi
p <-- data[(L+R) div 2]
i <-- L
j <--R
{ mulai membuat partisi }
while (i<=j) do
while (data[i] < p) do i <-- i+1 endwhile
while (data[j] > p) do j <-- j -1 endwhile
if (i<=j) then
tukar(data[i], data[j])
i <-- i+1
j <-- j-1
endif
endwhile
if (L < j) then quick_sort(data,L,j) endif
if (i < R) then quick_sort(data,i,R) endif
Dan yang ini Gambar Program C++ yang Menggunakan Aplikasi Dev C++ :
#include <iostream>
#include <cstdlib>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
void masuk_data(int A[], int n) {
int i;
for (i = 0; i < n; i++) {
cout << "Data ke-%d : ",i+1;
cin >> A[i];
}
}
void cetak_data(const int A[], int n) {
int i;
for (i = 0; i < n; i++)
cout << "%d ",A[i];
cout << "\n";
}
void tukar (int *a, int *b){
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void quick_sort(int data[], int L, int R) {
int i, j, p;
p = data[(L+R) / 2];
i = L;
j = R;
while (i<=j) {
while (data[i] < p) i++;
while (data[j] > p) j--;
if (i<=j){
tukar(&data[i], &data[j]);
i++;
j--;
}
}
if (L < j) quick_sort(data,L,j);
if (i < R) quick_sort(data,i,R);
}
int main(int argc, char** argv) {
int data[10], n;
cout << "Banyak data : ";
cin >> n;
masuk_data(data,n);
quick_sort(data,0,n-1);
cetak_data(data,n);
return 0;
}
Alhamdulillah kasus-kasus pada PPT 8 terselesaikan...
Wassalamu"alaikum wr.wb
