Transcription
PENGURUTAN
Yaitu proses pengaturan sekumpulanobjek menurut urutan atau susunantertentuAcuan pengurutan dibedakan menjadi :1. Ascending / menaikSyarat : L[1]L[2]L[3] L[N] L[N]2. Descending / menurunSyarat : L[1]L[2]L[3]
Pengurutan dibedakan menjadi– Pengurutan Internal / Pengurutan Array Yaitu pengurutan terhadap sekumpulan data yang disimpandalam memori utama komputer Umumnya struktur yang digunakan adalah Array Prosesnya lebih cepat & hasil pengurutan bersifat sementara– Pengurutan eksternal / Pengurutan File Yaitu pengurutan terhadap sekumpulan data yangdisimpan dalam memori sekunder (biasanya bervolumebesar) Struktur yang digunakan adalah File Prosesnya lebih lama tapi hasilnya bersifat tetap
Beberapa teknik pengurutan data yang seringdigunakan Bubble SortSelection SortInsertion SortShell sortQuick sort Heap sortMerge sortRadix sortTree sortBinary sort
Bubble sort Diinspirasi oleh gelembung sabun yang ada dipermukaanair, dimana benda yang berat akan terbenam dan yangringan akan terapung Bila pengurutan dengan acuan ascending : elemen yangbernilai besar akan “dibenamkan” melalui prosespembandingan antar elemen yang bersebelahan dan prosespertukaran– Proses pertukaran dilakukan sebanyak N-1 langkah, dimana Nadalah ukuran array– Pada akhir setiap langkah ke I, array L[1.N] akan terdiri atas duabagian yaitu : Yang sudah terurut Yang belum terurut– Setelah langkah terakhir diperoleh array L[1.N] yang terurutascending
Contoh : diurutkan secara ascending, N 6Lokasi123456Data25271087621Langkah 7*8*762132510827*76*214251082776*21*525108272176
Langkah *27*217631082527*21*76410825212776Langkah *21*2776381021252776
Langkah 252776Langkah 1Lokasi123456Awal8*10*21252776181021252776
Algoritma:DeklarasiI: bilangan bulat {untuk langkah}J: bilangan bulat {indek}Temp : bilangan bulat {untuk penampung sementara}L: Array [1 .N]N: bilangan bulat {jumlah elemen array}DeskripsiFor I(N-1) downto 1 doFor J 1 to I doIf L[J] L [J 1] thenTempL[J]L[J] L[J 1]L[J 1] tempEndifEndforEndfor
Selection sort Yaitu memilih nilai yang maksimum/minimum dari suatuarray yang akan diurutkan dan menempatkannya padaposisi awal atau akhir array; selanjutnya elemen tersebutdiisolasi dan tidak disertakan pada proses berikutnya. Halini dilakukan secara terus menerus sampai sebanyak N-1 Dibedakan menjadi :– Algoritma pengurutan maksimumYaitu memilih elemen maksimum sebagai basis pengurutan–Algoritma pengurutan minimumYaitu memilih elemen minimum sebagai basis pengurutan
Contoh : Diurutkan secara ascending dengan algoritmapengurutan minimumLokasi123456Data25271087621Langkah/ 25*257676767627212127*2776*
Algoritma :Deklarasi :I: bilangan bulat {untuk langkah}J: bilangan bulat {indek}Temp : bilangan bulat {untuk penampung sementara}L: Array [1 .N]N: bilangan bulat {jumlah elemen array}K: Bilangan bulat {menampung indek nilai terkecil}X: Bilangan bulat {menampung nilai terkecil}Deskripsi :For I 1 to (N-1) doK IX L[I]For J ( I 1) to N doIf L[J] X thenK JX L [J]EndifEndforTempL[I]L[I] XL[K] tempEndfor
Insertion sort / Sinking Sort / Sifting Sort Yaitu metode pengurutan dengan caramenyisipkan elemen array pada posisi yang tepat Pada prinsipnya seperti permainan kartu : ambilkartu pertama & pegang, ambil kartu kedua danletakkan pada posisi yang tepat / berurut, ambilkartu ketiga letakkan pada posisi yang berurut(biasa diawal, ditengah atau diakhir) dst
Contoh 3456252510888272510101027252521272725762776
DeklarasiIJketemux: Bilangan bulat {untuk langkah}: Bilangan bulat {untuk penelusuran array}: boolean {untuk menyatakan posisi penyisipan ditemukan}: Bilangan bulat {tempat sementara agar L[K] tidak ditimpaselama pergeseran }DeskripsiFor IEndfor2 to N doXL[I]J I–1KetemuFalseWhile (J 1) and (not ketemu) doIf X L[J] thenL[J 1]L[J]J J-1Else ketemutrueEndifEndwhileL[J 1] X
Shell sort Pada prinsipnya sama dengan bubble sort yaitumembandingkan elemen array dan melakukanproses penukaran; bedanya kalau bubble sortelemen yang dibandingkan adalah elemen yangbersebelahan sedangkan pada shell sort elemenyang dibandingkan mempunyai jarak tertentu Langkah pembandingan pertama berjarak N div 2,langkah kedua berjarak : jarak langkahperbandingan pertama div 2 demikian seterusnyasampai jarak perbandingan sama dengan satu. Bilajarak sama dengan satu maka prosesnya samadengan Bubble sort
Urutkan secara ascendingLokasi123456Data25271087621Loncat 6 div 2 57621*
Loncat 3 div 2Lokasi 127*76*
52776810212527761
Algoritma :Procedure swap(P,Q : bilangan pecahan)DeklarasiTemp : bilangan pecahanDeskripsiTempPP QQ tempReturnAlgoritma utama:DeklarasiLoncatNKondisiJIL: bilangan bulat: Bilangan Bulat: Boolean: bilangan bulat: bilangan bulat: array [1 . N]
DeskripsiLoncat NWhile loncat 1 doLoncat loncat div 2RepeatKondisi trueFor J 1 to (N- loncat) doI J LoncatIf L [J] L [I] thenSwap (L[J], L[I])Kondisi falseEndifEndforUntil kondisiEndwhile
Quick sort Langkah :a.b.c.d.Elemen 1 pindahkan pada penampung yang berfungsi sebagaipatokanDari kanan ke kiri secara berurutan cari nilai yang lebih kecildari patokan dan pindahkan nilainya pada posisi patokanDari kiri ke kanan secara berurutan cari nilai yang lebih besardari patokan dan pindahkan pada posisi data terakhir yangdipindahLakukan langkah b dan c sampai posisi patokan ditemukan,yaitu–––Bila posisi yang ditinggalkan dan yang ditempati salingbersebelahanBila dari kanan ke kiri tidak ada lagi data yang lebih kecil daripatokanBila dari kiri ke kanan tidak ada lagi data yang lebih besar daripatokan
Urutkan secara ascendingLokasi123456Data25271087621Patokan kr21810*762721810257627
Patokan 627810Patokan 10Lokasikn
Patokan il81021252776
Algoritma :Procedure swap(P,Q : bilangan pecahan)DeklarasiTemp : bilangan pecahanDeskripsiTempPP QQ tempReturn
Procedure bagi ( I, J , M : bilangan bulat)DeklarasiSaklar : bilangan bulatDeskripsiSaklar-1While I J doIf A[I] A[J] thenSwap( A[I} , A[J])Saklar- saklarEndifIf saklar-saklar then J J-1Else I I 1EndifM IEndwhileReturn
Procedure quicksort (L,R : bilangan bulat)deklarasiK, mid : bilangan bulat;DeskripsiWrite („L „, L:2, „, R „, R:2, „ : „);For K L to R doWrite (A[K] : 4)If L R thenIf A[L] A[R] thenswap (A[L], A[R])endifelsebagi(L,R,Mid)call Quicksort(L,Mid-1)Call quicksort(Mid 1, R)EndifEndforReturn
Algoritma utamaDeklarasiA : Array [1.N]I, N: bilangan bulatDeskripsiWrite(„Jumlah komponen „)Readln(N)For I 1 to N doRead(A[I])endforCall Quicksort(1,N)For I 1 to N dowrite(A[I]:4)endfor
Radix Sorta.b.c.d.e.Susun bilangan secara vertikalLakukan penambahan 0 didepan bilangan yang digitnyakurang (samakan digitnya)lakukan pengurutan secara vertikal mulai dari digitpertama dari kiri dan lakukan pengelompokanDalam tiap-tiap kelompok, lakukaan pengurutan secaravertikal untuk digit ke dua dari kiri, Bila dalampengelompokan hanya terdiri dari satu data makaposisinya tetap (tidak perlu diurutkan)Lakukan langkah d sampai dengan digit terakhir. Hasilpengurutan adalah hasil pengelompokan digit terakhir
Lokasi123456Data25171083621Data awalDigit 1 dari kiriDigit 2 dari kiri250808171710101017082521362125213636
Binary Sorta.b.c.d.e.f.Ubah bilangan desimal ke dalam binerSusun secara vertikalLakukan penambahan 0 didepan bilangan yang digitnyakurang (samakan digitnya)lakukan pengurutan secara vertikal mulai dari digitpertama dari kiri dan lakukan pengelompokanDalam tiap-tiap kelompok, lakukaan pengurutan secaravertikal untuk digit ke dua dari kiri, Bila dalampengelompokan hanya terdiri dari satu data makaposisinya tetap (tidak perlu diurutkan)Lakukan langkah e sampai dengan digit terakhir. Hasilpengurutan adalah hasil pengelompokan digit terakhir
Contoh : Urutkan secara ascendingdata : 8,5,4,2,10,7Ubah ke dalam bilangan binary dan lakukan pengurutandari digit 1 dari kiri8 01015 01004 00102 011110 10007 1010
Tanpa mengubah urutan digit 1 dari kiri, lakukanpengurutan digit 2 dari kiri001001110101010010001010
Tanpa mengubah urutan digit 1 dan 2 dari kiri, lakukanpengurutan digit 3 dari kiri001001010100011110001010
Tanpa mengubah urutan digit 1,2 dan 3 dari kiri, lakukanpengurutan digit 4 dari kiri0010 20100 40101 50111 71000 81010 10Hasil Pengurutan secara ascending 2, 4, 5, 7, 8, 10
Three sorta.b.c.d.e.Ambil data pertama dan tempatkan sebagai rootAmbil data ke dua dan bandingkan dengan root, bilanilai data kedua lebih kecil dari root maka tempatkansebagai anak kiri root, bila lebih besar tempatkan sebagaianak kanan rootAmbil data berikutnya, bandingkan dengan root bilalebih kecil dari root bandingkan dengan anak kiri , bilalebih kecil maka akan menjadi anak kiri dari anak kiriroot. begitu juga untuk anak kanannyaLakukan langkah c sampai data terakhirUrutan pembacaannya (bila ascending ) adalah anak kiriyang paling kiri, root, anak kanan paling kiri, anak kanan
Contoh : Urutkan secara ascending data : 8,6,4,5, 2,10,786421075Hasil : 2, 4, 5, 7, 8, 10Anak kiri yang paling kiri – root – anak kanan yang palingkiri – root – anak kanan – root - dst
Loncat : bilangan bulat N : Bilangan Bulat Kondisi : Boolean J : bilangan bulat I : bilangan bulat L : array [1 . N] Deskripsi Loncat N While loncat 1 do Loncat loncat div 2 Repeat Kondisi true For J 1 to (N- loncat) do I J Loncat If L [J] L [I] then Swap (L[J], L[I]) Kondisi false Endif Endfor Until kondisi .
