SORTING DAN SEARCHING ARRAY


BAB I

PENDAHULUAN

 

  1. Latar Belakang Masalah

    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 Penulisan

    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

METODE PENULISAN

 

2.1.    Metode Penulisan

    Dalam penyusunan karya tulis ini Metode Penulisan yang digunakan adalah penjelasan isi dan studi kepustakaan, dengan kata lain, makalah ini memberikan data-data yang bersifat faktual untuk memperkuat dan mempermudah pemahaman terhadap masalah yang ada serta menperdalam ilmu yang telah diperoleh dan juga memberikan gambaran mengenai cara membuat algoritma dari searching dan sorting. Selain itu, dalam makalah ini metode penulisan yang digunakan adalah memaparkan bentuk pemrograman dalam bahasa C.

 

2.2.    Pengumpulan Data

    Dalam makalah ini, pengumpulan data menggunakan studi kepustakaan, yaitu pengumpulan data-data melalui jurnal ilmiah, buku, riset-riset terdepan, majalah-majalah dan artikel-artikel ilmiah yang bersumber dari internet.

 

2.3.    Sifat dan Bentuk makalah

    Sifat dan bentuk karya tulis ini adalah bersifat deskriptif karena penulis ingin memberikan penjelasan tentang aplikasi searching dan sorting array. Kemudian penulis juga menjelaskan bagaimana suatu aplikasi ini dapat diterima oleh masyarakat sehingga penulis lebih mendeskriptifkan nilai karya tulis ini pada feature pemrogramannya. Sehingga pembaca bisa langsung mengaplikasikan searching dan sorting array ini pada bahasa C

BAB III

PEMBAHASAN

3.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.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.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);

}

}

 


Gambar3.1. Diagram Merge Sort

 

 

 

3.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);

}

}


Gambar 3.2. Diagram Quick Sort

 

3.5    Counting sort

Adalah sebuah algoritma sorting linear yang digunakan untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data yang nilainya kecil.

Algoritma ini diproses dengan mendefinisikan sebuah hubungan urutan antara ‘item’ yang akan disorting. Katakana ‘item’ yang akan disorting adalah variable A. Maka, terdapat sebuah array tambahan dengan ukuran yang serupa dengan array A. katakana array tersebut adalah array B. untuk setiap element di A, sebut e, algoritma ini menyimpan jumlah ‘item’ di A lebih kecil dari atau sama dengan e di B(e). jika hasil sorting yang terakhir disimpan di array C, maka untuk masing-masing e di A, dibuat dalam arah yang sebaliknya, yaitu C[B(e)]=e. setelah step di atas, niali dari B(e) berkurang dengan 1.

Algoritma ini membuat 2 passover A dan passover B. Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan langsung mengabarkan element-element yang muncul pertama kali.

Adapun syarat algoritma ini berjalan dengan baik ialah:

  1. Data harus bilangan bulat yang bernilai lebih besar atau sama dengan nol
  2. Range data diketahui

Ada 3 macam array yang terlibat:

  1. Array untuk mengisi bilangan yang belum diurutkan.
  2. Array untuk mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.
  3. Array untuk mengisi bilangan yang sudah diurutkan.

Algoritmanya :

countingsort(A[], B[], min, max, n)
for i = min to max do
C[i] = 0

for j = 1 to n do
C[A[j]] = C[A[j]] + 1

for i = min + 1 to max do
C[i] = C[i] + C[i-1]

for j = n downto 1 do
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] – 1


Gambar 3.3 Diagram Counting Sort

3.6    Radix Sort

Radix sorting bisa digunakan ketika masing-masing universal element bisa dilihat sebagai sebuah urutan digit (atau huruf atau symbol lainnya). Sebagai contoh, kita bisa membuat masing-masing bilangan bulat antar 0 sampai 99 sebagai sebuah urutan dengan dua digit (seperti “05”). Untuk menyorting sebuah array dari angka 2-digit, algoritma ini membuat dua ‘passing’ sorting melalui array tersebut. Pada ‘passing’ pertama, element array disorting pada least significant decimal digit. Kunci utama dari radix sort adalah pada passing yang kedua. Hasilnya, setelah kedua passing melewati array tersebut, data yang terisi telah disorting.

Algoritmanya :

source

List of bytes

source_n

number of bytes to sort

dest[256]

256 lists of bytes. each list should have enough space to hold source_n elements.

//——————-saving element in memory——————–

int distribution[256]

 

// fill the list with zeros.

 

for i=0 to 255 do

distribution[i]=0;

 

// build a distribution history:

 

for i=0 to source_n do

distribution] = distribution] +1;

endfor

 

// Now we build a index-list for each possible element:

 

int index[256];

index [0]=0;

 

for i=0 to 255 do

index[i]=index[i-1]+distribution[i-1];

endfor

 

//sorting

dest: array of bytes with space for source_n bytes.

 

for i = 0 to source_n do

  dest[index]]=source[i];

  index] = index] +1;

endfor

 

3.7 Searching

 

3.7.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.7.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 bisa 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

 

 


 

3 responses to “SORTING DAN SEARCHING ARRAY

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s