Quicksort: Memilih pivot

Saat menerapkan Quicksort, salah satu hal yang harus Anda lakukan adalah memilih pivot. Tetapi ketika saya melihat pseudocode seperti di bawah ini, tidak jelas bagaimana saya harus memilih pivot. Elemen pertama daftar? Sesuatu yang lain?

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     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))

Dapatkah seseorang membantu saya memahami konsep memilih pivot dan apakah skenario yang berbeda memerlukan strategi yang berbeda atau tidak.

Memilih pivot acak meminimalkan kemungkinan Anda akan mengalami performa O (n ² ) kasus terburuk (selalu memilih pertama atau terakhir akan menyebabkan performa terburuk untuk data yang hampir diurutkan atau hampir diurutkan terbalik). Memilih elemen tengah juga dapat diterima di sebagian besar kasus.

Selain itu, jika Anda mengimplementasikannya sendiri, ada versi algoritme yang berfungsi di tempat (yaitu tanpa membuat dua daftar baru dan kemudian menggabungkannya).

Itu tergantung pada kebutuhan Anda. Memilih pivot secara acak mempersulit pembuatan kumpulan data yang menghasilkan performa O (N ^ 2). 'Median-of-three' (pertama, terakhir, tengah) juga merupakan cara untuk menghindari masalah. Waspadalah terhadap kinerja perbandingan relatif; jika perbandingan Anda mahal, Mo3 melakukan lebih banyak perbandingan daripada memilih (satu nilai pivot) secara acak. Catatan database bisa mahal untuk dibandingkan.

Pembaruan: Menarik komentar menjadi jawaban.

mdkess menegaskan:

'Median dari 3' BUKAN bagian tengah terakhir yang pertama. Pilih tiga indeks acak, dan ambil nilai tengahnya. Intinya adalah memastikan bahwa pilihan pivot Anda tidak deterministik - jika ya, data kasus terburuk dapat dibuat dengan mudah.

Yang saya jawab:

• Analisis Algoritma Temukan Hoare Dengan Median-Of-Three Partition (1997) oleh P Kirschenhofer, H Prodinger, C Martínez mendukung pendapat Anda (bahwa 'median-of-three' adalah tiga item acak).

• Ada sebuah artikel yang dijelaskan di portal.acm.org yaitu tentang 'Permutasi Kasus Terburuk untuk Median-of-Three Quicksort' oleh Hannu Erkiö, diterbitkan dalam The Computer Journal, Vol 27, No 3, 1984. [Update 2012-02- 26: Mendapat teks untuk artikel tersebut . Bagian 2 'Algoritma' dimulai: ' Dengan menggunakan median dari elemen pertama, tengah dan terakhir dari A [L: R], partisi yang efisien menjadi bagian-bagian dengan ukuran yang cukup sama dapat dicapai dalam banyak situasi praktis. 'Jadi, ini membahas pendekatan Mo3 pertama-tengah-terakhir.]

• Artikel pendek lain yang menarik adalah oleh MD McIlroy, "A Killer Adversary for Quicksort" , diterbitkan dalam Software-Practice and Experience, Vol. 29 (0), 1–4 (0 1999). Ini menjelaskan bagaimana membuat hampir semua Quicksort berperilaku kuadrat.

• AT&T Bell Labs Tech Journal, Okt 1984 "Teori dan Praktek dalam Pembangunan Rutinitas Jenis Kerja" menyatakan "Hoare menyarankan partisi di sekitar median dari beberapa baris yang dipilih secara acak. Sedgewick [...] merekomendasikan memilih median dari [. ..] terakhir [...] dan tengah ". Ini menunjukkan bahwa kedua teknik untuk 'median-of-three' dikenal dalam literatur. (Perbarui 2014-11-23: Artikel tersebut tampaknya tersedia di IEEE Xplore atau dari Wiley - jika Anda memiliki keanggotaan atau siap membayar biaya.)

• 'Engineering a Sort Function' oleh JL Bentley dan MD McIlroy, diterbitkan dalam Software Practice and Experience, Vol 23 (11), November 1993, membahas masalah secara ekstensif, dan mereka memilih algoritme partisi adaptif yang sebagian didasarkan pada ukuran kumpulan data. Ada banyak diskusi tentang trade-off untuk berbagai pendekatan.

• Pencarian Google untuk 'median-of-three' bekerja dengan cukup baik untuk pelacakan lebih lanjut.

Terima kasih untuk informasi; Saya hanya menemukan 'median-of-three' deterministik sebelumnya.

Heh, saya baru saja mengajar kelas ini.

Ada beberapa pilihan.
Sederhana: Pilih elemen pertama atau terakhir dari rentang. (buruk pada masukan yang diurutkan sebagian) Lebih baik: Pilih item di tengah rentang. (lebih baik pada masukan yang diurutkan sebagian)

Namun, memilih elemen sembarang apa pun berisiko mempartisi buruk larik berukuran n menjadi dua larik berukuran 1 dan n-1. Jika Anda melakukannya cukup sering, quicksort Anda berisiko menjadi O (n ^ 2).

Satu peningkatan yang saya lihat adalah memilih median (pertama, terakhir, pertengahan); Dalam kasus terburuk, ini masih bisa pergi ke O (n ^ 2), tetapi secara probabilistik, ini adalah kasus yang jarang terjadi.

Untuk sebagian besar data, memilih yang pertama atau terakhir sudah cukup. Namun, jika Anda sering mengalami skenario terburuk (masukan yang diurutkan sebagian), opsi pertama adalah memilih nilai pusat (Yang merupakan poros yang secara statistik baik untuk data yang diurutkan sebagian).

Jika Anda masih mengalami masalah, lakukan rute median.

Jangan pernah memilih pivot tetap - ini dapat diserang untuk mengeksploitasi kasus terburuk runtime O (n ^ 2) algoritme Anda, yang hanya akan menimbulkan masalah. Runtime kasus terburuk Quicksort terjadi ketika partisi menghasilkan satu larik dari 1 elemen, dan satu larik n-1 elemen. Misalkan Anda memilih elemen pertama sebagai partisi Anda. Jika seseorang memasukkan array ke algoritme Anda yang urutannya menurun, pivot pertama Anda akan menjadi yang terbesar, jadi semua yang lain di dalam array akan pindah ke kiri. Kemudian ketika Anda mengulang, elemen pertama akan menjadi yang terbesar lagi, jadi sekali lagi Anda meletakkan semuanya di sebelah kiri, dan seterusnya.

Teknik yang lebih baik adalah metode median-of-3, di mana Anda memilih tiga elemen secara acak, dan memilih tengah. Anda tahu bahwa elemen yang Anda pilih tidak akan menjadi yang pertama atau yang terakhir, tetapi juga, berdasarkan teorema limit pusat, distribusi elemen tengah akan normal, yang berarti Anda akan cenderung ke tengah (dan karenanya , n lg n waktu).

Jika Anda benar-benar ingin menjamin runtime O (nlgn) untuk algoritme, metode kolom-of-5 untuk menemukan median array berjalan dalam waktu O (n), yang berarti persamaan pengulangan untuk quicksort dalam kasus terburuk akan menjadi T (n) = O (n) (menemukan median) + O (n) (partisi) + 2T (n / 2) (berulang kiri dan kanan.) Menurut Teorema Utama, ini adalah O (n lg n) . Namun, faktor konstanta akan sangat besar, dan jika kinerja kasus terburuk adalah perhatian utama Anda, gunakan jenis gabungan, yang hanya sedikit lebih lambat dari rata-rata quicksort, dan menjamin waktu O (nlgn) (dan akan jauh lebih cepat dari quicksort rata-rata lumpuh ini).

Penjelasan Median Algoritma Median

Jangan mencoba dan menjadi terlalu pintar dan menggabungkan strategi berputar. Jika Anda menggabungkan median 3 dengan poros acak dengan memilih median dari indeks pertama, terakhir dan indeks acak di tengah, maka Anda masih rentan terhadap banyak distribusi yang mengirimkan median 3 kuadrat (jadi sebenarnya lebih buruk daripada poros acak polos)

Misalnya distribusi organ pipa (1,2,3 ... N / 2..3,2,1) pertama dan terakhir keduanya akan menjadi 1 dan indeks acak akan menjadi beberapa angka lebih besar dari 1, mengambil median memberikan 1 ( baik pertama atau terakhir) dan Anda mendapatkan partisi yang sangat tidak seimbang.

Lebih mudah membagi quicksort menjadi tiga bagian dengan melakukan ini

1. Tukar atau tukar fungsi elemen data
2. Fungsi partisi
3. Memproses partisi

Ini hanya sedikit lebih tidak efektif daripada satu fungsi panjang tetapi jauh lebih mudah untuk dipahami.

Kode berikut:

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

Ini sepenuhnya tergantung pada bagaimana data Anda diurutkan untuk memulai. Jika Anda pikir itu akan menjadi pseudo-random maka taruhan terbaik Anda adalah memilih pilihan acak atau memilih tengah.

Jika Anda mengurutkan koleksi yang dapat diakses secara acak (seperti array), sebaiknya pilih item tengah fisik. Dengan ini, jika semua array siap diurutkan (atau hampir diurutkan), kedua partisi akan mendekati genap, dan Anda akan mendapatkan kecepatan terbaik.

Jika Anda menyortir sesuatu hanya dengan akses linier (seperti daftar tertaut), maka yang terbaik adalah memilih item pertama, karena ini adalah item tercepat untuk diakses. Di sini, bagaimanapun, jika daftarnya sudah diurutkan, Anda kacau - satu partisi akan selalu nol, dan yang lainnya memiliki segalanya, menghasilkan waktu terburuk.

Namun, untuk daftar tertaut, memilih apa pun selain yang pertama, hanya akan memperburuk keadaan. Itu memilih item tengah dalam daftar-terdaftar, Anda harus melangkah melewatinya pada setiap langkah partisi - menambahkan operasi O (N / 2) yang dilakukan logN kali membuat total waktu O (1,5 N * log N) dan itu jika kita tahu berapa panjang daftarnya sebelum kita mulai - biasanya kita tidak melakukannya, jadi kita harus melangkah jauh untuk menghitungnya, lalu melangkah setengah jalan untuk menemukan tengahnya, lalu melangkah melalui ketiga kalinya untuk melakukan partisi sebenarnya: O (2.5N * log N)

Idealnya, pivot harus menjadi nilai tengah di seluruh larik. Ini akan mengurangi kemungkinan mendapatkan kinerja kasus terburuk.

Kompleksitas pengurutan cepat sangat bervariasi dengan pemilihan nilai pivot. misalnya jika Anda selalu memilih elemen pertama sebagai pivot, kompleksitas algoritme menjadi paling buruk seperti O (n ^ 2). berikut adalah metode cerdas untuk memilih elemen pivot- 1. pilih elemen pertama, tengah, terakhir dari array. 2. Bandingkan ketiga angka ini dan temukan angka yang lebih besar dari satu dan lebih kecil dari yang lain yaitu median. 3. jadikan elemen ini sebagai elemen pivot.

memilih pivot dengan metode ini membagi array menjadi hampir dua setengah dan karenanya kompleksitasnya berkurang menjadi O (nlog (n)).

Rata-rata, Median 3 bagus untuk n kecil. Median 5 sedikit lebih baik untuk n yang lebih besar. Ninther, yang merupakan "median dari tiga median dari tiga" bahkan lebih baik untuk n yang sangat besar.

Semakin tinggi Anda melakukan pengambilan sampel, semakin baik Anda mendapatkan n meningkat, tetapi peningkatan secara dramatis melambat saat Anda meningkatkan sampel. Dan Anda dikenakan biaya overhead pengambilan sampel dan pengurutan sampel.

Saya merekomendasikan menggunakan indeks tengah, karena dapat dihitung dengan mudah.

Anda dapat menghitungnya dengan pembulatan (array.length / 2).

Dalam implementasi yang benar-benar dioptimalkan, metode untuk memilih pivot harus bergantung pada ukuran larik - untuk larik yang besar, sebaiknya Anda menghabiskan lebih banyak waktu untuk memilih pivot yang baik. Tanpa melakukan analisis lengkap, saya kira "tengah dari elemen O (log (n))" adalah awal yang baik, dan ini memiliki bonus tambahan karena tidak memerlukan memori tambahan: Menggunakan tail-call pada partisi yang lebih besar dan di- partisi tempat, kami menggunakan memori tambahan O (log (n)) yang sama di hampir setiap tahap algoritme.