Introsort - Introsort

Introsort
SinfSaralash algoritmi
Ma'lumotlar tarkibiArray
Eng yomoni ishlashO (n jurnal n)
O'rtacha ishlashO (n jurnal n)

Introsort yoki introspektiv tartib a gibrid saralash algoritmi bu o'rtacha tezkor ishlashni ham (asimptotik jihatdan ham) eng yomon ko'rsatkichlarni ham ta'minlaydi. Bu bilan boshlanadi tezkor, u o'zgaradi kassa rekursiya chuqurligi (ga asoslangan darajadan oshganda logaritma ning) saralanadigan elementlar soni va u o'zgaradi qo'shish tartibi elementlar soni biron bir chegaradan pastroq bo'lganda. Bu uchta algoritmning yaxshi qismlarini birlashtiradi va amaliy ko'rsatkichlar odatdagi ma'lumotlar to'plamlari va eng yomon holatlarda tezkor tortishish bilan taqqoslanadi O (n jurnal n) yig'ish tartibiga qarab ish vaqti. U foydalanadigan uchta algoritm bo'lgani uchun taqqoslash turlari, bu shuningdek taqqoslash tartibidir.

Introsort tomonidan ixtiro qilingan Devid Musser yilda Musser (1997), unda u ham tanishtirdi ichki tanlov, gibrid tanlash algoritmi asoslangan tez tanlash (quicksort varianti), bu qaytib keladi medianlar medianasi va shu bilan eng maqbul chiziqli murakkablikni ta'minlaydi. Ikkala algoritm ham taqdim etish maqsadida kiritilgan umumiy algoritmlar uchun C ++ standart kutubxonasi Bu o'rtacha tez ishlashga ham, eng yomon ko'rsatkichlarga ham ega edi, bu esa ishlash talablarini kuchaytirishga imkon berdi.[1] Introsort bu joyida va emas barqaror.[2]

Psevdokod

Agar to'plamni amalga oshirish va qismlarga ajratish funktsiyalari tezkor maqola mavjud, kirish joyini qisqacha ta'riflash mumkin

protsedura saralash (A: qator): ruxsat bering maxdepth = -log (uzunlik (A)) ⌋ × 2 introsort (A, maxdepth)protsedura introsort (A, maksimal chuqurlik): n ← uzunlik (A) agar n-1: qaytish  // asosiy ish    boshqa bo'lsa maxdepth = 0: yig'indisi (A) boshqa: p ← bo'lim (A) // bu funktsiya burilish tanlovini amalga oshiradi, p - burilishning so'nggi pozitsiyasi        introsort (A [0: p-1], maksimal chuqurlik - 1) introsort (A [p + 1: n], maksimal chuqurlik - 1)

Maksimal chuqurlikdagi 2-omil o'zboshimchalik bilan; uni amaliy ishlash uchun sozlash mumkin. A[men:j] belgisini bildiradi massiv bo'lagi buyumlar men ga j.

Tahlil

Quicksort-da muhim operatsiyalardan biri burilishni tanlashdir: ro'yxat bo'linadigan element. Pivotni tanlashning eng oddiy algoritmi - bu ro'yxatning birinchi yoki oxirgi elementini burilish sifatida qabul qilish, bu tartiblangan yoki deyarli saralangan kirish uchun yomon xatti-harakatlarni keltirib chiqaradi. Niklaus Virt Variant bu hodisalarning oldini olish uchun o'rta elementdan foydalanib, O (n2) tuzilgan ketma-ketliklar uchun. Median-of-3 pivotini tanlash algoritmi ro'yxatning birinchi, o'rta va oxirgi elementlarining medianasini oladi; ammo, garchi bu juda ko'p real-dunyodagi ma'lumotlarda yaxshi natijalarga erishsa ham, a ni tuzish mumkin 3-ning o'rtacha qotili ushbu pivot tanlash uslubiga asoslangan holda tezkor kortning sekinlashuviga olib keladigan ro'yxat.

Musserning ta'kidlashicha, 10000 ta elementdan iborat 3-ning o'rtacha qotillari ketma-ketligida introsortning ishlash vaqti 3-ning median-3 kvortortiga nisbatan 1/200 ga teng. Musser shuningdek, ta'sirni ko'rib chiqdi keshlar ning Sedgewick Kechiktirilgan kichik saralash, bu erda kichik diapazonlar oxirida bitta o'tish paytida saralanadi qo'shish tartibi. U keshni o'tkazib yuborish sonini ikki baravar oshirishi mumkinligini aytdi, ammo uning ishlashi ikki tomonlama navbat sezilarli darajada yaxshi edi va shablon kutubxonalarida saqlanishi kerak edi, chunki qisman boshqa hollarda darhol turlarni bajarishdan foyda katta bo'lmagan.

Amaliyotlar

Introsort yoki ba'zi bir variant bir qatorda ishlatiladi standart kutubxona ba'zi funktsiyalarni o'z ichiga olgan tartiblashtirish C ++ saralash amalga oshirish.

2000 yil iyun SGI C ++ Standart shablon kutubxonasi stl_algo.h amalga oshirish beqaror sort Parametr sifatida berilgan xaportga o'tish uchun Musser introsort yondashuvidan rekursiya chuqurligi bilan foydalanadi, 3-ning o'rtasini tanlash va 16-dan kichik bo'linmalar uchun Knuth-ni yakuniy qo'shish tartibini o'tkazish.

The GNU Standard C ++ kutubxonasi o'xshash: maksimal 2 × log chuqurlikdagi introsortdan foydalaniladi2 n, keyin an qo'shish tartibi 16 dan kichik bo'linmalarda.[3]

The Microsoft .NET Framework Sinf kutubxonasi, 4.5 (2012) versiyasidan boshlab, oddiy tezkor kort o'rniga introsortdan foydalaniladi.[4]

Boring kichik modifikatsiyadagi introsortdan foydalanadi: 12 yoki undan kam elementlardan iborat bo'laklar uchun u foydalanadi Shellsort o'rniga qo'shish tartibi, va tezkor tortish uchun uchta burilish tanlovi uchta medianing yanada rivojlangan medianasi.

Adabiyotlar

  1. ^ "Umumiy algoritmlar ", Devid Musser
  2. ^ https://www.geeksforgeeks.org/know-your-sorting-algorithm-set-2-introsort-cs-sorting-weapon/
  3. ^ libstdc ++ Hujjatlar: Algoritmlarni saralash
  4. ^ Array.Sort Method (Array)

Umumiy

  • Musser, Devid R. (1997). "Introspektiv saralash va tanlash algoritmlari". Dasturiy ta'minot: Amaliyot va tajriba. 27 (8): 983–993. doi:10.1002 / (SICI) 1097-024X (199708) 27: 8 <983 :: AID-SPE117> 3.0.CO; 2- #.CS1 maint: ref = harv (havola)
  • Niklaus Virt. Algoritmlar va ma'lumotlar tuzilmalari. Prentice-Hall, Inc., 1985 yil. ISBN  0-13-022005-1.