berlianhendrawanputra

Defenisi

Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Pada umumnya terdapat dua jenis pengurutan:

Ascending (Naik).
Descending (Turun).

Metode Pengurutan Data

Pengurutanberdasarkanperbandingan(comparison-based sorting)

Bubble sort, exchange sort

Pengurutanberdasarkanprioritas(priority queue sorting method)

Selection sort, heap sort

Pengurutanberdasarkanpenyisipandanpenjagaanterurut(insert and keep sorted method)

Insertion sort, tree sort

Pengurutanberdasarkanpembagiandanpenguasaan(devideand conquer method)

Quick sort, merge sort

Pengurutanberkurangmenurun(diminishing increment sort method)

Shell sort

1. Bubble Sort

Pengertian :

Bubble sort (metode gelembung) adalah metode / algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

2. Selection Sort

Pengertian :

Algoritma selection sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Selection Sort membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar.

3. Insertion Sort

Pengertian :

Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

4. Heap Sort

Pengertian :

Heapsort merupakan salah satu bentuk dari selection sort yang memiliki kompleksitas algorima O(n log(n)) yang menggunakan struktur data heap. Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap. Heap merupakan sebuah pohon biner hampir lengkap dimana isi dari simpul ayah selalu lebih besar dari isi simpul anak-anaknya sehingga simpul akar selalu merupakan elemen terbesar.

5. Shell Sort

Pengertian :

Algoritma ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan elemen-elemen dengan jarak tertentu. Insertion sort membandingkan elemen–elemen data yang berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai ini haruslah dicari sedemikian rupa agar tidak menulangi atau merusak hasil sorting sebelumnya.

6. Quick Sort

Pengertian :

Pengurutan ini berdasar pada prinsip devide and conquer. Devide adalah suatu langkah memilah masalah menjadi sub – masalah dalam proses rekursi, sedangkan conquer adalah proses menyelesaikan sub masalah tersebut, kemudian dilakukan pendekatan terhadap masalah utama. Pada dasarnya prinsip kerjanya adalah membagi atau memartisi sekumpulan data menjadi dua bagian sedemikian rupa sehingga elemen ke-i berada tepat pada posisisnya, dimana semua elemen yang nilainya lebih kecil daripada elemen ke-i akan terletak disebelah kirinya, sedangkan yang mempunyai nilai lebih besar berada disebelah kanannya. Algoritma ini memiliki kompleksitas O(n log n).

7. Merge Sort

Pengertian :

Merge sort merupakan salah satu teknik sorting yang menurutkan suatu data dengan cara penggabungan. Merge sort juga menggunakan proses divide and conquer pada rekursi. Berikut adalah langkah kerja merge sort :

Devide : Memilah elemen – elemen dari data menjadi dua bagian.

Conquer : Menyelesaikan setiap bagian dengan memanggil prosedur merge sort secara rekursif.

Kombinasi : Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.

Proses rekursi akan berhenti jika telah mencapai lemen dasar, atau artinya jika bagian yang diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah sesuai rangkaian.

8. Radix Sort

Pengertian :

Radix sort adalah salah satu algoritma sorting yang dilakukan tanpa melakukan perbandingan antardata yang dijadikan sebagai input. Makna harfiah Radix dapat diartikan sebagai posisi dalam angka. Dalam system decimal, radix adalah digit dalam angka decimal. Misalkan angka 37 mempunyai nilai radix 3 dan 7. Berdasarkan urutan pemrosesan radix-nya, ada 2 macam Radix sort. Pertama adalah LSD (Least Significant Digit) yaitu proses dimulai dari radix yang paling tidak signifikan(digit yang paling kanan). Kedua adalah MSD (Most Significant Digit), yaitu proses dimulai dari radix yang paling signifikan (digit yang paling kiri).

Contoh Metode Sorting

Bubble Sort

Tahap 1

20 10 15 5 3 2
20 10 15 5 2 3
20 10 15 2 5 3
20 10 2 15 5 3
20 10 2 15 5 3

20 2 10 15 5 3
2 20 10 15 5 3

Tahap 2

2 20 10 15 3 5
2 20 10 15 3 5
2 20 10 3 15 5
2 20 3 10 15 5
2 3 20 10 15 5

Tahap 3

2 3 20 10 15 5
2 3 20 10 5 15
2 3 20 5 10 15
2 3 5 20 10 15

Tahap 4

2 3 5 20 10 15
2 3 5 20 15 10
2 3 5 15 22 10

Tahap 5

2 3 5 1520 10
2 3 5 15 10 20

Selection sort

Awal

10	8	15	5	2
0	1	2	3	4

Tahap 1

I =2 , Lok =4 :

10	8	2	5	15
0	1	2	3	4

Tahap 2 :

I = 0, Lok 3

5	8	2	10	15
0	1	2	3	4

Tahap 3:

I = 1, Lok = 2

5	2	8	10	15
0	1	2	3	4

Tahap 4 :

I = 0, Lok = 1

2	5	8	10	15
0	1	2	3	4

Kumpulan Coding Bahasa C Sederha6

1. Paket Nasi

#include <stdlib.h>
#include <stdio.h>

int main ()
{
int menu, nasi=3000, ayam_bakar=7000, tahu=1000, tempe=1000, lalap=2000,
air_mineral=3000, sayur_asem=2000, gepuk=5000, air_hangat=1000,jumlah_pesanan,total,pajak,total_akhir;

printf("=========Selamat datang di Raka's Resto========== \n\n");
printf("PAKET MAKANAN \n");
printf("=============\n");
printf("Paket 1 \n");
printf("Paket 2 \n");
printf("Paket 3 \n");
printf("Silakan pilih paket menu yang ada :");
scanf("%d",&menu);
printf("Banyaknya pesanan :");
scanf("%d",&jumlah_pesanan);
printf("\n");

switch (menu){
case 1 :
printf("Paket 1 \n");
printf("Nasi :%d",nasi);
printf("\nAyam Bakar :%d",ayam_bakar);
printf("\nTahu :%d",tahu);
printf("\nTempe :%d",tempe);
printf("\nLalapan :%d",lalap);
printf("\nAir Mineral :%d",air_mineral);
printf("\nJumlah pesanan :%d paket",jumlah_pesanan);
total=(nasi+ayam_bakar+tahu+tempe+lalap+air_mineral)*jumlah_pesanan;
pajak=(total)*10/100;
total_akhir=total+pajak;
printf("\n");
printf("\nTotal, paket 1 * %d :%d",jumlah_pesanan,total);
printf("\nPajak 10 persen : %d",pajak);
printf("\nJadi, total yang harus anda bayar :%d",total_akhir);
printf("\n");
break;
case 2 :
printf("Paket 2 \n");
printf("Nasi :%d",nasi);
printf("\nAyam Bakar :%d",ayam_bakar);
printf("\nSayur Asem :%d",sayur_asem);
printf("\nTahu :%d",tahu);
printf("\nTempe :%d",tempe);
printf("\nLalapan :%d",lalap);
printf("\nAir Mineral :%d",air_mineral);
printf("\nJumlah pesanan :%d paket",jumlah_pesanan);
total=(nasi+ayam_bakar+sayur_asem+tahu+tempe+lalap+air_mineral)*jumlah_pesanan;
pajak=(total)*10/100;
total_akhir=total+pajak;
printf("\n");
printf("\nTotal, paket 2 * %d :%d",jumlah_pesanan,total);
printf("\nPajak 10 persen : %d",pajak);
printf("\nJadi, total yang harus anda bayar :%d",total_akhir);
printf("\n");
break;
case 3 :
printf("Paket 1 \n");
printf("Nasi :%d",nasi);
printf("\nGepuk :%d",gepuk);
printf("\nTahu :%d",tahu);
printf("\nTempe :%d",tempe);
printf("\nLalapan :%d",lalap);
printf("\nAir Hangat :%d",air_hangat);
printf("\nJumlah pesanan :%d paket",jumlah_pesanan);
total=(nasi+gepuk+tahu+tempe+lalap+air_hangat)*jumlah_pesanan;
pajak=(total)*10/100;
total_akhir=total+pajak;
printf("\n");
printf("\nTotal, paket 2 * %d :%d",jumlah_pesanan,total);
printf("\nPajak 10 persen : %d",pajak);
printf("\nJadi, total yang harus anda bayar :%d",total_akhir);
printf("\n");
break;
default:
printf("Maaf, Paket yang anda pilih tidak ada didalam menu..!! Silahkan Coba lagi :)\n");
}
system("pause");
return 0;
}

2. Menentukan Nilai Terbesar diantara 3 Bilangan.

#include <stdlib.h>
#include <stdio.h>

int main ()
{
int a, b, c;

printf("Masukan nilai a : ",a);
scanf("%d",&a);
printf("Masukan nilai b : ",b);
scanf("%d",&b);
printf("Masukan nilai c : ",c);
scanf("%d",&c);
printf("\n");

if (a>b){
if (a>c){
printf("A adalah yang terbesar",a);
}else{
printf("C adalah yang terbesar",c);
}
}else{
if (b>c){
printf("B adalah yang terbesar",b);
}else{
printf("C adalah yang terbesar",c);
}
}
printf("\n");
system("pause");
return 0;
}

3. Menghitung Luas Lingkaran.

#include <stdlib.h>

#include <stdio.h>

int main()

{

int r;

float phi, luas;

phi=3.14;

printf("Masukan jari-jari lingkaran (cm) :",r);

scanf("%i",&r);

luas=phi*r*r;

printf("Jadi luas lingkaran tersebut adalah :%f \n",luas);

system ("pause");

return 0;

}

4. Menghitung Luas Segitiga.

#include <stdlib.h>

#include <stdio.h>

int main()

{

int alas, tinggi;

float luas;

printf("Masukan tinggi segitiga (cm) :", tinggi);

scanf("%d",&tinggi);

printf("Masukan alas segitiga (cm) :", alas);

scanf("%d",&alas);

luas=((alas*tinggi)*0.5);

printf("Jadi luas segitiga tersebut adalah :%f \n",luas);

system ("pause");

return 0;

}

5. Menghitung Biaya Panggilan.

#include <stdlib.h>

#include <stdio.h>

int main()

{

int jamA, menitA, jamB, menitB, detikA, detikB, detik, waktuA, waktuB, biaya;

printf("WAKTU PANGGILAN AWAL \n ");

printf("masukan waktu memulai panggilan(jam) :",jamA);

scanf("%i",&jamA);

printf("masukan waktu memulai panggilan(menit) :",menitA);

scanf("%i",&menitA);

printf("masukan waktu memulai panggilan(detik) :",detikA);

scanf("%i",&detikA);

printf("\n");

printf("WAKTU PANGGILAN AKHIR \n ");

printf("masukan waktu mengakhiri panggilan(jam) :",jamB);

scanf("%i",&jamB);

printf("masukan waktu mengakhiri panggilan(menit) :",menitB);

scanf("%i",&menitB);

printf("masukan waktu mengakhiri panggilan(detik) :",detikB);

scanf("%i",&detikB);

printf("\n");

waktuA= (jamA*3600)+(menitA*60)+ detikA;

waktuB= (jamB*3600)+(menitB*60)+ detikB;

detik = waktuB-waktuA;

biaya = (detik/30)*700;

printf("Lama waktu bicara anda adalah %d jam %d menit %d detik \n",(jamB-jamA),(menitB-menitA),(detikB-detikA));

printf("jadi biaya yang harus dikeluarkan adalah :%i \n",biaya);

system("pause");

return 0;

}

6. Kalkulator.

#include<stdio.h>

#include<string.h>

int main(){

char menu [3];

int pertama, kedua, hasil;

printf("=========================================\n");

printf("Selamat Datang di Program Kalkulator Saya\n");

printf("=========================================\n\n");

printf("=============================\n");

printf("Nama \t: Raka Dwi Aprian\n");

printf("NIM \t: 1205990\n");

printf("=============================\n\n");

printf("Mulai Menjalankan Kalkulator\n");

menu:

printf("====================\n");

printf(" +. Pertambahan\n");

printf(" -. Pengurangan\n");

printf(" *. Perkalian\n");

printf(" /. Pembagian\n");

printf(" ^. Pemangkatan\n");

printf(" #. Exit \n");

printf("====================\n");

printf("-------------->>> Silakan input pilihan anda \t ?");

scanf("%s",menu);

if (strcmp(menu,"+")==0)

{

system("cls");

printf("Pertambahan ( + ) \n");

printf ("Input angka Pertama\t:");

scanf ("%d",&pertama);

printf ("\n");

printf ("Input angka kedua\t:");

scanf ("%d",&kedua);

printf(" . . Loading . .\n");

hasil=pertama+kedua;

system ("pause");

printf ("\n");

printf ("Jadi Hasil Penghitunganya adalah : %d+%d= %d\n", pertama, kedua, hasil);

}

if (strcmp(menu,"-")==0)

{

system("cls");

printf("Pengurangan ( - ) \n");

printf ("Input angka Pertama\t:");

scanf ("%d",&pertama);

printf ("\n");

printf ("Input angka kedua\t:");

scanf ("%d",&kedua);

printf(" . . Loading . .\n");

hasil=pertama-kedua;

system ("pause");

printf ("\n");

printf ("Jadi Hasil Penghitunganya adalah : %d-%d= %d\n", pertama, kedua, hasil);

}

if (strcmp(menu,"*")==0)

{

system("cls");

printf("Perkalian ( * ) \n");

printf ("Input angka Pertama\t:");

scanf ("%d",&pertama);

printf ("\n");

printf ("Input angka kedua\t:");

scanf ("%d",&kedua);

printf(" . . Loading . .\n");

hasil=pertama*kedua;

system ("pause");

printf ("\n");

printf ("Jadi Hasil Penghitunganya adalah : %d*%d= %d\n", pertama, kedua, hasil);

}

if (strcmp(menu,"/")==0)

{

system("cls");

printf("Pembagian ( / ) \n");

printf ("Input angka Pertama\t:");

scanf ("%d",&pertama);

printf ("\n");

printf ("Input angka kedua\t:");

scanf ("%d",&kedua);

printf(" . . Loading . .\n");

hasil=pertama/kedua;

system ("pause");

printf ("\n");

printf ("Jadi Hasil Penghitunganya adalah : %d/%d= %d\n", pertama, kedua, hasil);

}

if (strcmp(menu,"^")==0)

{

system("cls");

printf("Pemangkatan ( ^ ) \n");

printf ("Input angka Pertama\t:");

scanf ("%d",&pertama);

printf ("\n");

printf ("Input angka kedua\t:");

scanf ("%d",&kedua);

printf(" . . Loading . .\n");

hasil= pow(pertama,kedua);

system ("pause");

printf ("\n");

printf ("Jadi Hasil Penghitunganya adalah : (%d^%d)= %d\n", pertama, kedua, hasil);

}

if (strcmp(menu,"#")==0)

{

return 0;

}

system("pause");

system("cls");

goto menu

SEARCHING

SEARCHING (Sequential Search dan Binarry Search)

Searching adalah metode pencarian informasi dalam suatu aplikasi, dengan suatu kunci( key ). Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui. Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut table.

Pada metode searching (pencarian) ada 2 teknik yang digunakan yaitu :

a. Pencarian sekuensial (sequential search)

b. Pencarian biner (Binary search).

a. Sequential Search

Pencarian sekuensial (sequential search) atau sering disebut pencarian linier menggunakan prinsip sebagai berikut : data yang ada di bandingkan satu persatu secara berurutan dengan yang dicari. Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap perulangan , di bandingkan data ke-i dengan yang dicari. Apabila sama , berarti data telah ditemukan . Sebaliknya apabila sampai akhir pengulangan , tidak ada yang sama berarti data tidak ada.

Pencarian Sekuensial memiliki beberapa kelebihan dan kekurangan yaitu :

1. Kelebihannya :

Relatif lebih cepat dan efisien untuk data yang terbatas
Algoritma sederhana

2. Kekuranganya :

Kurang cepat untuk data dalam jumlah besa
Beban komputasi cenderung lebih besar

CONTOH PROGRAM PADA C++

#include <stdio.h>
#include <iostream.h>
#include <conio.h>

main()
{
int n,i,posisi,x,temu;
int a[5];
printf("Pencarian data dengan sequential search \n\n");
printf("Banyak data : ");
scanf("%d",&n);

for(i=0;i<n;i++)
{
printf("Masukan bilangan : ");
scanf("%d",&a[i]);
}
printf("Data yang akan dicari : ");
scanf("%d",&x);
temu=0;
i=0;
while((temu == 0)&&(i<n))
{
if(a[i]==x)
{
temu=1;
posisi=i;
}
else
i=i+1;
}
if(temu==1)
printf("%d Ditemukan pada posisi %d\n",x,posisi+1);
else
printf("%d Tidak ditemukan \n",x);
getch();
}

HASIL

b. Binarry Search

Binary search adalah sebuah algoritma pencarian dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian untuk menemukan nilai tertentu dalam sebuah larik (array) linear. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. Pencarian Biner (Binary Search) dilakukan untuk :

a) Memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

b) Beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah.

c) Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

d) Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut.

Langkah dalam pencarian biner adalah :

1. Mula-mula diambil dari posisi awal=1 dan posisi akhir = n

2. Kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) div 2

3. Kemudian data yang di cari dibandingkan dengan data tengah

a. Jika sama, data ditemukan, Proses selesai

b. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1

c. Jika lebih besar , proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.

4. Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.

5. Pencarian biner ini akan berakhir jika data ditemukan posisi awal lebih besar dari pada posisi akhir. Jika posisi awal sudah lebih besar dari posisis akhir berarti data tidak diketemukan.

Pencarian Biner :

a. Kelebihannya :

o Untuk data dalam jumlah besar, waktu searching lebih cepat

o Beban komputasi lebih kecil

b. Kekuranganya :

o Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut )

Contoh Program Binary Search pada Bahasa C++ :

#include <iostream.h>
#include <conio.h>

int data[10]={1,3,4,7,12,25,40,65,78,90};
int binary_search(int cari)
{
int a,b,c;
int n=10;
a=0;
b=n-1;
int ketemu=0;
while (a<=b && ketemu==0)
{
c=(a+b)/2;
if (data[c]==cari)
ketemu=1;
else
if(cari<data[c])
b=c-1;
else a=c+1;
}
if(ketemu==1) return 1; else return 0;
}

void main()
{
clrscr();
int cari, hasil;
cout<<"masukan data yang ingin di cari= ";
cin>>cari;
hasil = binary_search(cari);
if(hasil==1)
{
cout<<"data ada!"<<endl;
}
else
if(hasil==0)
cout<<"data tidak ada!"<<endl;
getch();
}

referensi : materi dari ppt. teori struktur data/ STIKOM-Bali
Coding dari dosen praktikum struktur data/ STIKOM-Bali/ dengan sedikit perubahan

Cari Blog Ini

Berlian Hendrawan Putra