logo

Timsort saralash algoritmi

Загружено в:

12.08.2023

Скачано:

0

Размер:

491.9736328125 KB
Mavzu: “Timsort saralash algoritmi”
MUNDARIJA
KIRISH .................................................................................................. 2
I Bob.Timsort saralash algoritmining asosiy g’oyasi. ........................... 3
1.1. Pastga tushadigan yugurishlar va minimal yugurish hajmi. ............... 4
1.2. Birlashtirish mezonlari ....................................................................... 6
1.3. Yuqori bo’shliqni birlashtirish. .......................................................... 7
1.4. Birlashtirish paytida yugurish rejimi. ................................................. 9
II Bob.Tahlil. ....................................................................................... 11
2.1.Rasmiy tekshirish. ............................................................................. 11
XULOSA ............................................................................................. 13
 ADABIYOTLAR RO’YXATI ........................................................... 14
ILOVALAR ........................................................................................ 15
ILOVA. TimSort saralash algoritmining c++ tilidagi kodi . ................... 15
1 KIRISH
Timsort   gibrid   ,   barqaror   tartiblash   algoritmi   bo ’ lib ,   birlashtirish   va
qo ’ shish   tartibidan   olingan   bo ’ lib ,   real   ma ʼ lumotlarning   ko ’ p   turlarida
yaxshi   ishlashga   mo ’ ljallangan  . U   Tim   Peters   tomonidan  2002 - yilda   Python
dasturlash   tilida   foydalanish   uchun   amalga   oshirilgan . Algoritm   allaqachon
buyurtma   qilingan   ( ishlaydi )   ma ’ lumotlarning   pastki   ketma - ketligini   topadi
va   qolganlarini   yanada   samaraliroq   saralash   uchun   ulardan   foydalanadi .   U   bu
tartiblangan   elementlarni   " tabiiy   yugurishlar "   deb   ataydi .   Ular   ma ' lumotlar
bo ' ylab   takrorlanadi ,  elementlarni   ketma - ket   to ' playdi   va   bir   vaqtning   o ’ zida
bir   nechtasini   bittaga   birlashtiradi . Bu   muayyan   mezonlar   bajarilgunga   qadar
yugurishlarni   birlashtirish   orqali   amalga   oshiriladi .   Timsort:   juda   tez,
O(n*log   n),   barqaror   tartiblash   algoritmi   akademik   maqsadlar   uchun   emas,
balki real dunyo uchun mo’ljallangan.
Timsort   -   bu   haqiqiy   ma'lumotlarda   samarali   bo’lgan   va   akademik
laboratoriyada yaratilmagan saralash algoritmi.Timsort 2.3 versiyasidan beri
Pythonning   standart   tartiblash   algoritmi   hisoblanadi.U   Android
platformasida   Java   SE   7   da   ibtidoiy   bo’lmagan   massivlarni   saralash   uchun
ham qo’llaniladi. 
Timsort
Sinf-saralash algoritmi;
Ma’lumotlar tuzilishi-massiv;
Eng yomon holatda ishlash murakkabligi-O(n*log n);
Eng yaxshi samaradorlik-O(n);
O’rtacha ishlash murakkabligi-O(n*log n);
U Piter Makilroyning 1993-yilda chop etilgan “Optimistik saralash va
axborot nazariy murakkabligi” nomli maqolasidan foydalanadi. 
2 I Bob.Timsort saralash algoritmining asosiy g’oyasi.
Timsort   ko’pgina   real   dunyo   ma’lumotlarida   mavjud   bo’lgan   ketma-
ket   tartiblangan   elementlarning   ishlashidan   foydalanish   uchun
mo’ljallangan.Ushbu   algoritm   Insertion   Sort   va   Merge   Sort   ga   asoslangan
tartiblash  algoritmi  hisoblanadi.  U  ma’lumotlarni  to’playdigan  elementlarni
ishga   tushiradi   va   bir   vaqtning   o’zida   stackga   joylashtiradi.   Qachonki
stackning   yuqori   qismidagi   yugurishlar   birlashma   mezoniga   mos   kelsa,ular
birlashtiriladi.   Bu   barcha   ma’lumotlar   o’tkazilgunga   qadar   davom
etadi.Keyin,   barcha   yugurishlar   bir   vaqtning   o’zida   ikkitadan   birlashtiriladi
va   faqat   bitta   tartiblangan   yugurish   qoladi.   Ruxsat   etilgan   o’lchamdagi
kichik   ro’yxatlarni   birlashtirish   o’rniga   buyurtma   qilingan   yugurishlarni
birlashtirishning   afzalligi   (an’anaviy   birlashma   tomonidan   bajarilgani   kabi)
butun   ro’yxatni   saralash   uchun   zarur   bo’lgan   taqqoslashlarning   umumiy
sonini kamaytiradi.
Har   bir   ishga   tushirish   minimal   o’lchamga   ega,u   kirish   hajmiga
asoslanadi   va   algoritm   boshida   aniqlanadi.   Agar   yugurish   ushbu   minimal
yugurish   hajmidan   kichikroq   bo’lsa,   qo’shish   tartiblash   minimal   yugurish
hajmiga   erishilgunga   qadar   ishga   qo’shimcha   elementlar   qo’shish   uchun
ishlatiladi.
Algoritm   haqiqiy   dunyoda   tartiblangan   ma’lumotlar   massivida
ko’pincha tartiblangan (o’sish yoki kamayish bo’yicha muhim emas) pastki
qatorlarni o’z ichiga oladi degan fikrga asoslanadi. Darhaqiqat, bu ko’pincha
shunday   bo’ladi.   Bunday   ma’lumotlarga   ko’ra,   Timsort   boshqa   barcha
algoritmlarni parchalab tashlaydi.
Bu   erda   ba’zi   murakkab   matematik   kashfiyotlar   kutmang.   Gap
shundaki, aslida Timsort butunlay mustaqil algoritm emas, balki gibrid, o’z
g’oyalari   bilan   tajriba   qilingan   bir   qancha   boshqa   algoritmlarning   samarali
kombinatsiyasi.   Juda   qisqacha,   algoritmning   mohiyatini   quyidagicha
tushuntirish mumkin:
Algoritmning asosiy g’oyasi:
.   Maxsus   algoritmga   ko’ra,   kirish   massivi   pastki   massivlarga
bo’linadi.
. Har bir pastki qator qo’shish tartibi bo’yicha tartiblangan.
. Tartiblangan   pastki   qatorlar   o’zgartirilgan   birlashma   tartiblash
yordamida bitta massivga yig’iladi.
3 1.1. Pastga tushadigan yugurishlar va minimal yugurish hajmi.
Amaldagi tushunchalar:
.  N-kirish massivining o’lchami
.   run-kirish   massividagi   tartiblangan   pastki   qator.Bundan   tashqari
qat’iy ravishda ko’tarilish yoki qat’iy ravishda tushish buyuriladi.
.   minrun   -   yuqorida   aytib   o'tilganidek,   algoritmning   birinchi
bosqichida   kirish   massivi   pastki   massivlarga   bo'linadi.   minrun   -   bunday
pastki qatorning minimal hajmi. Bu raqam N raqamidan ma'lum bir mantiq
bo’yicha hisoblanadi.
I.1.1-rasm minRUNni hisoblash
Minrunni hisoblash tartibi:
Minrunlar   soni   N   ga   qarab   quyidagi   printsiplarga   asoslanib
aniqlanadi :
1.U   juda   katta   bo’lmasligi   kerak,   chunki   qo’shish   tartiblash   minrun
o’lchamli   kichik   massivga   keyinroq   qo’llaniladi   va   u   faqat   kichik
massivlarda samarali bo’ladi.
2.U   juda   kichik   bo'lmasligi   kerak,   chunki   pastki   qator   qanchalik
kichik   bo’lsa,   algoritmning   oxirgi   bosqichida   pastki   qatorlarni
birlashtirishning ko’proq takrorlanishi kerak bo'ladi.
3.N\minrun 2 ning (yoki unga yaqin) kuchi bo’lsa yaxshi bo’lardi . Bu
talab   pastki   massivlarni   birlashtirish   algoritmining   taxminan   teng
o’lchamdagi pastki massivlarda eng samarali ishlashi bilan bog'liq.
Shu nuqtada, algoritm muallifi o’z tajribalariga murojaat qiladi, bu 1-
band   minrun   >   256   bilan   buzilganligini,   2-band   minrun   <   8   bilan
buzilganligini   va   diapazondagi   qiymatlardan   foydalanish   eng   samarali
ekanligini   ko’rsatdi   (   32;65).   Istisno,   agar   N   <   64   bo’lsa,   minrun   =   N   va
timsort  oddiy kiritish tartibiga aylanadi. Hozirgi  vaqtda minrunni  hisoblash
4 algoritmini   sharmanda  qilish  oson:  biz  N dan  eng  yuqori   6 bitni  olamiz  va
qolgan   eng   kam   ahamiyatli   bitlarda   kamida   bitta   nolga   teng   bo’lmagan
bo’lsa, bittasini qo’shamiz. Misol kodi quyidagicha ko’rinadi:
int GetMinrun(int n)
 {
         int r = 0;                     /* agar o‘zgartirilgan bitlar orasida1 nolga teng
bo‘lmagani bo‘lsa 0 ga aylanadi*/
     while (n >= 64) {
         r |= n & 1;
         n >>= 1;
     }
     return n + r;
 }
Quyi massivlarga ajratish va ularni saralash.
Shunday   qilib,   ushbu   bosqichda   bizda   kirish   massivi   mavjud,   uning
o’lchami N va hisoblangan minrun soni . Ushbu bosqich uchun algoritm:
1.Joriy element ko’rsatkichini kirish massivining boshiga qo’yamiz.
2.Joriy   elementdan   boshlab,   ishga   tushirish   uchun   kirish   massivini
qidiring (tartib qilingan pastki qator). Ta’rifga ko’ra, bu yugurish aniq joriy
elementni   va   keyingi   elementni   o’z   ichiga   oladi,   ammo   bundan   keyin   -
omadli.   Agar   hosil   bo’lgan   pastki   qator   kamayish   tartibida   tartiblangan
bo’lsa,   biz   elementlarni   o’sish   tartibida   bo’ladigan   tarzda   qayta
joylashtiramiz   (bu   oddiy   chiziqli   algoritm,   biz   elementlarni   almashtirib,
ikkala uchidan o’rtasiga o’tamiz).
3.Agar   joriy   yugurish   a   hajmi   minrun   dan   kichik   bo’lsa,topilgan
yugurishdan   keyingi   elementlarni   minrun   —   size(run)   miqdorida
olamiz.Shunday   qilib,   chiqishda   biz   minrun   yoki   undan   ortiq   o’lchamdagi
pastki   qatorni   olamiz,  uning   bir   qismi   (va   ideal   holda,   hammasi)   buyurtma
qilinadi.
4.Ushbu   pastki   qatorga   qo’shish   tartibini   qo’llang.   Pastki   qatorning
o’lchami kichik va uning bir qismi allaqachon buyurtma qilinganligi sababli,
saralash tez va samarali bo’ladi.
5.Joriy elementning ko’rsatkichini  pastki  qatordan keyingi  elementga
o’rnatamiz.
6.Agar kirish massivining oxiriga yetib borilmasa,2-bosqichga o’ting,
aks holda ushbu bosqichni tugating.
5 1.2. Birlashtirish mezonlari
Ushbu   bosqichda   bizda   har   biri   tartiblangan   pastki   massivlarga
bo’lingan kirish massivi  mavjud. Agar kirish massiv ma’lumotlari tasodifiy
ma’lumotlarga   yaqin   bo’lsa   -   tartiblangan   pastki   massivlarning   o’lchami
minrun   ga   yaqin   bo’lsa,agar   ma’lumotlar   tartiblangan   diapazonlarni   o’z
ichiga olgan bo’lsa (va algoritmni  qo’llash bo’yicha tavsiyalarga  asoslanib,
bizda shunday deb umid qilish uchun asos bor) - buyurtma qilingan. Pastki
qatorlar minrun dan kattaroq hajmga ega .
Endi   biz   to’liq   tartiblangan   massivni   olish   uchun   ushbu   pastki
qatorlarni   birlashtirishimiz   kerak.   Bundan   tashqari,   ushbu   assotsiatsiya
jarayonida ikkita talab bajarilishi kerak:
1.Taxminan   teng   o’lchamdagi   pastki   qatorlarni   birlashtiring   (bu
samaraliroq).
2.Algoritmning   barqarorligini   saqlang   –   ya’ni   ma’nosiz
almashtirishlarni   qilmang   (masalan,   ikkita   ketma-ket   bir   xil   sonni   joylarda
o’zgartirmang).
Bunga shu tarzda erishiladi:
1.<subbarray   start   index>-<subarray   size>   juftliklaridan   iborat   bo’sh
stack yarating. Biz birinchi buyurtma qilingan pastki qatorni olamiz.
2.Joriy kichik massiv uchun <start index>-<size> ma’lumotlar  juftini
stackga suramiz.
3.Joriy   pastki   qatorni   oldingilar   bilan   birlashtirish   protsedurasini
bajarish   zarurligini   aniqlaymiz.   Buning   uchun   2   ta   qoidaning   bajarilishi
tekshiriladi   (X,   Y   va   Z   stackdagi   eng   yuqori   uchta   pastki   massivlarning
o‘lchamlari bo‘lsin):
X > Y + Z
Y > Z
4.Agar   qoidalardan   biri   buzilgan   bo’lsa,   Y   massivi   X   va   Z
massivlarning   kichigi   bilan   birlashtiriladi.U   ikkala   qoida   bajarilmaguncha
yoki ma’lumotlar to’liq tartibga solinmaguncha takrorlanadi.
5.Agar   hali   ko’rib   chiqilmagan   pastki   qatorlar   mavjud   bo’lsa,   biz
keyingisini olib, 2-bosqichga o’tamiz. Aks holda, oxiri.
6 I.2.2-rasm.Ushbu   murakkab   protseduraning   maqsadi   muvozanatni   saqlashdir.
Bular o’zgarishlar quyidagicha ko’rinadi:
bu   stackdagi   pastki   qatorlarning   o’lchamlari   keyingi   birlashtirish
saralash   uchun   samarali   ekanligini   anglatadi.   Ideal   holatni   tasavvur   qiling:
bizda   128,   64,   32,   16,   8,   4,   2,   2   o’lchamdagi   pastki   qatorlar   mavjud   (bir
soniyaga “pastki qator hajmi >= minrun” talabini unuting ) . Bunday holda,
oxirgi   2   ta   pastki   qatorlar   uchrashgunga   qadar   hech   qanday   birlashma
amalga   oshirilmaydi,   lekin   undan   keyin   7   ta   mukammal   muvozanatli
birlashma amalga oshiriladi.
1.3. Yuqori bo’shliqni birlashtirish.
Yuqori bo’shliqni birlashtiring:
7 I.3.3-rasm   Birlashtirish uchun Timsort kichikroq massivning elementlarini (ushbu
rasmda X) vaqtinchalik xotiraga ko’chiradi, so’ngra elementlarni oxirgi tartibda saralaydi
va X va Y ning birlashtirilgan maydoniga to’ldiradi.
Asl   birlashma   tartibini   amalga   oshirish   joyida   emas   va   unda   N
(ma'lumotlar   hajmi)   bo’sh   joy   mavjud.   Joyda   birlashma   tartiblash   ilovalari
mavjud, ammo ko’p vaqt sarflanadi. O’rta muddatga erishish uchun Timsort
N   ga   qaraganda   kichikroq   vaqt   va   kichikroq   bo’sh   joy   bilan   birlashtirishni
amalga oshiradi.
Birinchidan, Timsort ikkilik qidiruvni amalga oshiradi tartibni saqlab,
ikkinchi   ishga   tushirishning   birinchi   elementi   birinchi   tartiblangan   ishga
qo’yiladigan   joyni   topish   uchun.   Keyin   u   xuddi   shu   algoritmni   bajarib,
birinchi   ishga   tushirishning   oxirgi   elementi   ikkinchi   tartibli   ishga
qo’yiladigan   joyni   topadi   va   tartibni   saqlaydi.   Ushbu   joylashuvdan   oldingi
va   keyingi   elementlar   allaqachon   o’z   joyida   va   ularni   birlashtirish   shart
emas.   Keyin,   ikkita   ishga   tushirishning   qolgan   elementlaridan   kichikrog’i
vaqtinchalik   xotiraga   ko’chiriladi   va   elementlar   kattaroq   bo’sh   joyga
birlashtiriladi.   Agar   birinchi   yugurish   kichikroq   bo’lsa,   birlashma   boshidan
boshlanadi; ikkinchisi kichikroq bo’lsa, birlashma oxirida boshlanadi. Ushbu
optimallashtirish   talab   qilinadigan   elementlarning   harakatlanish   sonini,   ish
vaqtini va umumiy holatda vaqtinchalik bo’sh joyni kamaytiradi.
Misol:   ikkita   yugurish   [1,   2,   3,   6,   10]   va   [4,   5,   7,   9,   12,   14,   17]
birlashtirilishi   kerak.   E’tibor   bering,   ikkala   ishga   tushirish   allaqachon
alohida tartiblangan. Ikkinchi yugurishning eng kichik elementi 4 ga teng va
uning   tartibini   saqlab   qolish   uchun   uni   birinchi   yugurishning   to’rtinchi
pozitsiyasiga   qo’shish   kerak   bo’ladi   (yugurishning   birinchi   pozitsiyasi   1
bo'lsa).   Birinchi   yugurishning   eng   katta   elementi   10   ga   teng   va   uning
tartibini   saqlab   qolish   uchun   uni   ikkinchi   yugurishning   beshinchi
pozitsiyasiga qo’shish kerak bo’ladi. Shunday qilib, [1, 2, 3] va [12, 14, 17]
allaqachon   yakuniy   pozitsiyalarida   va   elementlarning   harakati   talab
qilinadigan yugurishlar [6, 10] va [4, 5, 7, 9]. Ushbu bilim bilan biz faqat 4
o’rniga 2 o’lchamdagi vaqtinchalik buferni ajratishimiz kerak.
Birlashtirish   yo’nalishi-birlashtirish   har   ikki   yo’nalishda   hamamalga
oshirilishi   mumkin:an’anaviy   birlashmadagi   kabi   chapdan   o’nga   yoki
o’ngdan chapga.
8 1.4. Birlashtirish paytida yugurish rejimi.
I.4.4-rasm.Elementlar   (ko’k   o’q   bilan   ko’rsatilgan)   taqqoslanadi   va   kichikroq
element oxirgi holatiga o’tkaziladi (qizil o’q bilan ko’rsatilgan).
R1 va R2 yugurishlarining individual birlashuvi yugurishdan tanlangan ketma-ket
elementlarning sonini saqlaydi. Bu raqam minimal yugurish chegarasiga ( min_gallop )
yetganda,Timsort ko’plab ketma-ket elementlar hali ham ushbu yugurishdan tanlanishi
mumkin   deb   hisoblaydi   va   yugurish   rejimiga   o’tadi.   Faraz   qilaylik,   R1   uni   ishga
tushirish uchun javobgardir. Ushbu rejimda algoritm R1 ishidagi R2 ishining keyingi x
elementi   uchun   galloping   qidiruvi   deb   ham   ataladigan   eksponensial   qidiruvni   amalga
oshiradi. Bu ikki bosqichda amalga oshiriladi: birinchisi diapazonni topadi (2  k
- 1, 2  k+1
-
1) bu erda x. Ikkinchi bosqich birinchi bosqichda topilgan diapazonda x elementi uchun
binar   qidiruvni   amalga   oshiradi.   Galloping   rejimi   -   bu   birlashma   algoritmini
yugurishdagi elementlar orasidagi intervallar naqshiga moslashtirishga urinish.
9 I.4.5-rasmBarcha qizil elementlar ko’kdan kichikroq (bu yerda, 21). Shunday qilib, ular oxirgi
massivga bo’linib ko’chirilishi mumkin.
Yugurish   har   doim   ham   samarali   emas.   Ba’zi   hollarda   galloping   rejimi   oddiy
chiziqli qidiruvdan ko’ra ko’proq taqqoslashni talab qiladi. Ishlab chiquvchi tomonidan
amalga   oshirilgan   mezonlarga   ko’ra,   bir   yugurishning   boshlang’ich   elementi   boshqa
yugurishning dastlabki yetti elementidan biri bo’lmasa, galloping foydali bo’ladi. Bu 7
boshlang'ich chegarani nazarda tutadi. Galloping rejimining kamchiliklarini oldini olish
uchun ikkita harakat amalga oshiriladi: 
(1) Galloping ikkilik qidiruvga qaraganda kamroq samarali deb topilsa, galloping
rejimidan chiqadi. 
(2)   Gallopning   muvaffaqiyati   yoki   muvaffaqiyatsizligi   min_gallop   ni   sozlash
uchun ishlatiladi.
Agar tanlangan element elementni avval qaytargan massivdan bo’lsa, min_gallop
bittaga   qisqaradi,   shuning   uchun   galloping   rejimiga   qaytishni   rag’batlantiradi.   Aks
holda, qiymat bittaga oshiriladi, shuning uchun galloping rejimiga qaytishga to’sqinlik
qiladi.   Tasodifiy   ma’lumotlar   bo’lsa,   min_gallop   qiymati   shunchalik   katta   bo’ladiki,
galloping rejimi hech qachon takrorlanmaydi.
Shuningdek,   kamayish   tartibida   tartiblangan   ma’lumotlardan   foydalanish   uchun
Timsort   ularni   topgach,   ularni   qat’iy   ravishda   kamayib   boruvchi   yugurishlarni
o’zgartiradi va ularni yugurishlar to’plamiga qo’shadi.
  Tushuvchi yugurishlar keyinchalik ko’r-ko’rona teskari bo’lganligi sababli, teng
elementlarga   ega   yugurishlarni   hisobga   olmaganda,   algoritm   barqarorligi   saqlanib
qoladi ya'ni teng elementlar teskari bo’lmaydi.
10 II Bob.Tahlil.
Eng yomon holatda , Timsort oladi O(n*log n) n ta elementdan iborat
massivni  saralash  uchun taqqoslash  . Eng yaxshi  holatda, kirish allaqachon
tartiblangan   bo’lsa,   u   chiziqli   vaqtda   ishlaydi,   ya’ni   bu   moslashuvchan
tartiblash algoritmidir.
Obyekt   havolalari   yoki   ko’rsatkichlarini   saralash   uchun   Quicksort-dan
ustundir,   chunki   ular   ma’lumotlarga   kirish   va   taqqoslash   uchun   qimmat
xotirani bilvosita talab qiladi va Quicksort-ning kesh muvofiqligi afzalliklari
sezilarli darajada kamayadi.
2.1.Rasmiy tekshirish.
2015-yilda   EI   FP7   ENVISAGE   loyihasida   Gollandiyalik   va
Germaniyalik tadqiqotchilar Timsort standartini amalga oshirishda xatolikni
aniqladilar. 
 U 2015-yilda Python, Java va Android-da tuzatilgan.
Xususan,   stackda   yugurish   o’lchamlaridagi   o’zgarmasliklar   kerakli
stackning maksimal o’lchamiga qattiq yuqori chegarani ta’minlaydi. Amalga
oshirish                          2   64  
bayt     kirishni  saralash   uchun yetarli   bo’lgan  stackni
oldindan ajratadi va keyingi ortiqcha tekshiruvlardan qochadi.
Biroq,   kafolat   o’zgarmaslardan   ketma-ket   uchta   yugurishning   har   bir
guruhiga   qo’llanilishini   talab   qiladi,ammo   amalga   oshirish   uni   faqat   eng
yaxshi uchtalik uchun tekshiradi.Java dasturiy ta’minotini rasmiy tekshirish
uchun   KeyY   vositasidan   foydalanib   ,   tadqiqotchilar   bu   tekshirish   yetarli
emasligini aniqladilar va ular o’zgarmasliklarning chuqurroq buzilishiga olib
keladigan ish uzunligini (va shu ish uzunligini yaratgan kirishlarni) topishga
muvaffaq bo’lishdi. 
Natijada,   ma’lum   kirishlar   uchun   ajratilgan   o’lcham   barcha
birlashtirilmagan yugurishlarni  ushlab  turish uchun  yetarli  emas.  Javada  bu
kirishlar uchun massivdan tashqarida istisno hosil qiladi. Java va Android v7
da   ushbu   istisnoni   ishga   tushiradigan   eng   kichik   kiritish   hajmi   katta.
(Androidning   eski   versiyalari   ma’lum   hajmdagi   kirishlar   uchun   ushbu
istisnoni allaqachon ishga tushirgan.
Java   ilovasi   yangilangan   eng   yomon   holatlar   tahlili   asosida   oldindan
ajratilgan   stack   hajmini   oshirish   orqali   tuzatildi.   Maqolada,   shuningdek   ,
stackdagi   to’rtta   eng   yuqori   yugurish   yuqoridagi   ikkita   qoidaga   mos
kelishini   tekshirish   orqali   mo’ljallangan   invariantni   qanday   o’rnatishni
11 rasmiy   usullar   bilan   ko’rsatdi   .   Ushbu   yondashuv   Python   [16]   va   Android
tomonidan qabul qilingan.
12 XULOSA
Xulosa   qilib   aytganda,   asosiy   tartib   massiv   bo‘ylab   chapdan   o‘ngga
bir   marta  o‘tadi,navbatma-navbat  keyingi   yugurishni  aniqlaydi,  so’ngra  uni
oldingisiga   birlashtiradi"aqlli"   ishlaydi.   Qolgan   hamma   narsa   tezlik   uchun
murakkab, ba’zilari esa xotira samaradorligining qiyin o’lchovi..
Timsort   gibrid   ,   barqaror   tartiblash   algoritmi   bo’lib,   birlashtirish   va
qo’shish   tartibidan   olingan   bo’lib,   real   ma lumotlarning   ko’p   turlaridaʼ
yaxshi ishlashga mo’ljallangan .U Tim Peters tomonidan 2002 -yilda Python
dasturlash   tilida   foydalanish   uchun   amalga   oshirilgan.Algoritm   allaqachon
buyurtma   qilingan   (ishlaydi)   ma’lumotlarning   pastki   ketma-ketligini   topadi
va qolganlarini yanada samaraliroq saralash uchun ulardan foydalanadi.   U bu
tartiblangan   elementlarni   "tabiiy   yugurishlar"   deb   ataydi.   Ular   ma'lumotlar
bo'ylab takrorlanadi, elementlarni ketma-ket to'playdi va bir vaqtning o’zida
bir nechtasini bittaga birlashtiradi.Bu muayyan mezonlar bajarilgunga qadar
yugurishlarni   birlashtirish   orqali   amalga   oshiriladi.   Timsort:   juda   tez,
O(n*log   n),   barqaror   tartiblash   algoritmi   akademik   maqsadlar   uchun   emas,
balki real dunyo uchun mo’ljallangan.
Timsort   -   bu   haqiqiy   ma'lumotlarda   samarali   bo’lgan   va   akademik
laboratoriyada yaratilmagan saralash algoritmi.Timsort 2.3 versiyasidan beri
Pythonning standart tartiblash algoritmi hisoblanadi.
13 ADABIYOTLAR RO’YXATI
1.  Misy   E   Vermaat,   Susan   L   Sebok,   Steven   M   Freund.   Discovering
Computers (C)2016 (2016 edition). Textbook.USA, 2016.
2.  Mamarajabov   M.,   Tursunov   S.   Kompyuter   grafikasi   va   Web   dizayn:
Darslik.  T.: Cho‘lpon, 2013.
3. https :// en . wikipedia . org / wiki / Timsort # Minimum _ size _.28 minrun .29
4.Auger,   Nikolay;   Nikod,   Kiril;   Pivoteau,   Carine   (2015).   "Birlashtirish
strategiyalari: Birlashtirish tartibidan TimSortgacha" . hal-01212839 .
5.Auger,   Juge,   Nicaud,   Pivoteau   (2018).   "TimSortning   eng   yomon
murakkabligi to'g'risida" . ESA 2018.
6.Sem   Buss,   Aleksandr   Knop.   "Barqaror   birlashmalarni   saralash
strategiyalari". SODA 2019
7. https://library.ziyonet.uz/uz/book/126181
8. https://library.ziyonet.uz/uz/book/index?Book%5Blevel_id%5D=&Book
%5Btype_id%5D=1&Book%5Bcategory_id%5D=53&Book%5Btitle
%5D=&Book%5Bdescription%5D=&Book%5Blanguage_id%5D=&yt0=Qidiruv  
9.   https://svn.python.org/projects/python/trunk/Objects/listsort.txt
10.https://en.wikipedia.org/wiki/Timsort#Minimum_size_.28minrun.2
14 ILOVALAR
ILOVA. TimSort saralash algoritmining c++ tilidagi kodi .  
// TimSort ni bajarish uchun C++ dasturi.
#include<bits/stdc++.h>
using namespace std;
const int RUN = 32;  // o'zgarmas son
// Bu funksiya massivni chap indeksdan o’ng indeksga saralaydi,uning
hajmi RUN//
void insertionSort(int arr[], int left, int right)
{
    for (int i = left + 1; i <= right; i++)
    {
        int temp = arr[i];  // massiv elon qilish
        int j = i - 1;
                while   (j   >=   left   &&   arr[j]   >   temp)   //   takrorlanuvchi   jarayon
yolg'on bo'lsagina tugaydi
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }
}
//Birlashtirish funksiyasi tartiblangan yugurishlarni birlashtiradi//
void merge(int arr[], int l, int m, int r)
{
    // Asl massiv ikki qismga bo’lingan
15     // Chap va o’ng massiv
    int len1 = m - l + 1, len2 = r - m;
    int left[len1], right[len2];
    for (int i = 0; i < len1; i++)
        left[i] = arr[l + i];
    for (int i = 0; i < len2; i++)
        right[i] = arr[m + 1 + i];
    int i = 0;
    int j = 0;
    int k = l;
    // Taqqoslashdan keyin, biz
    //bu ikkita massivni birlashtirdik
    // kattaroq kichik massivda
    while (i < len1 && j < len2)
    {
        if (left[i] <= right[j])
        {
            arr[k] = left[i];
            i++;
        }
        else
        {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
16     // agar mavjud bo’lsa,chapning qolgan elementlarini nusxalash
    while (i < len1)
    {
        arr[k] = left[i];
        k++;
        i++;
    }
    // Agar mavjud bo’lsa uning qolgan elementlarini nusxalash
    while (j < len2)
    {
        arr[k] = right[j];
        k++;
        j++;
    }
}
// massivni saralash uchun iterativ Timsort
// funksiyasi[0...n-1] (birlashtirib tartiblash kabi)
void timSort(int arr[], int n)
{
    //RUN o’lchamidagi alohida pastki massivlarni saralash
    for (int i = 0; i < n; i+=RUN)
        insertionSort(arr, i, min((i+RUN-1), (n-1)));
    // RUN (yoki 32) o’lchamidan birlashtirishni boshlang
    // U birlashadi
    // 64,keyin 128, 256 o’lchamini shakllantirish uchun
    // va hakozo....
    for (int size = RUN; size < n; size = 2*size)
17     {
        // boshlanish nuqtasini tanlang
        // chap pastki qator birlashtiriladi
        // arr[left..left+size-1]
        // and arr[left+size, left+2*size-1]
        //Har bir birlashgandan keyin chap tomonni 2 o’lchamga oshiring
for (int left = 0; left < n;left += 2*size)
{
        // tugash nuqtasini toping
       // chap pastki massiv
      // o’rta(mid)+1 boshlang’ich nuqta
    // o’ng pastki qator
            int mid = left + size - 1;
            int right = min((left + 2*size - 1), (n-1));
            // sub massivni birlashtirish[left.....mid] &
            // arr[mid+1....o’ng],right(o’ng)
              if(mid < right)
                merge(arr, left, mid, right);
        }
    }
}
// Massivni chop etish uchun yordamchi dastur
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d  ", arr[i]);
  printf("\n");
}
18 // yuqoridagi funksiyani sinab ko’rish uchun dastur
int main()
{
    int arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7,-4, -13, 5, 8, -14, 12};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Berilgan massiv ko'rinishi: ");
    printArray(arr, n);
    // Cal funksiya
 timSort(arr, n);
    printf("Saralangan massiv ko'rinishi: ");
    printArray(arr, n);
    return 0;
}
6-rasm.Kodning natijasi
19

Mavzu: “Timsort saralash algoritmi” MUNDARIJA KIRISH .................................................................................................. 2 I Bob.Timsort saralash algoritmining asosiy g’oyasi. ........................... 3 1.1. Pastga tushadigan yugurishlar va minimal yugurish hajmi. ............... 4 1.2. Birlashtirish mezonlari ....................................................................... 6 1.3. Yuqori bo’shliqni birlashtirish. .......................................................... 7 1.4. Birlashtirish paytida yugurish rejimi. ................................................. 9 II Bob.Tahlil. ....................................................................................... 11 2.1.Rasmiy tekshirish. ............................................................................. 11 XULOSA ............................................................................................. 13 ADABIYOTLAR RO’YXATI ........................................................... 14 ILOVALAR ........................................................................................ 15 ILOVA. TimSort saralash algoritmining c++ tilidagi kodi . ................... 15 1

KIRISH Timsort gibrid , barqaror tartiblash algoritmi bo ’ lib , birlashtirish va qo ’ shish tartibidan olingan bo ’ lib , real ma ʼ lumotlarning ko ’ p turlarida yaxshi ishlashga mo ’ ljallangan . U Tim Peters tomonidan 2002 - yilda Python dasturlash tilida foydalanish uchun amalga oshirilgan . Algoritm allaqachon buyurtma qilingan ( ishlaydi ) ma ’ lumotlarning pastki ketma - ketligini topadi va qolganlarini yanada samaraliroq saralash uchun ulardan foydalanadi . U bu tartiblangan elementlarni " tabiiy yugurishlar " deb ataydi . Ular ma ' lumotlar bo ' ylab takrorlanadi , elementlarni ketma - ket to ' playdi va bir vaqtning o ’ zida bir nechtasini bittaga birlashtiradi . Bu muayyan mezonlar bajarilgunga qadar yugurishlarni birlashtirish orqali amalga oshiriladi . Timsort: juda tez, O(n*log n), barqaror tartiblash algoritmi akademik maqsadlar uchun emas, balki real dunyo uchun mo’ljallangan. Timsort - bu haqiqiy ma'lumotlarda samarali bo’lgan va akademik laboratoriyada yaratilmagan saralash algoritmi.Timsort 2.3 versiyasidan beri Pythonning standart tartiblash algoritmi hisoblanadi.U Android platformasida Java SE 7 da ibtidoiy bo’lmagan massivlarni saralash uchun ham qo’llaniladi. Timsort Sinf-saralash algoritmi; Ma’lumotlar tuzilishi-massiv; Eng yomon holatda ishlash murakkabligi-O(n*log n); Eng yaxshi samaradorlik-O(n); O’rtacha ishlash murakkabligi-O(n*log n); U Piter Makilroyning 1993-yilda chop etilgan “Optimistik saralash va axborot nazariy murakkabligi” nomli maqolasidan foydalanadi. 2

I Bob.Timsort saralash algoritmining asosiy g’oyasi. Timsort ko’pgina real dunyo ma’lumotlarida mavjud bo’lgan ketma- ket tartiblangan elementlarning ishlashidan foydalanish uchun mo’ljallangan.Ushbu algoritm Insertion Sort va Merge Sort ga asoslangan tartiblash algoritmi hisoblanadi. U ma’lumotlarni to’playdigan elementlarni ishga tushiradi va bir vaqtning o’zida stackga joylashtiradi. Qachonki stackning yuqori qismidagi yugurishlar birlashma mezoniga mos kelsa,ular birlashtiriladi. Bu barcha ma’lumotlar o’tkazilgunga qadar davom etadi.Keyin, barcha yugurishlar bir vaqtning o’zida ikkitadan birlashtiriladi va faqat bitta tartiblangan yugurish qoladi. Ruxsat etilgan o’lchamdagi kichik ro’yxatlarni birlashtirish o’rniga buyurtma qilingan yugurishlarni birlashtirishning afzalligi (an’anaviy birlashma tomonidan bajarilgani kabi) butun ro’yxatni saralash uchun zarur bo’lgan taqqoslashlarning umumiy sonini kamaytiradi. Har bir ishga tushirish minimal o’lchamga ega,u kirish hajmiga asoslanadi va algoritm boshida aniqlanadi. Agar yugurish ushbu minimal yugurish hajmidan kichikroq bo’lsa, qo’shish tartiblash minimal yugurish hajmiga erishilgunga qadar ishga qo’shimcha elementlar qo’shish uchun ishlatiladi. Algoritm haqiqiy dunyoda tartiblangan ma’lumotlar massivida ko’pincha tartiblangan (o’sish yoki kamayish bo’yicha muhim emas) pastki qatorlarni o’z ichiga oladi degan fikrga asoslanadi. Darhaqiqat, bu ko’pincha shunday bo’ladi. Bunday ma’lumotlarga ko’ra, Timsort boshqa barcha algoritmlarni parchalab tashlaydi. Bu erda ba’zi murakkab matematik kashfiyotlar kutmang. Gap shundaki, aslida Timsort butunlay mustaqil algoritm emas, balki gibrid, o’z g’oyalari bilan tajriba qilingan bir qancha boshqa algoritmlarning samarali kombinatsiyasi. Juda qisqacha, algoritmning mohiyatini quyidagicha tushuntirish mumkin: Algoritmning asosiy g’oyasi: . Maxsus algoritmga ko’ra, kirish massivi pastki massivlarga bo’linadi. . Har bir pastki qator qo’shish tartibi bo’yicha tartiblangan. . Tartiblangan pastki qatorlar o’zgartirilgan birlashma tartiblash yordamida bitta massivga yig’iladi. 3

1.1. Pastga tushadigan yugurishlar va minimal yugurish hajmi. Amaldagi tushunchalar: . N-kirish massivining o’lchami . run-kirish massividagi tartiblangan pastki qator.Bundan tashqari qat’iy ravishda ko’tarilish yoki qat’iy ravishda tushish buyuriladi. . minrun - yuqorida aytib o'tilganidek, algoritmning birinchi bosqichida kirish massivi pastki massivlarga bo'linadi. minrun - bunday pastki qatorning minimal hajmi. Bu raqam N raqamidan ma'lum bir mantiq bo’yicha hisoblanadi. I.1.1-rasm minRUNni hisoblash Minrunni hisoblash tartibi: Minrunlar soni N ga qarab quyidagi printsiplarga asoslanib aniqlanadi : 1.U juda katta bo’lmasligi kerak, chunki qo’shish tartiblash minrun o’lchamli kichik massivga keyinroq qo’llaniladi va u faqat kichik massivlarda samarali bo’ladi. 2.U juda kichik bo'lmasligi kerak, chunki pastki qator qanchalik kichik bo’lsa, algoritmning oxirgi bosqichida pastki qatorlarni birlashtirishning ko’proq takrorlanishi kerak bo'ladi. 3.N\minrun 2 ning (yoki unga yaqin) kuchi bo’lsa yaxshi bo’lardi . Bu talab pastki massivlarni birlashtirish algoritmining taxminan teng o’lchamdagi pastki massivlarda eng samarali ishlashi bilan bog'liq. Shu nuqtada, algoritm muallifi o’z tajribalariga murojaat qiladi, bu 1- band minrun > 256 bilan buzilganligini, 2-band minrun < 8 bilan buzilganligini va diapazondagi qiymatlardan foydalanish eng samarali ekanligini ko’rsatdi ( 32;65). Istisno, agar N < 64 bo’lsa, minrun = N va timsort oddiy kiritish tartibiga aylanadi. Hozirgi vaqtda minrunni hisoblash 4

algoritmini sharmanda qilish oson: biz N dan eng yuqori 6 bitni olamiz va qolgan eng kam ahamiyatli bitlarda kamida bitta nolga teng bo’lmagan bo’lsa, bittasini qo’shamiz. Misol kodi quyidagicha ko’rinadi: int GetMinrun(int n) { int r = 0; /* agar o‘zgartirilgan bitlar orasida1 nolga teng bo‘lmagani bo‘lsa 0 ga aylanadi*/ while (n >= 64) { r |= n & 1; n >>= 1; } return n + r; } Quyi massivlarga ajratish va ularni saralash. Shunday qilib, ushbu bosqichda bizda kirish massivi mavjud, uning o’lchami N va hisoblangan minrun soni . Ushbu bosqich uchun algoritm: 1.Joriy element ko’rsatkichini kirish massivining boshiga qo’yamiz. 2.Joriy elementdan boshlab, ishga tushirish uchun kirish massivini qidiring (tartib qilingan pastki qator). Ta’rifga ko’ra, bu yugurish aniq joriy elementni va keyingi elementni o’z ichiga oladi, ammo bundan keyin - omadli. Agar hosil bo’lgan pastki qator kamayish tartibida tartiblangan bo’lsa, biz elementlarni o’sish tartibida bo’ladigan tarzda qayta joylashtiramiz (bu oddiy chiziqli algoritm, biz elementlarni almashtirib, ikkala uchidan o’rtasiga o’tamiz). 3.Agar joriy yugurish a hajmi minrun dan kichik bo’lsa,topilgan yugurishdan keyingi elementlarni minrun — size(run) miqdorida olamiz.Shunday qilib, chiqishda biz minrun yoki undan ortiq o’lchamdagi pastki qatorni olamiz, uning bir qismi (va ideal holda, hammasi) buyurtma qilinadi. 4.Ushbu pastki qatorga qo’shish tartibini qo’llang. Pastki qatorning o’lchami kichik va uning bir qismi allaqachon buyurtma qilinganligi sababli, saralash tez va samarali bo’ladi. 5.Joriy elementning ko’rsatkichini pastki qatordan keyingi elementga o’rnatamiz. 6.Agar kirish massivining oxiriga yetib borilmasa,2-bosqichga o’ting, aks holda ushbu bosqichni tugating. 5