Pencarian dan Pengurutan Data pada Pemograman

Logika pencarian data dengan algoritma pencarian linier

Algoritma pencarian yang paling sederhana, yaitu metode pencarian linier (pencarian lurus).

Nama lain algoritma linier adalah algoritma pencarian beruntun (sequential search). Pada

dasarnya, algoritma pencarian linier adalah proses membandingkan setiap elemen array satu

persatu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa.

Misalkan, pada sebuah kasus anda ingin menelepon teman, tapi kebetulan lupa dengan

nomor teleponnya. Maka anda pasti membuka buku telepon untuk mencari nomor telepon yang anda inginkan tersebut. Di sis lain, buku telepon anda tidak urut sama sekali, baik dari segi nama yang sesuai urutan huruf abjad, maupun dari nomor telepon. Berarti anda harus mencari satu persatu, halaman demi halaman nomor telepon tersebut sampai akhirnya ditemukan nomor telepon tersebut. Begitulah kira-kita algoritma pencarian linier.

Algoritma pencarian yang paling sederhana adalah metode pencarian linier. Seperti yang

dibahas pada kegiatan sebelumnya, kita akan melakukan pencarian pada sebuah array yang

sudah terdefinisi elemen-elemennya, dan x adalah elemen yang bertipe sama dengan elemen

array A carilah x di dalam array A.

Logika pengurutan data dengan algoritma bubble sort

Definisi Sorting merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen.Pengurutan data dalam struktur data sangat penting untuk data yang bertipe data numerik ataupun karakter. 

Dalam arti bahasa sorting adalah penyortiran atau memilih-milih. Pada struktur data Sorting adalah sebuah metode untuk pengurutan data, misalnya dari data yang terbesar ke data yang terkecil. Dengan cara program yang dibuat harus dapat membandingkan antar data yang di inputkan. Artinya jika ada deretan data, maka data yang pertama akan membandingkan dengan data yang kedua. Jika data yang pertama lebih besar dari pada data yang kedua maka data yang pertama akan bertukar posisi dengan data yang kedua, begitu seterusnya sampai benar-benar data terurut dari yang terbesar hingga yang terkecil.Metode sorting sangat banyak dan berkembang ada Bubble sort, Selection Sort, Insertion sort, Merge sort, Quick sort. Metode-metode ini menggunakan caranya sendiri untuk membandingkan, memeriksa dan menukar posisi data. Namun tidak semua metode sorting ini efektif. Karena metode sorting yang paling efektif adalah ketika metode tersebut dapat melakukan pengurutan data dengan cepat dan tidak memerlukan banyak memori.

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

DEKLARASI ARRAY UNTUK SORTING

Deklarasikan  :

int data[100];

int n;

//untuk jumlah data

Fungsi untuk Tukar 2 Buah Data :

void tukar(int *a,int *b)

{

int t=*a;

*a=*b;

*b=

Pengetian Metode Bubbel Sort dan Metode Selection Sort

1. Pengetian Metode Bubbel Sort

Bubble sort (metode gelembung) adalah metode atau algoritma pengurutan dengan cara melakukan penukaran data dengan tempat disebelahnya jika data sebelum lebih besar dari pada data sesudahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan, atau telah terurut dengan benar. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci atau data akan dengan lambat menggelembung atau membandingan data ke posisinya yang tepat.

Metode ini mudah dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang kita pelajari, metode ini merupakan metode yang paling tidak efisien karena memiliki banyak pertukara sehingga memerlukan pengalokasian memori yang besar untuk menjalankan metode ini.

2. Pengertian Metode Selection Sort

Selection Sort berbeda dengan Bubble sort. Selection Sort pada dasarnya memilih data yang akan diurutkan menjadi dua bagian, yaitu bagaian yang sudah diurutkan dan bagian yang belum di urutkan.

Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan. Metode ini lebih efektif dari pada metode bubble karena tidak memerlukan banyak pertukaran dan pengalokasian memori.

3. Merge Sort

Pengertian Merge Sort adalah algoritma yang dijalankan sebagai akibat dari terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak daftar yang diurutkan sebagai output. Algoritma merge ini disesuaikan untuk mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi algoritma merge yang mempunyai alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga semua data. Hal ini disebabkan algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel.

Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.

Algoritma Merge umumnya memiliki satu set pointer p0..n yang menunjuk suatu posisi di dalam satu set daftar L0..n . Pada awalnya mereka menunjuk item yang pertama pada setiap daftar. Algoritmanya sebagai berikut:

Selama p0..n masih menunjuk data yang di dalam sebagai pengganti pada akhirnya:

1. Melakukan sesuatu dengan data item yang menunjuk daftar mereka masing-masing.

2. Menemukan pointers points untuk item dengan kunci yang paling rendah

4. Quick Sort

Pengerian Quick Sort adalah algoritma yang dijalankan sebagai akibat dari terlalu banyaknya daftar yang diurutkan, dengan menghasilkan lebih banyak daftar yang diurutkan sebagai output. Algoritma merge ini disesuaikan untuk mesin drive tape. Penggunaannya dalam akses memori acak besar yang terkait telah menurun, karena banyak aplikasi algoritma merge yang mempunyai alternatif lebih cepat ketika kamu memiliki akses memori acak yang menjaga semua data. Hal ini disebabkan algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel.

Algoritma merge sort membagi tabel menjadi dua tabel yang sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut. Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan.

Algoritma Merge umumnya memiliki satu set pointer p0..n yang menunjuk suatu posisi di dalam satu set daftar L0..n . Pada awalnya mereka menunjuk item yang pertama pada setiap daftar. Algoritmanya sebagai berikut:

Selama p0..n masih menunjuk data yang di dalam sebagai pengganti pada akhirnya:

1. Melakukan sesuatu dengan data item yang menunjuk daftar mereka masing-masing.

2. Menemukan pointers points untuk item dengan kunci yang paling rendah; membantu salah satu pointer untuk item yang berikutnya dalam daftar.

Pada umumnya algoritma merge berjalan dalam waktu proposional untuk penjumlahan pada panjangnya daftar; Algoritma merge beroperasi pada bilangan besar dalam daftar yang akan segera mengalikan penjumlahan panjangnya daftar pada saat itu untuk keluaran gambar pointers points yang mana menunjuk pada item yang paling rendah, yang dapat terpengaruhi dengan suatu heap(tumpukan) yang didasarkan prioritas antrian dalam O(lg n) waktu, untuk O(m lg n) waktu (dimana n adalah bilangan pada daftar yang digabungkan, m adalah penjumlahan panjangnya daftar, dan lg adalah log basis 2). Ketika menggabungkan panjang m dua daftar, terdapat suatu perbandingan lompatan yang lebih rendah 2m-1 yang ada dalam kasus terburuk.

Algoritma Bubble SortAda N panjang elemen data terdiri atas T1, T2, T3,…Tn-1, Tn, maka :

• Lakukan traversal untuk membandingkan dua elemen berdekatan. Traversal dilakukan dari belakang
• Jika elemen pada Tn-1> Tn, maka lakukan pertukaran (swap). Jika tidak lanjutkan ke prosestraversal berikutnya sampai bertemu dengan bagian struktur data yang telah diurutkan
• Ulangi langkah di atas untuk struktur data yang tersisa.Atau bisa dijelaskan sbb:Ada N elemen data terdiri atas T1, T2, T3,…Tn-1,Tn, maka untuk ascending :
• Ambil TN-bandingkan TN dengan TN-1

*jika TN < TN-1 maka dipindahkan isi TN = TN-1 dan isi TN-1 = TN

*jika TN > TN-1 maka tetap tidak ada perubahan isi-ambil TN-1-bandingkan TN-1 dengan TN-2

*jika TN-1 < TN-2 maka dipindahkan isi TN-1 = TN-2 dan isi TN-2=TN-1

*jika TN-1 > TN-2 maka tidak ada perubahan isi-ambil TN-2-bandingkan TN-2 dengan TN 3

*jika TN-2 < TN-3 maka dipindahkan isi TN-2 = TN-3 dan isi TN-3=TN-2

*jika TN-2 > TN-3 maka tetap tidak ada perubahan isi

• Lakukan kembali pengambilan TN-3, dan lakukan pembandingan sampai N-1 kali
• Kemudian ulangi dari TN-1 sampai N-2, N-3 dst.

Logika pengurutan data dengan algoritma selection sort

Algoritma Selection Sort adalah algoritma pengurutan dengan cara mencari nilai elemen yang terbesar atau yang terkecil dari sekumpulan elemen nilai pada sebuah data.

Logika Pengurutan Selection Sort sebagai berikut :

1. Mencari nilai elemen max atau min (terserah, atau pilih salah satu) pada semua nilai elemen pada array yang seharusnya (minimal pada pertama atau nilai max pada akhir). kemudian elemen array tersebut di tetapkan atau di isolasi dan tidak di ganggu lagi.

2. Temukan sebuah elemen array yang memilikidi nilai kecil atau besardari index kedua dari elemen awal jika terkecil atau dari akhir jika terbesar, setelah itu tukarkan eleman tersebut dengan elemen array pada posisi (indeks) kedua (dari awal atau dari akhir tergantung penggunaan untuk mencari nilai terkecil atau dari yang terbesar), kemudian isolasi atau tetapkan elemen array tersebut ditambah dengan elemen array yang sebelumnya.

3. Lakukan langkah seperti  diatas pada elemen berikutnya sampai elemen terakhir.

Selection Sort diakui karena kesederhanaan algoritmanya dan performanya lebih bagus daripada algoritma lain yang lebih rumit dalam situasi tertentu. Algoritma ini bekerja sebagai berikut:

1. Mencari nilai minimum (jika ascending) atau maksimum (jika descending) dalam sebuah list

2. Menukarkan nilai ini dengan elemen pertama list

3. Mengulangi langkah di atas untuk sisa list dengan dimulai pada posisi kedua

Secara efisien kita membagi list menjadi dua bagian yaitu bagian yang sudah diurutkan, yang didapat dengan membangun dari kiri ke kanan dan dilakukan pada saat awal, dan bagian list yang elemennya akan diurutkan.