Skip to main content

STRUKTUR DATA


      QUICK SORT







AHMAD FAJAR SUSILO

2115R1067

PENGERTIAN QUICK SORT

Algoritma quick sort diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960, dan dimuat sebagai artikel di “Computer Journal 5” pada April 1962. Quick sort adalah algoritma sorting yang berdasarkan pembandingan dengan metoda divide-and-conqueror. Disebut Quick Sort, karena Algoritma quick sort mengurutkan dengan sangat cepat.


  Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.


Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data,  kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa


Strategi divide-and-conqueror digunakan di dalam quicksort.
Di bawah
ini akan dijelaskan langkah-langkahnya:


Pilih nilai pivot Kita ambil nilai di tengah-tengah elemen sebagai sebagai nilaidari pivot  tetapi bisa nilai mana saja.




Partisi  Atur ulang semua elemen sedemikian rupa, lalu semua elemen yang lebihrendah daripada pivot dipindahkan ke sebelah kiri dari array/list dan semuaelemen yang lebih besar dari  pivot dipindahkan ke sebelah kanan dari array/list. Nilai yang sama dengan pivot  dapat diletakkan di mana saja dari array. Ingat,mungkin array/list akan dibagi dalam bagian yang tidak sama.



Urutkan semua bagian (kiri/kanan)  Aplikasikan algoritma quicksort secararekursif pada bagian sebelah kiri dan kanan.


Algoritma Partisi secara detail

Ada dua indeks i dan j dan pada awal algoritma partisi i menunjuk ke elemen  pertama dalam array dan poin j yang terakhir. Kemudian algoritma menggerakkan i ke depan, sampai elemen dengan nilai yang lebih besar atau sama dengan pivot ditemukan. Indeks j bergerak mundur, sampai elemen dengan nilai yang lebih rendah atau sama dengan pivot ditemukan.


Jika i ≤ j maka mereka bertukar dan saya

langkah ke posisi berikutnya (i + 1), langkah-langkah j dengan yang sebelumnya (j - 1). Algoritma berhenti, ketika saya menjadi lebih besar dari j. Setelah partisi, semua nilai sebelum elemen ke-i kurang atau sama dengan pivot dan semua nilai setelah elemen ke-j lebih besar atau sama dengan pivot.

KELEBIHAN

Algoritma Quicksort memiliki kompleksitas O(n log n) dimana pada  prakteknya lebih cepat dari algoritma pengurutan lainnya.

KEKURANGAN

Pada kemungkinan terburuknya, algoritma Quicksort ini dapat memiliki kompleksitas O(n2). Meskipun ini sangat langka terjadi


Image Exampel Quick Sort


SUMBER : http://catatan-ati.blogspot.co.id/2015/08/pengertian-quick-sort-dan-implementasi.html#sthash.X4k9S9jC.dpuf

SEKIAN
DAN
TERIMA KASIH

Comments

Popular posts from this blog

Inilah 5 Teknologi Baru Tercanggih yang di Dunia

Banyak teknologi terbaru yang telah ditemukan oleh para ilmuwan memang menggemparkan dunia. Sebagian banyak dari teknologi terbaru yang bisa dikategorikan tercanggih dan terunik ini tidak diluncurkan ke pasaran, yang memang banyak faktor yang menjadi kendala, bahkan banyak juga yang hanya berakhir begitu saja, faktor seperti biaya produksi yang berpengaruh terhadap harga jual yang terlalu tinggi, atau mungkin dari segi fungsi. Berikut ini ada 5 teknologi baru tercanggih yang menggemparkan dunia! 1.Quantum teleporter Q-Teleportation telah berhasil pada objek yang lebih kecil berdasarkan penelitian yang telah dilakukan. Pada Q-Teleportation, quantum pada objek dihancurkan dan dibuat kembali. Oleh karena itu, Q-Teleportation nggak bisa memindahkan benda hidup maupun mati secara keseluruhan fisik. Alat ini "menciptakan" replika benda sebelumnya pada posisi di tempat lain dan benda sebelumnya akan "menghilang" selama replikanya di...

Kode macro excel

Hai, sahabat Excel-ID jika Anda sedang belajar VBA (Macro) Excel tentunya perlu donk referensi untuk menambah wawasan dan pengetahui mengenai coding. Dan pada kesempatan ini saya akan berbagi daftar code VBA yang perlu diketahui dan dipelajari oleh Anda yang sedang belajar VBA. Kelebihan VBA Excel ini Anda bisa lebih bereksplorasi mengenai Excel Advance dan Anda bisa memaksimalkan keunggulan dalam penggunaan Excel untuk kebutuhan dunia kerja Anda. Oke berikut adalah koleksi kode VBA Macro Excel yang perlu diketahui. Coding VBA (Macro) Excel Backup File Sub FileBackUp() ThisWorkbook.SaveCopyAs Filename:=ThisWorkbook.Path & _ "" & Format(Date, "mm-dd-yy") & " " & _ ThisWorkbook.name End Sub Coding VBA (Macro) Menutup Semua File Kecuali yang Aktif Sub CloseAllWorkbooks() Dim wbs As Workbook For Each wbs In Workbooks wbs.Close SaveChanges:=True Next wb End Sub Coding VBA (Macro) Menyembunyikan Worksheet Sub HideWorksheet() Dim...

HTML

Sejarah dan Masa Depan HTML.  Teknologi selalu berkembang dan akan meningkat semakin tinggi. Seorang yang mempunyai profesi sebagai Desainer harus terus mengupdate diri mereka dengan tren dan teknologi terbaru agar bisa bertahan dalan kompetisi yang begitu ketat. Bisa dikatakan, seorang desainer yang tidak pernah memperbarui dirinya dengan teknologi, tren masa kini, dan pengetahuan-pengetahuan yang baru akan jatuh dan menjadi desainer yang ketinggalan jaman. Sejarah dan Masa Depan HTML Sejarah HTML  W3C   (World Wide Web Consortium)  adalah organisasi internasional yang menggabungkan pengguna melalui koneksi internet dan perancangan platform. W3C dituan-rumahi oleh tiga universitas berbeda yang berlokasi di Jepang, USA, dan Eropa. W3C juga diasosiasikan dengan banyak Industri software yang terkenal seperti IMB, Sun Microsystems, AOL, Apple, Adobe, Microsoft dan banyak lagi industri yang mempunyai reputasi Besar dalam pasar software. HTML at...