NPM : 54414833
DOSEN : Kunto Bayu A, ST
MATKUL : Algoritma & Pemrograman 1A
Quicksort merupakan Algoritma Sorting yang dikembangkan oleh Tony Hoare yang, secara kasus rata-rata, membuat pengurutan O(n log n) untuk mengurutkan n item. Algoritma ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting Pergantian Pembagi. Pada kasus terbentuknya, algoritma ini membuat perbandingan O(n2), malaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya dari pada algoritma O(n log n) yang lainnya. Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n).
Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritma sorting yang stabil.
contoh quicksort

ALGORITMA
Quicksort merupakan Algoritma Pembagi. Pertama sekali quicksort membagi list yang besar menjadi dua buah sub list yang lebih kecil: element kecil dan element besar. Quicksort kemudian dapat menyortir sub list itu secara rekursif.
Langkah-Langkah pengerjaannya ialah:
- Ambil sebuah elemen, yang disebut dengan pivot, pada sebuah daftar.
- Urutkan kembali sebuah list sehingga elemen dengan nilai yang kecil dari pivot berada sebelum pivot, sedangkan seluruh element yang memiliki nilai yang lebih besar dari pivot berada setelahnya (nilai yang sama dapat berada pada pivot setelahnya). Setelah pemisahan, pivot berada pada posisi akhirnya. Operasi ini disebut Partition.
- Sub list kemudian disortir secara recursif dari elemen yang lebih kecil dan sub list dari elemen yang lebih besar.
Versi Sederhana
Dalam Pseudocode sederhana, Algoritmanya dapat dinyatakan sebagai berikut:
function quicksort('array') if length('array') ≤ 1 return 'array' // an array of zero or one elements is already sorted select and remove a pivot value 'pivot' from 'array' create empty lists 'less' and 'greater' for each 'x' in 'array' if 'x' ≤ 'pivot' then append 'x' to 'less' else append 'x' to 'greater' return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

Contoh keseluruhan dari quicksort pada kumpulan acak dari angka. Element
yang gelap merupakan pivot. Pivot selalu dipilih sebagai element
terakhir pada partisi. Bagaimanapun, selalu memilih elemen terakhir pada
partisi sebagai pivot sehingga hasil pada kasus terburuk (
) pada daftar yang telah diurutkan,
atau daftar yang serupa. Karena elemen yang sama memotong hingga pada
akhir dari prosedur soring pada jumlah yang besar, versi dari algoritma
quicksort yang memilih pivot sebagai elemen tengah berjalan lebih cepat
dari pada algortima yang dijelaskan pada diagram ini pada sejumlah besar
angka.

Kebenaran dari algoritma partisi didasari pada dua argumen berikut:
- Pada setiap iterasi, seluruh elemen diproses selama ini berada pada posisi yang diinginkan: sebelum pivot lebih kurang dari nilai pivot, setelah pivot lebih besar dari nilai pivot (Invarian Loop).

Partisi ditepat bekerja pada daftar yang kecil. Elemen kotak merupakan
element pivot, elemen berwarna biru merupakan elemen yang bernilai kecil
atau sama, dan elemen yang berwarna merah lebih besar.
Versi In-Place
Kerugian dari versi sederhana diatas membutuhkan ruang simpan O(n) yang lebih besar, yang sama buruknya seperti merge sort.
Memory tambahan yang dibutuhkan dapat juga secara radikal berpengaruh
pada kecepatan dan performa cache pada implementasi praktiknya. Terdapat
juga versi yang lebih rumit yang menggunakan algoritma partisi in-place dan dapat mencapai urutan lengkap menggunakan ruang O(logn) (tidak dihitung input) pada rata-rata (untuk sekali pemanggilan tumpukan). Kita mulai dengan fungsi partisi:
Ini merupakan Algoritma Partisi In-Place. algortima ini memisahkan bagian dari array antara index kiri dan kanan secara inklusif, dengan memindahkan seluruh elemen kurang dari
Setelah kita memiliki ini, menulis quicksort sendiri ialah mudah:
Setiap pemanggilan rekursif pada fungsi quicksort ini mengurangi besar dari array yang akan diurutkan paling tidak satu elemen, semenjak setiap elemen pada pivotNewIndex diletakkan pada posisi akhirnya. Oleh karena itu, algoritma ini menjamin mengakhiri pemanggilan rekursif pada paling banyak n pemanggilan. Bagaimanapun, versi dari quicksort ini tidak stabil semenjak pengurutan elemen partisi hanya dilakukan pada satu partisi.
Daftar Pustaka http://id.wikipedia.org/wiki/Quicksort
// left is the index of the leftmost element of the array // right is the index of the rightmost element of the array (inclusive) // number of elements in subarray = right-left+1 function partition(array, 'left', 'right', 'pivotIndex') 'pivotValue' := array['pivotIndex'] swap array['pivotIndex'] and array['right'] // Move pivot to end 'storeIndex' := 'left' for 'i' from 'left' to 'right' - 1 // left ≤ i < right if array['i'] < 'pivotValue' swap array['i'] and array['storeIndex'] 'storeIndex' := 'storeIndex' + 1 swap array['storeIndex'] and array['right'] // Move pivot to its final place return 'storeIndex'
array[pivotIndex]
sebelum pivot, dan elemen yang sama atau lebih besar darinya. Dalam
prosesnya, algoritma ini juga mencari posisi akhir untuk elemen pivot,
yang kembali. algoritma ini secara sementara memindahkan elemen pivot
pada akhir dari subarray, sehingga tidak mengganggu proses algoritma.
Karena hanya menggunakan penukaran, list akhir memiliki elemen yang sama
seperti elemen awalnya. Perlu diperhatikan bahwa elemen ditukan
beberapa kali sebelum mencapai tempat akhirnya. Dan juga, jika pivot itu
ganda pada inputan array, mereka dapat menyebar pada subarray kanan,
pada urutan apapun. Cara ini tidak mewakili kesalahan dalam membagi,
dimana pengurutan lebih lanjut akan memindahkan dan akhirnya merekatkan mereka bersama.Setelah kita memiliki ini, menulis quicksort sendiri ialah mudah:
function quicksort(array, 'left', 'right') // If the list has 2 or more items if 'left' < 'right' // See "Choice of pivot" section below for possible choices choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right' // Get lists of bigger and smaller items and final position of pivot 'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex') // Recursively sort elements smaller than the pivot quicksort(array, 'left', 'pivotNewIndex' - 1) // Recursively sort elements at least as big as the pivot quicksort(array, 'pivotNewIndex' + 1, 'right') |
Daftar Pustaka http://id.wikipedia.org/wiki/Quicksort
Tidak ada komentar:
Posting Komentar