Algoritma & Pemrograman 1a

Nama: Cynthia Manurung 

NPM : 52414474

Dosen: Kunto Bayu

Kelas : 1IA17

Quicksort

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

QuickSort

Visualisasi Algoritma Quicksort. Garis horisontal merupakan nilai sumbu.
Quicksort
Kelas	Algoritma Sorting
Waktu	O(n2)
Kasus rata-rata	O(n log n)
Kasus terburuk	O(n log n)

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 terburuknya, algoritma ini membuat perbandingan O(n²), 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.

Quicksort ialah versi optimisasi memori dari Binary Tree Sort. Alih-alih memasukkan item secara berurutan pada tree yang jelas, quicksort mengatur mereka secara bersamaan pada tree yang tersirat dengan pemanggilan rekursif. Algoritma membuat perbandingan yang persis sama, tetapi pada urutan yang berbeda. Sifat yang paling diinginkan dari Algoritma Sorting ialah kestabilannya - yang urutan elemennya pada nilai yang sama tidak berubah, memberikan urutan kontrol dari tabel multikey (contoh direktori atau listing folder) pada umumnya. Sifat ini sangat sulit untuk diatur pada quicksort (atau in-place) (yang hanya menggunakan memori tambahan tetap untuk pointer dan buffer, dan memori tambahan lognN untuk pengaturan untuk rekursif yang tampak maupun tidak. Untuk ragam Quicksort melibatkan memori lebih dikarenakan perwakilannya menggunakan pointer (contoh list atau tree) atau file (list yang sering digunakan), yang menjaga stabilitas dengan mudah. Untuk contoh yang lebih kompleks dan rumit, struktur data cenderung meningkatkan waktu yang dibutuhkan, secara umum meningkatkan memori virtual atau disk.
Pesaing quicksort langsung ialah Heapsort. Waktu kalkulasi Worst case Heasort selalu bernilai O(n log n). Tetapi average casenya heapsort diasumsikan lebih lambat dari Quicksort in-place standarnya. Masalah ini masih diperdebatkan dan masih diteliti, karena ada beberapa jurnal ilmiah yang mengatakan sebaliknya.Introsort merupakan variasi dari quicksort yang menukar heapsort ketika terdapat kasus buruk yang dideteksi untuk menghindari worst case quicksort. Lebih lanjut diketahui heapsort akan sangat dibutuhkan, menggunakan heapsort secara langsung akan lebih cepat dari pada harus menunggu introsort untuk menukarnya.
Quicksort juga bersaing dengan Mergesort, algoritma sorting rekursif yang lainnya tetapi dengan keuntungan waktu kalkulasi worst casenya O(n log n). Mergesort merupakan sorting stabil, tidak seperti quicksort in-place dan heapsort standar, dan dapat dengan mudah diadaptasikan untuk berjalan pada linked list dan list dengan penyimpanan yang sangat besar pada media dengan akses lambat seperti disk penyimpanan atau penyimpanan pada jaringan. Seperti pula mergesort, quicksort dapat diimplementasikan sebagai sorting stabil in-place,tetapi hal ini jarang digunakan. Walaupun quicksort dikatakan dapat berjalan pada linked list, tapi sering mendapatkan pivot yang buruk tanpa menggunakan akses acak. Kerugian utama dari mergesort ialah, ketika berjalan pada array, implementasi yang efisient membutuhkan ruang tambahan O(n), sedangkan variasi dari quicksort dengan patitisasi in-place dan rekursif ekor hanya menggunakan memori sebesar O(log n). (dengan catatan bahwa ketika menjalankannya pada linked list, mergesort hanya membutuhkan ruang tambahan yang konstan, namun kecil).
Bucket Sort dengan dua keranjang atau bucket hampir sama dengan quicksort; pivot pada kasus ini secara efektif mengambil nilai tengah dari range nilai, yang dimana berjalan dengan sangat baik pada average case untuk input yang terdistribusi secara umumnya.

Terdapat empat ragam quicksort yang paling terkenal:

• Balanced Quicksort: memilih pivot mungkin untuk mewakili pertengah dari nilai yang akan dipilih, dan kemudian mengikuti algoritma quicksort seperti biasa.

• External Quicksort: sama seperti quicksort yang biasanya kecuali pivot digantikan dengan buffer. Pertama, baca M/2 elemen pertama dan kedua menjadi buffer dan urutkan mereka. Baca elemen selanjutnya dari awal atau akhir untuk menyeimbangkan penulisan. Jika elemen selanjutnya lebih kurang dari buffer terendah, maka tulis elemen itu pada ruang yang tersedia pada awal. Jika lebih besar dari buffer tertinggi, maka tulis elemen itu pada akhir. Atau tidak tulis buffer terbesar atau terkecil, dan tempatkan elemen selanjutnya pada buffer. Tetap tulis elemen maksimum dan minimum untuk menghindari diurutkannya lagi elemen tengah yang telah terurut. Ketika selesai, tulis buffernya. Secara recursif urutkan kembali partisi yang lebih kecil, dan ulangi urutannya pada partisi yang tersisa. Cara ini merupakan tiga cara quicksort yang yang dimana buffer (partisi tengah) mewakili subarray yang telah diurut dari elemen yang kkira-kira sama dengan pivotnya.

• Tiga cara Quicksort radiks (ditemukan oleh Sedgewick dan juga dikenal sebagai Multikey Quicksort): ialah kombinasi dari Radix sort dan Quicksort. Ambil sebuah elemen dari array (pivotnya) dan tempatkan karakter pertama pada string (multikey). Partisikan elemen sisa menjadi tiga set: karakter yang lebih kecil, sama, dan lebih besar dari karakter pivot. Urut secara rekursif partisi "kurang dari" dan "lebih dari" pada karakter yang sama. Urutkan secara rekursif partisi "sama dengan" dengan karakter selanjutnya (tanda). Pertimbangkan dengan mengurut menggunakan bytes atau words dari panjang W bit, best casenya ialah O(KN) dan worst casenya ialah O(2^KN) atau paling tidak O(N²) sebagai quicksort standar, dengan diberikan untuk tanda khusus N<2 sup="">K

, dan K adalah konstanta yang tersembunyi pada seluruh algortima sorting pembanding semuanya termasuk quicksort. Ini merupakan salah satu dari tiga cara quicksort yang partisi tengah mewakili urutan subarray elemen (mudah) yang persis sama dengan pivot.
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:

   // 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'

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 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')

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.



Ruang yang digunakan oleh quicksort tergantung dari versi yang digunakan.
Versi In-Place dari Quicksort menggunakan kerumitan ruang dari O(long n), bahkan pada worst case, ketika diimplementasikan menggunakan beberapa strategi berikut:

• Menggunakan Partisi In-place. Partisi yang tak stabil ini memerlukan ruang O(1).
• Setelah melakukan partisi, partisi yang memiliki elemen yang lebih kecil secara rekursif diurutkan terlebih dahulu, yang membutuhkan ruang paling banyak O(log n). Kemudian partisi lainnya diurutkan menggunakan rekursif ekor atau iterasi, yang tidak ditambahkan pada panggilan tumpukan. Ide ini, seperti yang telah diceritakan diatas, dijelaskan oleh Robert Sedgewick, dan menjaga kedalaman tumpukan dengan O(log n).

Quicksort dengan Sistem Partisi In-Place dan unstable menggunakan ruang tambahan konstan sebelum membuat panggilan rekursif manapun. Quicksort haru menyimpan jumlah informasi tetap untuk setiap pemanggilan rekursif bersarang. Sejak best case dapat membuat paling banyak O(long n) pemanggilan rekursif bersarang, yang menggunakan ruang O(log n). Bagaimanapun cara Sedgewick untuk membatasi pemanggilan rekursif, pada worst case quicksort dapat membuat pemanggilan bersarang O(n) dan membutuhkan ruang tambahan O(n).
Dari sudut pandang yang lumayan rumit, variabel seperti kiri dan kanan tidak menggunakan ruang konstan; tetapi menggunakan O(log n) bit pada indeks list dari n kali. Karena terdapat variabel pada setiap tumpukan frame, quicksort menggunakan cara Sedgewick yang membutuhkan bit ruang. Kebutuhan ruang ini tidaklah buruk, walaupun sejak jika list yang mengandung elemen berbeda, maka akan membutuhkan paling kurang O(n log n) bits ruang.
Lainnya, kurang lebih, yang bukan algoritma In-Place, versi Quicksort yang menggunakan ruang O(n) untuk menyimpan dan dapat mengimplementasikan urutan yang stabil. Tempat penyimpanan menyediakan inputan array dengan mudah dipartisi pada cara yang stabil dan kemudian menyalinnya kembali pada inputan array untuk pemanggilan rekursif yang berurutan. Optimisasi Sedgewick masih sangat sesuai.