WikiDer > Ko'p kalitli tezkor kontseptsiya - Vikipediya

Multi-key quicksort - Wikipedia

Ko'p kalitli tezkor kort, shuningdek, nomi bilan tanilgan uch tomonlama radixli tezkor kortort,[1] bu algoritm uchun tartiblash torlar. Ushbu gibrid tezkor va radiks sort dastlab P. Shaklton tomonidan taklif qilingan, birida aytilganidek C.A.R. HoareSeminal hujjatlar tezkor;[2]:14 uning zamonaviy mujassamlanishi tomonidan ishlab chiqilgan Jon Bentli va Robert Sedvik 1990-yillarning o'rtalarida.[3] Algoritm ko'pgina muammolarda satrlar birgalikda bo'lish xususiyatidan foydalanishga mo'ljallangan prefikslar.

Algoritmdan biri bu qurishdir qo'shimchalar qatorlari, buning uchun u 2004 yildagi eng tezkor algoritmlardan biri edi.[4]

Tavsif

Uch tomonli radixli tezkor algoritm qatorni saralaydi N (ko'rsatgichlar ga) qatorlar leksikografik tartib. Barcha satrlar teng uzunlikka ega deb taxmin qilinadi K; agar torlar har xil uzunlikda bo'lsa, ular iplarning har qanday elementidan kam bo'lgan qo'shimcha elementlar bilan to'ldirilishi kerak.[a] Algoritm uchun psevdokod keyin bo'ladi[b]

algoritm sort (a: qator qatori, d: integer) bu    agar uzunlik (a) ≤ 1 yoki d ≥ K keyin        qaytish    p: = burilish (a, d) i, j: = qism (a, d, p) (Bir vaqtning o'zida ikkita o'zgaruvchining tayinlanishiga e'tibor bering.)    sort (a [0: i), d) sort (a [i: j), d + 1) sort (a [j: uzunlik (a)), d)

The pivot funktsiya bitta belgini qaytarishi kerak. Bentli va Sedvik ikkitasini tanlashni taklif qilishadi o'rtacha ning a [0] [d], ..., a [uzunlik (a) -1] [d] yoki ushbu diapazondagi tasodifiy belgi.[3] Bo'lim funktsiyasi oddiy ishlatiladigan variantning bir variantidir uch tomonlama tezkor kort: u qayta tartibga soladi a shuning uchun hammasi a [0], ..., a [i-1] holatida elementga ega bo'lish d bu kamroq p, a [i], ..., a [j-1] bor p holatida dva simlar j oldinga ega ddan katta element p. (Bentley va Sedgvik tomonidan taklif qilingan asl bo'lim funktsiyasi takrorlanadigan elementlarda sekin bo'lishi mumkin; a Gollandiyaning milliy bayrog'ini ajratish buni engillashtirish uchun foydalanish mumkin.[5])

Ko'p kalitli tezkor kortni amaliy tatbiq etish, tezkor kortga tatbiq etiladigan bir xil optimallashtirishdan foyda ko'rishi mumkin: uchdan biriga burilish, o'tish qo'shish tartibi kichik massivlar uchun va boshqalar.[6]

Shuningdek qarang

Izohlar

  1. ^ Qatorlarning xotiradagi ko'rinishini o'zgartirmasdan buni amalga oshirishning usullaridan biri bu ko'rsatkich oralig'idan tashqarida bo'lganda $ -1 $ yoki boshqa kichik qiymatni qaytaradigan funktsiya yordamida ularni indekslashdir.
  2. ^ Massivlar va satrlar nol bilan indekslanadi. An massiv bo'lagi a [i: j) ning subarrayini beradi a dan men ga j (eksklyuziv) va nusxa olinmaydigan, doimiy vaqtdagi operatsiya deb taxmin qilinadi.

Adabiyotlar

  1. ^ Ushbu maqola o'z ichiga oladi jamoat mulki materiallari danNIST hujjat:Qora, Pol E. "multikey Quicksort". Algoritmlar va ma'lumotlar tuzilmalari lug'ati.
  2. ^ Hoare, C. A. R. (1962). "Quicksort". Hisoblash. J. 5 (1): 10–16. doi:10.1093 / comjnl / 5.1.10.
  3. ^ a b v Bentli, Jon; Sedgewick, Robert (1997). Qatorlarni saralash va qidirish uchun tezkor algoritmlar (PDF). Proc. Yillik ACM-SIAM simptomi. Diskret algoritmlar (SODA) bo'yicha. ISBN 0-89871-390-0.
  4. ^ Manzini, Jovanni; Ferragina, Paolo (2004). "Yengil qo'shimchalar qatorini yaratish algoritmini yaratish". Algoritmika. 40: 33–50. CiteSeerX 10.1.1.385.5959. doi:10.1007 / s00453-004-1094-1.
  5. ^ Kim, Yunsang; Park, Kunsoo (2009). "Ko'p teng elementli satrlarni saralash uchun multikey Quicksort-ni takomillashtirish". Axborotni qayta ishlash xatlari. 109 (9): 454–459. doi:10.1016 / j.ipl.2009.01.007.
  6. ^ Bentli, Jon; Sedgewick, Robert (1998). "Uch qatorli Radix Quicksort bilan torlarni saralash". Doktor Dobbning jurnali.