Tampilkan postingan dengan label PEMROGRAMAN DASAR XI TKJ. Tampilkan semua postingan

Jumat, 11 Maret 2016

Pencarian dan Pengurutan Data

Tujuan:Mempelajari bagaimana mengatur sekumpulandata berdasar pada pengurutan dan pencarian STRUKTUR DATA
Pengurutan adalah upaya mengatursekumpulan data berdasar pada urutan (naik atau turun) Pencarian adalah upayamencari/mendapatkan satu atau lebih objek dari sekumpulan data STRUKTUR DATA
SortingPengurutan data dalam struktur data sangatpenting untuk data yang beripe data numerikataupun karakter.Pengurutan dapat dilakukan secara ascending(urut naik) dan descending (urut turun)Pengurutan (Sorting) adalah proses menyusunkembali data yang sebelumnya telah disusundengan suatu pola tertentu, sehingga tersusunsecara teratur menurut aturan tertentu.Contoh:Data Acak : 5 6 8 1 3 25 10Ascending : 1 3 5 6 8 10 25Descending : 25 10 8 6 5 3 1 STRUKTUR DATA
6 (enam) metode pengurutan yang akan dipaparkanPenyisipan Langsung (Straight Insertion Sort)Penyisipan Biner (Binary Insertion Sort)Seleksi (Selection Sort)Gelembung (Bubble Sort)Shell (Shell Sort)Quick (Quick Sort) STRUKTUR DATA
2 (dua) metode pencarian yang akan dipaparkan Pencarian Pencarian Sekuensial Biner(Sequential Search) (Binary Search) STRUKTUR DATA
Algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data ke dalam urutan tertentu, berdasarkan satu atau beberapa kunci dalam tiap–tiap – elemen 2 (dua) model urutan yaitu model urut naik (increase sort) dan urut turun (decrease sort). Contoh: Data 5,2,4,6. Diurut naik menjadi 2,4,5,6 Diurut turun menjadi 6,5,4,2.(Mengapa perlu Pengurutan dilakukan agar data pengurutan?) dapat dilihat dengan mudah. STRUKTUR DATA
Bubble SortMetode sorting termudahDiberi nama “Bubble” karena proses pengurutansecara berangsur-angsur bergerak/berpindah keposisinya yang tepat, seperti gelembung yangkeluar dari sebuah gelas bersoda.Bubble Sort mengurutkan data dengan caramembandingkan elemen sekarang denganelemen berikutnya. STRUKTUR DATA
Bubble Sort (2)Pengurutan Ascending :Jika elemen sekarang lebihbesar dari elemen berikutnya maka kedua elementersebut ditukar.Pengurutan Descending: Jika elemen sekarang lebihkecil dari elemen berikutnya, maka kedua elementersebut ditukar.Algoritma ini seolah-olah menggeser satu per satuelemen dari kanan ke kiri atau kiri ke kanan,tergantung jenis pengurutannya.Ketika satu proses telah selesai, maka bubble sortakan mengulangi proses, demikian seterusnya dari 0sampai dengan iterasi sebanyak n-1.Kapan berhentinya? Bubble sort berhenti jika seluruharray telah diperiksa dan tidak ada pertukaran lagiyang bisa dilakukan, serta tercapai perurutan yangtelah diinginkan. STRUKTUR DATA
Bubble Sort (3) STRUKTUR DATA
Bubble Sort (4) STRUKTUR DATA
Bubble Sort (5) STRUKTUR DATA
Bubble Sort (6)Dengan prosedur diatas, data terurut naik(ascending), untuk urut turun (descending)silahkan ubah bagian:if (data[j]<data[j-1]) tukar(&data[j],&data[j-1]);Menjadi:if (data[j]>data[j-1]) tukar(&data[j],&data[j-1]);“The bubble sort is an easy algorithm to program,but it is slower than many other sorts” STRUKTUR DATA
Selection SortMerupakan kombinasi antara sorting dan searchingUntuk setiap proses, akan dicari elemen-elemen yangbelum diurutkan yang memiliki nilai terkecil atau terbesarakan dipertukarkan ke posisi yang tepat di dalam array.Misalnya untuk putaran pertama, akan dicari data dengannilai terkecil dan data ini akan ditempatkan di indeksterkecil (data[0]), pada putaran kedua akan dicari datakedua terkecil, dan akan ditempatkan di indeks kedua(data[1]).Selama proses, pembandingan dan pengubahan hanyadilakukan pada indeks pembanding saja, pertukaran datasecara fisik terjadi pada akhir proses. STRUKTUR DATA
Selection Sort (2) STRUKTUR DATA
Insertion SortMirip dengan cara orang mengurutkan kartu,selembar demi selembar kartu diambil dandisisipkan (insert) ke tempat yang seharusnya.Pengurutan dimulai dari data ke-2 sampai dengandata terakhir, jika ditemukan data yang lebihkecil, maka akan ditempatkan (diinsert) diposisiyang seharusnya.Pada penyisipan elemen, maka elemen-elemenlain akan bergeser ke belakang STRUKTUR DATA
Insertion Sort (2) STRUKTUR DATA
Insertion Sort (3) STRUKTUR DATA
PerbandinganTabel Perbandingan Kecepatan MetodePengurutan DataUntuk data sejumlah 10.000 data padakomputer Pentium II 450 MHz STRUKTUR DATA
SoalCarilah 3 metode sorting lainnya dantuliskan dalam paper beserta source code,cara dan analisis dan tiap-tiap metodesorting yang ada! STRUKTUR DATA
Implementasi Algoritma Rekursi1_Faktorial dalam pascalProgram Rekursi1_Faktorial;uses crt, dos;Var n_faktorial,x : longint;Function faktorial (n: longint) : longint;Begin if (n = 0) or (n = 1) then faktorial := 1 else faktorial := n * faktorial ( n - 1);End;Begin Writeln(Masukan bilangan n yang anda inginkan); Readln (x); n_faktorial := Factorial(x); Writeln (x, ! adalah , n_faktorial);End. STRUKTUR DATA
Contoh Pemakaian Rekursi (Permutasi).Untuk menampilkan semua permutasi dari N karakter ’A’, ’B’, ’C’, danseterusnya, diperlukan rekursi karena proses permutasi akanmenampilkan karakter yang sama secara berulang.Contoh : Permutasi untuk n = 2 adalah : A B B AContoh : Permutasi untuk n = 3 adalah : A B C A C B B A C B C A C A B C B A STRUKTUR DATA
Prosedur DoPermutasiProcedure DoPermutasi (Input/Output A: TPermutasi ; mulai :byte){prosedur untuk mengerjakan hitungan permutasi untuk n objek}{K.Awal : sebuah nilai n diberikan untuk menyatakan banyaknya objek}{K.Akhir: Susunan huruf alphabet sebagai permutasi dari n objek dan dicetak ke piranti keluaran}DEKLARASI i : byte; Temp : char; STRUKTUR DATA
DESKRIPSI:If ( mulai = N ) then For i 1 to N do write ( A [ i ] ) Endfor Else For i mulai to N do temp A [ i ] A [ i ] A [ mulai ] A [ mulai ] temp DoPermutasi (A, mulai +1) Endfor EndelseEndif STRUKTUR DATA
Contoh : Algoritma Permutasi yang memanggil prosedur bernama DoPermutasi.Algoritma Permutasi{Algoritma program utama menentukan permutasi dari n obejk}{K.Awal : nilai n yang menyatakan banyak objek berupa huruf aplhabet sudah terdefinisi}{K.Akhir: susunan permutasi yang mungkin dari n objek berupa huruf alphabet dan dicetak ke piranti keluaran}DEKLARASIConst Max = 10Type TPermutasi = array [ 1..10 ] of charProcedure DoPermutasi (Input/Output A: TPermutasi ; mulai :byte){prosedur dengan parameter formal input/output} STRUKTUR DATA
DESKRIPSI: If ( mulai = N ) then for i ← 1 to N do write ( A [ i ] ) endfor else for i ← mulai to N do temp ← A [ i ] A[i] ← A [ mulai ] A [ mulai ] ← temp DoPermutasi (A, mulai +1) endfor endif STRUKTUR DATA

Pengertian Umum
Fungsi adalah sebuah blok pernyataan yang berisi sejumlah pernyataan yang dikemas dalam sebuah nama yang dapat dipanggil beberapa kali di beberapa tempat di dalam program.

Tujuan pembuatan fungsi :
Untuk memudahkan dalam pengembangan program, karena program dipecah menjadi beberapa program yang lebih kecil
Untuk menghemat ukuran program, ini akan terasa kalau ada beberapa deretan instruksi yang sama dan digunakan pada beberapa tempat di dalam program

Deklarasi / prototipe fungsi
Deklarasi / prototipe sebuah fungsi meliputi :

    Nama fungsi
    Tipe data nilai balik fungsi
    jumlah dan tipe data argumen fungsi

Format deklarasi untuk fungsi menghasilkan nilai balik :

Tipe Nama_fungsi(daftar_parameter);

Format deklarasi untuk fungsi yang tidak menghasilkan nilai balik :

void Nama_fungsi(daftar_parameter);

Definisi Fungsi
Setiap fungsi yang dipanggil di dalam program harus didefinisikan terlebih dahulu yang letaknya bisa dimana saja. Khusus untuk fungsi yang disediakan oleh sistem, definisi sebenarnya sudah ada dalam pustaka yang disebut sebagai file header contoh #include

Fungsi Tanpa Nilai Balik
Adakalanya suatu fungsi tidak perlu memiliki nilai balik. Misalnya fungsi yang hanya dimaksudkan untuk menampilkan suatu keterangan saja, pada fungsi seperti ini, tipe nilai balik fungsi yang diperlukan adalah void, contoh :

void tampilkan_judul()
{
cout << "PT. MOJA MAJU" <
cout << "JL. Buntu No.xx" <
cout << "www.gatewan.com" <
}

Contoh diatas adalah fungsi tanpa nilai balik sebab tidak ada pernyataan return, mengingat fungsi tersebut tidak memiliki nilai balik, namun penggunaan pernyataan return secara eksplisit juga diperkenankan, dalam hal ini digunakan sebagai formalitas, contoh :

void tampilkan_judul()
{
cout << "PT. MOJA MAJU" <
cout << "JL. Buntu No.xx" <
cout << "www.gatewan.com" <
return;
}

Contoh program fungsi tanpa nilai balik :

View:

Program:
//fungsi utama
void main()
{
clrscr();
tampilkan_judul();
line();
getch();
}

//definisi fungsi
void line()
{
cout<<"======================================="<<endl;
}

void tampilkan_judul()
{
cout<<"GATEWAN"<<endl;
cout<<"alamat : www.gatewan.com"<<endl;
cout<<"Yogyakarta"<<endl;

return;
}

Rabu, 11 November 2015

POINTER

Pointer

Pointer adalah variable yang berisi alamat memory sebagai nilainya dan berbeda dengan variable biasa yang berisi nilai tertentu. Dengan kata lain, pointer berisi alamat dari variable yang mempunyai nilai tertentu.

Dengan demikian, ada variabel yang secara langsung menunjuk ke suatu nilai tertentu, dan variabel yang secara tidak langsung menunjuk ke nilai.

Adapun bentuk umum dari pernyataan variabel pointer dalam C++ adalah :

Type *variabel-name

Dengan :

Type adalah tipe dasar pointer
Variabel name adalah nama variabel pointer
* adalah variabel pada alamatnya yang ditentukan oleh operand.

Contoh :

Int *int_pointer; // pointer to integer

Float *float_pointer; // pointer to float

Contoh :

//Program : pointer.cpp

#include <stdio.h>

main()

{

int a, *b;

a=20;

b=&a;

printf (" Pointer b menunjukkan alamat =%p\n",b);

printf (" Alamat tersebut berisi nilai :%d\n",*b);

}

//Program : pointer1.cpp

#include <iostream .h>

// cetak p dan *p

void main(void)

{

int v = 7, *p;

p = &v;

cout << " Nilai v = " << v << " dan *p = " << *p

<< "\nAlamatnya = " << p << '\n';

}

Bila program diatas dijalankan, maka hasilnya adalah sebagai berikut :

Nilai v = 7 dan *p = 7

Alamatnya = efffb24

//Program:pointer2.cpp

#include <iostream.h>

int main ()

{

int value1 = 5, value2 = 15;

int * mypointer;

mypointer = &value1;

*mypointer = 10;

mypointer = &value2;

*mypointer = 20;

cout << "value1==" << value1 << "/ value2==" << value2;

return 0;

}

Bila program diatas dijalankan, maka hasilnya adalah sebagai berikut :

“value1==” 10 << “/ value2==20

OPERATOR POINTER

Ada beberapa operator yang bisa digunakan dalam pointer. Operator tersebut adalah operator alamat (yang dilambangkan dengan simbol &) dan operator unary yang mengembalikan alamat dari operandnya.

Sebagai contoh, diasumsikan deklarasi sebagai berikut :

Int y = 5;

Int *yPtr;

Maka pernyataan :

YPtr = &y;

Pernyataan ini mengandung arti bahwa alamat dari variabel y ditujukan kepada variabel pointer yPtr.

Contoh lain :

Int balance, value;

Int *balptr;

Balance = 3200; // step 1

Balptr=&balance; // step 2

Value=*balptr; // step 3

Contoh diagram :

	Step 1			Step 2			Step 3

12		Balptr	12	100	Balptr	12	100	Balptr

100	3200	Balance	100	3200	Balance	100	3200	Balance

130		value	130		value	130	3200	value

Contoh :

//Program:pointer3.cpp

#include <iostream.h>

int main()

{

int *ptr, num; // Step 1

ptr = &num; // Step 2

*ptr = 100; // Step 3

cout << num << " ";

(*ptr)++; // Step 4

cout << num << " ";

(*ptr)*=2; // Step 5

cout << num << "\n";

return 0;

}

Bila program dijalankan :

100 101 202

Contoh diagram :

	Step 1			Step 2			Step 3			Step 4			Step 5

12	*int	Ptr	12	50	Ptr	12	50	Ptr	12	50	Ptr	12	50	Ptr

50	int	num	50	int	num	50	100	num	50	101	num	50	202	num

	...			...			...			...			...

EKSPRESI POINTER

Pointer Aritmatika

Hanya 4 operator aritmatik dapat digunakan pada pointer ++, = =, +, dan -. Asumsi integer 32 bit.

Contoh :

Int *p1;

p1++;

p1--;

Contoh :

//Program:pointer4.cpp

#include <iostream.h>

int main()

{

int i[10], *i_ptr;

double f[10], *f_ptr;

int x;

i_ptr = i; // i_ptr points to first element of i

f_ptr = f; // f_ptr points to first element of f

for(x=0; x<10; x++)

cout << i_ptr+x << " " << f_ptr+x << "\n";

return 0;

}

Bila program dijalankan :

0xeffffd9c 0xeffffd48

0xeffffda0 0xeffffd50

0xeffffda4 0xeffffd58

0xeffffda8 0xeffffd60

... ...

Pointer Perbandingan

Pointer dapat dibandingkan dengan menggunakan operator hubungan, seperti !=, ==, <, dan >.

Contoh :

//Program:pointer5.cpp

#include <iostream.h>

int main()

{

int num[10];

int *start, *end;

start = num;

end = &num[9];

while(start != end) {

cout << "Masukkan bilangan sebanyak 9 data : ";

cin >> *start;

start++;

}

return 0;

}

Data yang akan dimasukkan sebanyak 9 buah data dan program tidak akan berhenti apabila belum sampai 9 buah data.

POINTER VERSUS ARRAY

Array dan pointer adalah dua struktur data yang saling berkaitan satu dengan yang lain dalam C, dan dapat saling dipertukarkan penggunaannya. Karena array dapat didefinisikan sebagai pointer.

Contoh :

int *bPtr, b[5];

Dapat dibuat menjadi :

bPtr = b;

bPtr = &b[0];

Berarti bPtr ditugaskan untuk menunjukkan ke alamat elemen pertama dari array b atau b[0].

Elemen array b[3] dapat ditulis :

* (bPtr + 3)

Alamat &b[3] dapat ditulis :

bPtr +3

Deklarasi suatu variabel array x[] yang berisi nilai int dapat ditulis :

int *x;

Variabel array ganda dapat ditulis :

int y [ ] [ ];

int *y [ ];

int *( *y);

Penggunaan pointer dan array untuk deklarasi variabel array ganda untuk menyimpan empat buah elemen yang masing-masing bertipe string (array dari karakter).

char *suit [4] = { “Hearts”, “Diamonds”, “Clubs”, “Spades” };

Contoh :

//Program:pointer6.cpp

#include <iostream.h>

#include <stdio.h>

int main()

{

char str[80];

char token[80];

char *str_ptr, *tk_ptr;

cout << "Masukkan sebuah kalimat : ";

gets(str);

str_ptr = str;

while(*str_ptr) {

tk_ptr = token;

while( *str_ptr != ' ' && *str_ptr ) {

*tk_ptr = *str_ptr;

tk_ptr++;

str_ptr++;

}

if(*str_ptr) str_ptr++;

*tk_ptr = '\0';

cout << token << endl;

}

return 0; }

//Program:pointer7.cpp

#include <iostream.h>

#include <stdio.h>

int main()

{

char str[80];

char token[80];

int i, j;

cout << "Masukkan sebuah kalimat: ";

gets(str);

for(i=0; ; i++) {

for(j=0; str[i] != ' ' && str[i]; j++, i++)

token[j] = str[i];

token[j] = '\0';

cout << token << '\n';

if(!str[i]) break;

}

return 0;

}

Pada contoh program pointer 6 adalah program dengan pointer, sedangkan contoh program pointer 7 dengan menggunakan array. Hasil dari kedua program tersebut sama.

POINTER INDEX

Pointer tidak hanya dapat digunakan untuk mengakses elemen array, tetapi pointer juga dapat diindex seperti pada array.

Contoh :

//Program:pointer8.cpp

#include <iostream.h>

#include <ctype.h>

int main()

{

char str[20] = "hello tom";

char *p;

int i;

p = str;

for(i=0; p[i]; i++)

p[i] = toupper(p[i]);

cout << p;

return 0;

}

Bila program diatas dijalankan, maka hasilnya adalah sebagai berikut :

HELLO TOM

Proses pengindexan pointer dapat dilihat pada variabel p yang menunjuk pada variabel str yang berisi data nama dengan panjang 20. Fungsi toupper memperjelas proses pengindexan.

KONSTANTA STRING DAN POINTER

Konstanta string terlihat dalam program teks dan disimpan dalam tabel string serta setiap entry dalam tabel string, pointer string dibangkitkan.

Contoh :

//Program:pointer9.cpp

#include <iostream.h>

int main()

{

char *s;

s = "Pointers are fun to use.\n";

cout << s;

return 0;

}

Bila program diatas dijalankan, maka hasilnya adalah sebagai berikut :

Pointers are fun to use.

ARRAY POINTER

Pointer dapat diarraykan seperti tipe data yang lain dalam C++. Untuk menyatakan sebuah array pi dari pointer sebanyak 10 buah data yang bertipe 10 integer, dapat ditulis :

int *pi [10];

Untuk menentukan alamat dari variabel integer disebut var ke elemen ketiga dari pointer array, dapat ditulis :

int var;

pi [2] = &var

Contoh :

//Program:point10.cpp

#include <iostream.h>

int main ()

{

int numbers[5];

int *p;

p = numbers; *p = 10;

p++; *p = 20;

p = &numbers[2]; *p = 30;

p = numbers + 3; *p = 40;

p = numbers; *(p+4) = 50;

for (int n=0; n<5; n++)

cout << numbers[n] << ", ";

return 0;

}

Bila program diatas dijalankan, maka hasilnya adalah sebagai berikut :

10, 20, 30, 40, 50,

POINTER DALAM POINTER

C++ memperbolehkan penggunaan pointer dalam pointer yang berisi data yang sama atau berbeda. Dalam kondisi pointer biasa atau pointer tunggal, diagramnya adalah :

Pointer Variabel

value

address

Untuk pointer dalam pointer, diagramnya adalah :

value

Pointer Pointer Variabel

address

address

Contoh :

char a;

char *b;

char **c;

a = ‘z’;

b = &a;

c = &b;

Dengan misal data acak pada memori 7230, 8092, dan 10502, maka diagramnya adalah :

8092

a b c

7230

‘z’

7230 8092 10502

Dari diagram dapat disimpulkan :

· c adalah sebuah variabel dengan tipe (char**) yang berisi 8092

· *c adalah sebuah variabel dengan tipe (char*) yang berisi 7230

· **c adalah sebuah variabel dengan tipe (char) yang berisi ‘z’

Contoh :

//Program:point12.cpp

#include <iostream.h>

#include <stdio.h>

#include <string.h>

int main()

{

int x, *p, **q;

x = 10;

p = &x;

q = &p;

cout << **q; // prints the value of x

return 0;

}

Bila program diatas dijalankan, maka hasilnya adalah sebagai berikut :