Timsort saralash algoritmi
![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](/data/documents/9a9a16b2-364e-49ac-962e-f5c0ddf31239/page_8.png)
![rasmiy usullar bilan ko’rsatdi . Ushbu yondashuv Python [16] va Android
tomonidan qabul qilingan.
12](/data/documents/9a9a16b2-364e-49ac-962e-f5c0ddf31239/page_12.png)
![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](/data/documents/9a9a16b2-364e-49ac-962e-f5c0ddf31239/page_15.png)
![// 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](/data/documents/9a9a16b2-364e-49ac-962e-f5c0ddf31239/page_16.png)
![// 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](/data/documents/9a9a16b2-364e-49ac-962e-f5c0ddf31239/page_17.png)
![{
// 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](/data/documents/9a9a16b2-364e-49ac-962e-f5c0ddf31239/page_18.png)
![// 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](/data/documents/9a9a16b2-364e-49ac-962e-f5c0ddf31239/page_19.png)
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