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 .