MAKALAH
SORTING (PENGURUTAN)
& SEARCHING (PENCARIAN)
DISUSUN OLEH :
NAMA
: EMIL HARDIANSYAH
STAMBUK
: F55116086
PROGRAM STUDI S1 TEKNIK
INFORMATIKA
JURUSAN TEKNOLOGI
INFORMASI
FAKULTAS TEKNIK
UNIVERSITAS TADULAKO
2017
KATA PENGANTAR
Puji dan syukur penulis panjatkan kehadirat Allah
SWT karena dengan rahmat dan hidayah-Nya
sehingga penulis dapat membuat makalah dengan judul ”SORTING
& SEARCHING”.
Makalah ini
bertujuan untuk memenuhi tugas mata kuliah STRUKTUR DATA yang diberikan oleh
Dosen mata kuliah yang bersangkutan.
Pada kesempatan ini
penulis tak lupa mengucapkan terima kasih kepada semua pihak khususnya kepada
asisten mata kuliah Struktur Data dan rekan-rekan yang telah membantu dalam proses penyelesaian
makalah ini.
Akhirnya, dengan segala kerendahan hati
penulis sampaikan bahwa setiap manusia tidak luput dari kesalahan dan
kekhilafan. Oleh karena itu, penulis senantiasa mengharapkan kritik dan saran
yang konstruktif sehingga penulis dapat berkarya yang lebih baik lagi pada masa
yang akan datang.
Semoga bermanfaat
Palu,
13 Mei 2017
DAFTAR ISI
KATA PENGANTAR............................................................................................ i
DAFTAR ISI........................................................................................................... ii
BAB I PENDAHULUAN.................................................................................... 1
1.1 Latar Belakang.................................................................................... 1
1.2 Rumusan Masalah................................................................................ 3
1.3 Tujuan.................................................................................................. 3
BAB II LANDASAN TEORI................................................................................. 6
2.1 Landasan Teori Sorting....................................................................... 6
2.2 Landasan Teori Searching................................................................... 7
BAB III PEMBAHASAN.................................................................................... 11
3.1 Sorting............................................................................................... 11
3.2 Searching........................................................................................... 19
BAB IV PENUTUP.............................................................................................. 25
4.1 Kesimpulan....................................................................................... 25
4.2 Saran ................................................................................................ 25
DAFTAR PUSTAKA........................................................................................... 26
BAB I
PENDAHULUAN
1.1 Latar
Belakang
Algoritma merupakan kumpulan perintah yang memiliki daya guna yang sangat
besar bagi masyarakat. Algoritma biasanya digunakan sebagai kumpulan perintah
untuk menyelesaikan suatu masalah. Algoritma ini memiliki aplikasi yang
bermacam-macam dalam setiap masalah yang ada. Contohnya saja adalah algoritma
cara menyelesaikan suatu aritmatika yang rumit, algoritma untuk menghitung luas
penampang dari suatu kabel, atau bahkan untuk menghitung bayaran parkir di
setiap mal. Salah satu aplikasi bentuk pemrograman ini adalah dalam bahasa
permrograman yang disebut bahasa C. Dimana bahasa C ini memiliki suatu
aturan-aturan tertentu yang sangat penting sehingga dalam penggunaanya kita
harus memperhatikan cara menggunakan aturan tersebut. Salah satu cara
penggunaannya adalah dengan array. Dimana array ini merupakan suatu data
struktur yang berkoneksi satu sama lain dengan tipe yang sama. Aplikasi array
ini banyak sekali, contohnya saja adalah menghitung golongan dari umur yang
berjumlah 25 tahun hingga 55 tahun. Array ini juga bisa digunakan untuk mencari
suatu elemen nilai dalam suatu struktur data, selain itu array ini juga bisa
digunakan untuk mengurutkan data-data yang tidak berurutan. Hal –hal yang telah
disebutkan disebut sebagai searching array dan sorting array.
Sorting array merupakan salah satu aplikasi yang paling penting dalam
suatu sistem aplikasi perhitungan data. Biasanya suatu bank memiliki komputasi
sorting array yang sudah biasa digunakan dalam aplikasinya sehari-hari. Bahkan
telephone juga mengurutkan suatu list yang terdiri dari nama akhir , nama awal
agar bisa memudahkan dalam perhitungan dalam mencari nomor telephone.
Searching array juga memiliki tak kalah pentingnya dibandingkan dengan
sorting array. Pada searcing array kita biasa menggunakannya pada data yang
sangat banyak. Sehingga sangat sulit bila kita ingin mencari suatu data atau
suatu angka didalamnya satu per satu. Aplikasi searching array memudahkan kita
dalam mencari suatu data atau angka yang kita inginkan dengan hanya memasukkan
nilai input pada suatu data yang disikan.
1.2
Rumusan Masalah
Timbulnya masalah akibat sulitnya pekerjaan yang
dilaksanakan secara manual pada masyarakat menyebabkan adanya pemborosan waktu,
tenaga, dan pikiran. Pemborosan –pemborosan ini menyebabkan kerugian pada
masyarakat itu sendiri bahkan secara akumulatif jika kerugian pada tiap
individu dijumlahkan, maka dampaknya akan menjadi kerugian sebuah negara,
bahkan secara lebih luas dapat berdampak pada kerugian global. Sebagai
alternatif, suatu sistem algoritma mengatasi permasalahan tersebut dengan
searching dan sorting array.
1.3
Tujuan dan Manfaat
Makalah
ini disusun untuk memaparkan tentang pengertian sorting dan searching array
dalam aplikasi di dunia kerja. Dengan membaca makalah ini, pembaca akan
mengetahui lebih dalam mengenai membuat algoritma dari searching dan sorting
array yang bisa dijadikan sebagai referensi dalam pembuatan algoritma. Selain
itu, pembaca juga akan mengetahui manfaat dari searching dan sorting array
dalam aplikasinya didunia kerja.
BAB
II
LANDASAN
TEORI
2.1 Landasan Teori Sorting
Data dalam struktur data sangat penting untuk data yang bertipe data
numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut
naik) dan descending (urut turun) Pengurutan (Sorting) adalah proses menyusun
kembali data yangsebelumnya telah disusun dengan suatu pola tertentu, sehingga
tersusun secara teratur menurut aturan tertentu.
Contoh:
Data Acak : 5 6 8 1 3 25 10
Ascending : 1 3 5 6 8 10 25
Descending : 25 10 8 6 5 3 1
2.1.1 Bubble Sort
Sorting yang termudah. Diberi nama “Bubble” karena
proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang
tepat, seperti gelembung yangkeluar dari sebuah gelas bersoda. Bubble Sort
mengurutkan data dengan caramembandingkan elemen sekarang dengan elemen
berikutnya. Pengurutan Ascending : Jika elemen sekarang lebih besar dari elemen
berikutnya maka kedua elemen tersebutditukar. Pengurutan Descending: Jika
elemen sekarang lebih kecil dari elemen berikutnya , maka kedua elemen tersebut
ditukar. Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke
kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses
telah selesai, maka bubble sorta akan mengulangi proses, demikian seterusnya
dari 0 sampai dengan iterasi sebanyak n-1Kapan berhentinya? Bubble sort
berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang
bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
2.1.2 Selection Sort
Merupakan kombinasi antara sorting dan searching
• Untuk setiap proses, akan dicari elemen-elemen
yang belum diurutkan yang memiliki nilai terkecil
atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.
• Misalnya untuk putaran pertama, akan dicari data
dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil
(data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan
ditempatkan di indeks kedua (data[1]).
• Selama proses, pembandingan dan pengubahan hanya
dilakukan pada indeks pembanding saja, pertukaran data
secara fisik terjadi pada akhir proses.
2.1.3 Insertion Sort
• Mirip dengan cara orang mengurutkan kartu,
selembar demi selembar kartu diambil dan disisipkan
(insert) ke tempat yang seharusnya.
• Pengurutan dimulai dari data ke-2 sampai dengan
data terakhir, jika ditemukan data yang lebih
kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya.
• Pada penyisipan elemen, maka elemen-elemen lain
akan bergeser ke belakang
2.2 Landasan Teori Searching
Searching adalah cara pencarian
data dengan menelusuri kembali data-data tersebut. Data yang dicari dapat
berupa array dalam memory atau bisa juga pada file di external storage.
Searching sendiri dapat dibagi menjadi 3 bagian.
1. Sequential Search
2. Binary SearchPenjelasan dari kedua jenis searching tersebut adalah sbb:
Searching sendiri dapat dibagi menjadi 3 bagian.
1. Sequential Search
2. Binary SearchPenjelasan dari kedua jenis searching tersebut adalah sbb:
2.2.1
Sequential
Search
Sequential search adalah suatu cara pencarian data dalam array 1 dimensi. Data yang dicari akan ditelusuri dalam semua elemen-elemen aray dari awal sampai akhir, dan data tersebut tidak perlu diurutkan terlebih dahulu.
Dalam sequential search terdapat 2 kemungkinan yang akan terjadi dalam waktu pencarian data, yaitu :
– kemungkinan terbaik (best case)
hal ini terjadi jika data yang dicari terletak pada indeks array terdepan, sehingga waktu yang dibutuhkan untuk mencari data sedikit.
– kemungkinan terburuk (worst case)
hal ini terjadi jika data yang dicari terletak pada indeks array terakhir, sehingga waktu yang dibutuhkan untuk mencari data sangat lama.
Dalam pencarian data menggunakan sequential search, peningkatan efisiensi pencarian dapat dilakukan dengan cara menghentikan looping apabila data yang dicari sudah ketemu dengan menggunakan BREAK.
Sequential search adalah suatu cara pencarian data dalam array 1 dimensi. Data yang dicari akan ditelusuri dalam semua elemen-elemen aray dari awal sampai akhir, dan data tersebut tidak perlu diurutkan terlebih dahulu.
Dalam sequential search terdapat 2 kemungkinan yang akan terjadi dalam waktu pencarian data, yaitu :
– kemungkinan terbaik (best case)
hal ini terjadi jika data yang dicari terletak pada indeks array terdepan, sehingga waktu yang dibutuhkan untuk mencari data sedikit.
– kemungkinan terburuk (worst case)
hal ini terjadi jika data yang dicari terletak pada indeks array terakhir, sehingga waktu yang dibutuhkan untuk mencari data sangat lama.
Dalam pencarian data menggunakan sequential search, peningkatan efisiensi pencarian dapat dilakukan dengan cara menghentikan looping apabila data yang dicari sudah ketemu dengan menggunakan BREAK.
Disebut juga sebagai metode
pencarian urut adalah metode pencarian yang paling mudah. Bayangkan saja jika
anda dihadapkan pada sebuah rak buku, dan anda diberi tugas untuk mencari
sebuah buku dari rak tersebut. Sudah tentu anda akan mulai mencarinya satu –
persatu entah itu dari atas atau dari bawah sampai buku yang dimaksud ketemu.
Singkatnya sequential search memiliki proses sebagai berikut:
• Tentukan banyaknya data yang akan di olah, missal banyak data adalah N.
• Tentukan data apa yang akan dicari, missal data yang akan dicari adalah C.
• Deklarasikan sebuah counter untuk menghitung banyak data yang ditemukan, missal counternya adalah K.
• Inisialisasikan K =0
• Lakukanlah perulangan sebanyak N kali
• Dalam tiap proses perulangan tersebut periksalah apakah data yang sedang
diolah sama dengan data yang dicari.
• Jika ternyata sama K=K+1
• Jika tidak, lanjutkan proses perulangan .
• Setelah proses perulangan berhenti, periksalah nilai K.
• Jika nilai K lebih dari 0, artinya data yang dicari ada dalam data /array dan tampilkan nilai K ke layer sebagai jumlah data yang ditemukan.
• Jika nilai K=0, artinya data yang dicari tidak ditemukan dalam data / array dan tampilkan ke layar bahwa data tidak ditemukan
• Proses selesai.
Singkatnya sequential search memiliki proses sebagai berikut:
• Tentukan banyaknya data yang akan di olah, missal banyak data adalah N.
• Tentukan data apa yang akan dicari, missal data yang akan dicari adalah C.
• Deklarasikan sebuah counter untuk menghitung banyak data yang ditemukan, missal counternya adalah K.
• Inisialisasikan K =0
• Lakukanlah perulangan sebanyak N kali
• Dalam tiap proses perulangan tersebut periksalah apakah data yang sedang
diolah sama dengan data yang dicari.
• Jika ternyata sama K=K+1
• Jika tidak, lanjutkan proses perulangan .
• Setelah proses perulangan berhenti, periksalah nilai K.
• Jika nilai K lebih dari 0, artinya data yang dicari ada dalam data /array dan tampilkan nilai K ke layer sebagai jumlah data yang ditemukan.
• Jika nilai K=0, artinya data yang dicari tidak ditemukan dalam data / array dan tampilkan ke layar bahwa data tidak ditemukan
• Proses selesai.
Dapat disimpulkan bahwa
sequential search, akan mencari data dengan cara membandingkannya satu-persatu
dengan data yang ada. Prosesnya tentu saja akan singkat jika data yang diolah
sedikit, dan akan lama jika data yang diolah banyak. Disarankan proses ini
digunakan pada jumlah data yang sedikit saja.
2.2.2
Binary
Search
Binary search adalah teknik pencarian data dengan cari membagi dua data setiap kali proses pengurutan.
Cara pencarian biner :
– data diambil dari posisi 1 sampai posisi N
– lalu cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
– kemudian data yang dicari dibandingkan dengan data tengah, apakah data itu lebih besar atau lebih kecil.
– Jika lebih besar, maka (posisi awal = posisi tengah + 1)
– Jika lebih kecil, maka (posisi akhir = posisi tengah – 1)
– Jika data yang dicari = data tengah, maka “KETEMU”.
CONTOH DAN CARA KERJA BINARY SEARCH
Di bawah ini adalah kunci–kunci carilah kunci 39 dengan mengunakan algorithm Binary Search.
[13, 16, 18, 27, 28, 29, 38, 39, 53].
1 2 3 4 5 6 7 8 9
File ini dinamakan File Sequential (secara berurutan).
Cara penyelesaian.
Bila di cari kunci 39 maka ;
Bila terendah = 1, dan tertinggi = 9,
maka 1 + 9 = 10 , lalu 10 / 2 = 5.
1. Nomor urut 5, adalah kunci 28 , tapi 28 < 39,
[13, 16, 18, 27, 28, 29, 38, 39, 53].
maka terendah = 5 , dan tertinggi = 9,
maka : 5 + 9 = 14
14 / 2 = 7.
2. Nomor urut 7 adalah 38 , tapi 38 8,5 ≈ 8
3. Nomor urut 8 adalah kunci 39 , dimana kunci 39 = 39.
[13, 16, 18, 27, 28, 29, 38, 39, 53]
Binary search adalah teknik pencarian data dengan cari membagi dua data setiap kali proses pengurutan.
Cara pencarian biner :
– data diambil dari posisi 1 sampai posisi N
– lalu cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
– kemudian data yang dicari dibandingkan dengan data tengah, apakah data itu lebih besar atau lebih kecil.
– Jika lebih besar, maka (posisi awal = posisi tengah + 1)
– Jika lebih kecil, maka (posisi akhir = posisi tengah – 1)
– Jika data yang dicari = data tengah, maka “KETEMU”.
CONTOH DAN CARA KERJA BINARY SEARCH
Di bawah ini adalah kunci–kunci carilah kunci 39 dengan mengunakan algorithm Binary Search.
[13, 16, 18, 27, 28, 29, 38, 39, 53].
1 2 3 4 5 6 7 8 9
File ini dinamakan File Sequential (secara berurutan).
Cara penyelesaian.
Bila di cari kunci 39 maka ;
Bila terendah = 1, dan tertinggi = 9,
maka 1 + 9 = 10 , lalu 10 / 2 = 5.
1. Nomor urut 5, adalah kunci 28 , tapi 28 < 39,
[13, 16, 18, 27, 28, 29, 38, 39, 53].
maka terendah = 5 , dan tertinggi = 9,
maka : 5 + 9 = 14
14 / 2 = 7.
2. Nomor urut 7 adalah 38 , tapi 38 8,5 ≈ 8
3. Nomor urut 8 adalah kunci 39 , dimana kunci 39 = 39.
[13, 16, 18, 27, 28, 29, 38, 39, 53]
BAB III
PEMBAHASAN
3.1 Sorting
3.1.1
Insertion Sort
Salah
satu algoritma sorting yang paling sederhana adalah insertion sort.
Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan
berikut ini menerangkan bagaimana algoritma insertion sort bekerja
dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari
kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu
diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri
ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua,
dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak
pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu
kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua,
kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut
akan berlangsung hingga seluruh kartu pada meja pertama telah diletakkan
berurutan pada meja kedua. Algoritma insertion sort pada dasarnya
memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja
pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari
bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada
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.
Algoritmanya :
void insertionSort(Object array[], int startIdx, int endIdx) {
for (int i = startIdx; i < endIdx; i++) {
int k = i;
for (int j = i + 1; j < endIdx; j++) {
if(((Comparable) array[k]).compareTo(array[j])>0) {
k = j;
}
}
swap(array[i],array[k]);
}
}
3.1.2
Selection Sort
Jika anda diminta untuk membuat algoritma sorting tersendiri,
anda mungkin akan menemukan sebuah algoritma yang mirip dengan selection
sort. Layaknya insertion sort, algoritma ini sangat rapat
dan mudah untuk diimplementasikan. Mari kita kembali menelusuri bagaimana
algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu
tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut
akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas
ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu
ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu
dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan kartu
yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah –
langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan
dapat digeser dengan kartu yang bernilai lebih rendah.
Ide utama dari
algoritma selection sort adalah memilih elemen dengan nilai paling
rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari
i dimulai dari 1 ke n, dimana n adalah jumlah total
elemen dikurangi 1.
Algoritmanya :
void selectionSort(Object array[], int
startIdx, int endIdx) {
int min;
for (int i = startIdx; i <
endIdx; i++) {
min = i;
for (int j = i + 1; j <
endIdx; j++) {
if ((( Comparable ) array [min] ) . compareTo (array[j])>0) {
min = j;
}
}
swap(array[min], array[i]);
}
}
3.1.3
Merge Sort
Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan
permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian
solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.
Pada setiap
tingkatan rekursi, pola tersebut terdiri atas 3 langkah.
1. Divide
Memilah masalah menjadi sub masalah.
2. Conquer
Selesaikan
sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup ringkas
dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif.
3. Kombinasi
Mengkombinasikan
solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas
permasalahan utama.
Seperti yang
telah dijelaskan sebelumnya, Merge sort menggunakan pola divide
and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3
langkah berpola divide-and-conquer.
Berikut menjelaskan langkah kerja dari Merge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer
setiap bagian dengan memanggil prosedur merge sort secara rekursif.
3. Kombinasi
Mengkombinasikan
dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Proses rekursi
berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan
diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut
menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Algoritmanya :
void
mergeSort(Object array[], int startIdx, int endIdx) {
if
(array.length != 1) {
//Membagi
rangkaian data, rightArr dan leftArr
mergeSort(leftArr,
startIdx, midIdx);
mergeSort(rightArr,
midIdx+1, endIdx);
combine(leftArr,
rightArr);
}
}
Diagram Merge Sort
3.1.4
Quick Sort
Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge
sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda
dengan merge sort, algoritma ini hanya mengikuti langkah – langkah
sebagai berikut:
1. Divide
Memilah
rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap
elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada
A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut
sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian
dari prosedur pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif
Pada
algoritma quicksort, langkah “kombinasi” tidak di lakukan karena telah
terjadi pengurutan elemen – elemen pada sub-array
Algoritmanya
:
void
quickSort(Object array[], int leftIdx, int rightIdx) {
int
pivotIdx;
/*
Kondisi Terminasi */
if (rightIdx > leftIdx) {
pivotIdx
= partition(array, leftIdx, rightIdx);
quickSort(array, leftIdx, pivotIdx-1);
quickSort(array, pivotIdx+1, rightIdx);
}
}
Diagram Quick Sort
3.1.5 Bubble
Sort
Bubble Sort merupakan cara pengurutan yang
sederhana. Konsep dari ide dasarnya adalah seperti “gelembung air” untuk elemen
struktur data yang semestinya berada pada posisi awal.
Cara kerjanya adalah dengan berulang-ulang melakukan traversal (proses looping) terhadap elemen-elemen struktur datayang belum diurutkan. Di dalam traversal tersebut, nilai dari dua elemen struktur data dibandingkan. Jikaternyata urutannya tidak sesuai dengan “pesanan”,maka dilakukan pertukaran (swap).
Cara kerjanya adalah dengan berulang-ulang melakukan traversal (proses looping) terhadap elemen-elemen struktur datayang belum diurutkan. Di dalam traversal tersebut, nilai dari dua elemen struktur data dibandingkan. Jikaternyata urutannya tidak sesuai dengan “pesanan”,maka dilakukan pertukaran (swap).
3.2 Searching
3.2.1
Linear Searching
Algoritma pencarian secara linear adalah algoritma untuk mencari sebuah
nilai pada table sambarang dengan cara melakukan pass atau transversal.
Transversal dari awal sampai akhir table. Ada dua macam cara pencarian pada
table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean dan tanpa
Boolean.
void SeqSearch1 (int T[], int
Nmax,
int value, int *idx){/*kamus
lokal*/
int
i;/*Algoritma*/
i = 1;
while
((i<Nmax) && (T[i] != value)){
i = i + 1;
}
if (T[i]==value){
*idx = i;
}
else{
*idx = 0;
}
}
Algoritma di
atas melakukan pengulangan sampai i sama dengan Nmax (ukuran tabel) atau harga
value dalam tabel sudah ditemukan. Kemudian harga i
di-assign ke dalam variable idx. Elemen terakhir diperiksa secara khusus.
void SeqSearch2 (int T[],int
Nmax,
int value, int *idx){
int i;
boolean found;/*algoritma*/
i = 1;
found = false;
while
((i<=Nmax) && (!found)){
if (T[i] == value){
found = true;
}
else{
i = i + 1;
}
}
if (found){
*idx = i;
}
else{
*idx = 0;
}
3.2.2
Binary Searching
Algoritma pencairan secara linear melakukan pengulangan sebanyak 1 kali
untuk kasus terbaik (value sama dengan elemen pertama dalam tabel) dan Nmax
kali untuk kasus terburuk. Sehingga algoritma ini mempunyai kompleksitas
algoritma O(n).
Implementasi
algoritma pencarian biner dalam bahasa C adalah sebagai berikut.
void BinSearch (int T[],int Nmax,
int value, int*
idx)
int i,j,mid;
boolean found;$
/*algoritma*/
found = false;
i = 1;
j = Nmax;
while ((!found) &&
(i<=j)){
mid = (i+j) div 2;
if (T[mid] == value){
found = true;
}
else{
if (T[mid]<value)
{
i = mid + 1;
}
else{
j = mid – 1;
}
}
}
if (found){
*idx = mid;
}
else{
*idx = 0;
}
}
Algoritma
pencarian biner adalah algoritma untuk mencari sebuah nilai pada tabel teurut
dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini
mencari nilai yang dicari dengan tiga langkah yaitu :
• Mencari nilai
tengah dari tabel (median)
• Melakukan perbandingan nilai tengah dengan nilai
yang dicari untuk menentukan apakah nilai yang dicari ada pada sebelum atau setelah
nilai tengah
• Mencari
setengah sisanya dengan cara yang sama.
BAB IV
PENUTUP
4.1
Kesimpulan
Berdasarkan
uraian bahasan “jenis-jenis algoritma searching dan sorting” dapat disimpulkan
bahwa :
1.
Terdapat
banyak algoritma searching dan sorting yang bias programmer gunakan sehingga
dapat digunakan dalam situasi dan kondisi masalah tertentu.
2.
Pembuat
algoritma baru dirasakan sangat penting Karena setiap masalah akan memerlukan
teknik sorting dan searching yang baik dan sesuai.
4.2 Saran
Adapun
saran-saran yang dapat penulis sampaikan dalam hal ini adalah sebagai berikut :
1.
Semoga pembaca dapat memahami dan
mengerti tentang algoritma searching dan sorting yang dijelaskan
2.
Dengan adanya makalah ini,
diharapkan pembaca mendapat informasi terbaru tentang algoritma-algoritma
sorting dan searching.
3.
Semoga dengan membaca makalah
ini, pembaca mendapat inspirasi-inspirasi terbaru yang berguna dalam pembuatan
algoritma-algoritma lainnya
4.
Dalam kesempatan-kesempatan
berikutnya sebaiknya ditambahkan kemungkinan algoritma-algoritma baru sehingga
ke depannya akan didapt lebih banyak algoritma yang lebih efisien dan efektif
DAFTAR PUSTAKA
2 komentar
Tulis komentarthanks min
Replysangat membantu dan terima kasih
Reply