Pencarian dan Pengurutan Data

1. Tujuan:Mempelajari bagaimana mengatur sekumpulandata berdasar pada pengurutan dan pencarian STRUKTUR DATA
2. Pengurutan adalah upaya mengatursekumpulan data berdasar pada urutan (naik atau turun) Pencarian adalah upayamencari/mendapatkan satu atau lebih objek dari sekumpulan data STRUKTUR DATA
3. 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
4. 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
5. 2 (dua) metode pencarian yang akan dipaparkan Pencarian Pencarian Sekuensial Biner(Sequential Search) (Binary Search) STRUKTUR DATA
6. 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
7. 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
8. 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
9. Bubble Sort (3) STRUKTUR DATA
10. Bubble Sort (4) STRUKTUR DATA
11. Bubble Sort (5) STRUKTUR DATA
12. 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
13. 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
14. Selection Sort (2) STRUKTUR DATA
15. 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
16. Insertion Sort (2) STRUKTUR DATA
17. Insertion Sort (3) STRUKTUR DATA
18. PerbandinganTabel Perbandingan Kecepatan MetodePengurutan DataUntuk data sejumlah 10.000 data padakomputer Pentium II 450 MHz STRUKTUR DATA
19. SoalCarilah 3 metode sorting lainnya dantuliskan dalam paper beserta source code,cara dan analisis dan tiap-tiap metodesorting yang ada! STRUKTUR DATA
20. 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
21. 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
22. 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
23. 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
24. 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
25. 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