Algoritma - Quick Sort

Setelah membahas materi lalu tentang bubble sort, penyortiran dalam algoritma juga ada yang dikenal sebagai Quick sort. Algoritma ini diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960, merupakan salah satu algoritma pengurutan yang paling populer berdasarkan divide and conquer sehingga menghasilkan kompleksitas O (n log n). Algoritme dimulai dengan memilih item, yang disebut pivot, dan memindahkan semua item yang lebih kecil sebelumnya, sementara semua elemen yang lebih besar setelahnya. Inilah operasi utama quick sor yang disebut partisi, berulang secara rekursif pada sub daftar yang lebih kecil dan lebih kecil sampai ukurannya satu atau nol - dalam hal ini daftar disortir secara implisit. Memilih pivot yang tepat, seperti misalnya elemen median adalah funda-mental untuk menghindari penurunan drastis dari O (n2).

Algoritma quicksort memiliki worst-case running time - n2 pada array input n angka. Terlepas dari worst-case running time, quicksort sering merupakan pilihan praktis terbaik untuk menyortir karena sangat efisien secara rata-rata: Running time yang diharapkan adalah ‚.n lg n /, dan faktor konstan yang tersembunyi di‚ .n lg n / notasi cukup kecil. Ini juga memiliki keuntungan penyortiran di tempat (lihat halaman 17), dan bekerja dengan baik bahkan di lingkungan virtual-memory.

Algoritma ini dengan subrutin sangat penting digunakan dengan quicksort untuk partisi. Versi quicksort juga menggunakan sampling acak. Algoritma ini memiliki waktu berjalan yang diharapkan baik, dan tidak ada masukan tertentu yang memunculkan perilaku terburuknya. Quick sort memiliki algoritma acak sehingga menunjukkan bahwa ia berjalan dalam ‚.n2 / waktu dalam kasus terburuk dan, dengan asumsi elemen yang berbeda, dalam harapan O. n lg n / waktu.

Quicksort mirip dengan merge sort yang sudah dibahas sebelumnya, dengan mengaplikasikan metode divide-and-conquer. Berikut ini adalah langkah proses divide-and-conquer untuk menyortir. Ingat bahwa tujuan kita pada algoritma ini adalah untuk mempartisi semua elemen yang tersisa berdasarkan apakah mereka lebih kecil dari atau lebih besar dari pivot. Disini kita akan akan menemukan dua entri: Satu lebih besar dari pivot (menatap dari depan) Satu lebih kecil dari pivot (mulai dari belakang) yang kacau urutannya dan kemudian memperbaiki urutannya Menukar urutan

Terus lakukan hingga entri yang tepat yang Anda temukan benar-benar dalam urutan. Indeks ke entri yang lebih besar yang kit atemukan akan menjadi entri besar ertama dalam daftar (seperti yang terlihat dari kiri) Oleh karena itu, kita dapat memindahkan entri ini ke entri terakhir dari daftar Kita dapat mengisi tempat ini dengan pivot

box1

algorithm QuickSort(list)

    Pre: list  

    Post: Daftar ini udah disortir dalam urutan meningkat
    if list.Count = 1 // Sudah disortir
      return list
    end if
    pivot      MedianValue(list)
    for i     	0 to list.Count --1
      if list[i] = pivot
         equal.Insert(list[i])
      end if
      if list[i] < pivot
         less.Insert(list[i])
      end if
      if list[i] > pivot
         greater.Insert(list[i])
      end if
    end for
    return Concatenate(QuickSort(less), equal,QuickSort(greater))
  end Quicksort

Waktu berjalan dari quicksort tergantung pada apakah partisi tersebut seimbang atau tidak seimbang, yang pada gilirannya tergantung pada elemen yang digunakan untuk partisi. Jika partisi tersebut seimbang, algoritma berjalan asimtotik secepat penggabungan. Jika partisi tidak seimbang, bagaimanapun, dapat berjalan asimtotik secara perlahan-lahan seperti penyisipan.

Kelebihan dari Algoritma Quicksort ini memiliki kompleksitas O(n log n) dimana pada aplikasinya lebih cepat dari algoritma pengurutan lainnya sedangkan Kekurangannya algoritma Quicksort ini dapat memiliki kompleksitas O(n2) walaupun ini sangat langka terjadi