Oʻzbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti mavzu: Saralash usul algoritmlarini tadqiq etish

OʻZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA

KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT

TEXNOLOGIYALARI UNIVERSITETI

Mavzu: Saralash usul algoritmlarini tadqiq etish.Saralashga doir misollarni hal qilish.

Bajardi: Saypidinov Sadriddin
Tekshirdi: Bo’riyev Yusuf

Toshkent-2022
ISHNING MAQSADI
Ishni bajarishdan maqsad :biz Insertion Sort usuli yordamidamalumotlarni saralashni o’rganamiz.

Nazariy malumotlar
Qo'shishni saralash - taqqoslash yo'li bilan bir vaqtning o'zida yakuniy tartiblangan massivni (yoki ro'yxatni) bitta elementni yaratadigan oddiy tartiblash algoritmi . Bu tezkor saralash , yig'ish tartiblash yoki birlashtirish kabi ilg'or algoritmlarga qaraganda katta ro'yxatlarda unchalik samarali emas . Biroq, kiritish tartibi bir qator afzalliklarga ega:

• 
  Oddiy amalga oshirish: Jon Bentley optimallashtirilganda besh qatorli uch qatorli C / C++ versiyasini ko'rsatadi . ^[1]
  
• 
  Boshqa kvadratik (ya'ni, O ( n ² )) tartiblash algoritmlari kabi (juda) kichik ma'lumotlar to'plamlari uchun samarali
  
• 
  Tanlovni saralash yoki qabariqli tartiblash kabi boshqa oddiy kvadratik algoritmlarga qaraganda amalda samaraliroq
  
• 
  Moslashuvchan , ya'ni allaqachon sezilarli darajada tartiblangan ma'lumotlar to'plamlari uchun samarali: kirishdagi har bir element o'zining tartiblangan joyidan k dan ortiq bo'lmagan joyda bo'lsa , vaqt murakkabligi O ( kn ) ga teng.
  
• 
  Barqaror ; ya'ni, teng tugmalar bilan elementlarning nisbiy tartibini o'zgartirmaydi
  
• 
  joyida ; ya'ni, faqat doimiy miqdorda O (1) qo'shimcha xotira maydoni talab qiladi
  
• 
  Onlayn ; ya'ni ro'yxatni qabul qilganidek saralashi mumkin
  

Odamlar kartalarni ko'prik qo'lida qo'lda saralashda, ko'pchilik kiritish tartiblashiga o'xshash usuldan foydalanadi. ^[2
Kiritish tartibi takrorlanadi, har bir takrorlashda bitta kirish elementi sarflanadi va saralangan chiqish roʻyxatini kengaytiradi. Har bir iteratsiyada qo'shish tartiblash kiritilgan ma'lumotlardan bitta elementni olib tashlaydi, tartiblangan ro'yxatda joylashgan joyni topadi va u erga qo'yadi. U hech qanday kirish elementlari qolmaguncha takrorlanadi.
Saralash odatda massivni takrorlash, uning orqasida tartiblangan ro'yxatni ko'paytirish orqali joyida amalga oshiriladi. Har bir massiv pozitsiyasida u yerdagi qiymatni saralangan ro'yxatdagi eng katta qiymatga nisbatan tekshiradi (uning yonida, oldingi massiv pozitsiyasida tekshirilgan). Agar kattaroq bo'lsa, u elementni joyida qoldiradi va keyingisiga o'tadi. Agar kichikroq bo'lsa, u tartiblangan ro'yxatdagi to'g'ri pozitsiyani topadi, bo'sh joy qoldirish uchun barcha katta qiymatlarni yuqoriga siljitadi va o'sha to'g'ri joyga kiritadi.
K iteratsiyadan so'ng hosil bo'lgan massiv birinchi k + 1 yozuvlar tartiblangan xususiyatga ega (birinchi yozuv o'tkazib yuborilganligi sababli "+1"). Har bir iteratsiyada kirishning qolgan birinchi yozuvi olib tashlanadi va natijaga to'g'ri holatda kiritiladi, natijada natija uzaytiriladi:

aylanadi

x dan katta bo'lgan har bir element o'ngga ko'chiriladi, chunki u x bilan solishtiriladi .
Massivlarda ishlaydigan qo'shish tartibining eng keng tarqalgan variantini quyidagicha ta'riflash mumkin:

1. 
   Aytaylik , massiv boshida tartiblangan ketma-ketlikka qiymat kiritish uchun mo‘ljallangan Insert nomli funksiya mavjud . U ketma-ketlikning oxiridan boshlab va yangi element uchun mos joy topilmaguncha har bir elementni bir joydan o'ngga siljitish orqali ishlaydi. Funktsiya massivdagi tartiblangan ketma-ketlikdan keyin darhol saqlangan qiymatni qayta yozishning yon ta'siriga ega.
   
2. 
   Qo'shishni saralashni amalga oshirish uchun massivning eng chap elementidan boshlang va har bir duch kelgan elementni o'zining to'g'ri joyiga kiritish uchun Insert -ni chaqiring. Element kiritilgan tartibli ketma-ketlik allaqachon tekshirilgan indekslar to'plamida massivning boshida saqlanadi. Har bir kiritish bitta qiymatning ustiga yoziladi: kiritilayotgan qiymat.
   

Masala sharti: Insertion Sort usuli yordamida saralash
#include
//Funksiya yordamida massivni tartiblash
//qo'shish tartibi
void insertionSort(int arr[],int n)
{
int i,key ,j;
for(i=1;i {
key=arr[i];
j=i-1;
//Move elements of arr[0..i-1],
//that are greater than key,to one
//position ahead of their
//current position
while(j>= 0 && arr[j] >key)
{
arr[j+1]= arr[j];
j=j-1;
}
arr[j+1]=key;
}
}
//A utility function to print an array
//of size n
void printArray(int arr[],int n)
{
int i;
for (i=0;i cout< cout<}
//Driver code
int main()
{
int arr[]={12,11,13,5,6};
int N=sizeof(arr) /sizeof(arr[0]);
insertionSort(arr,N);
printArray(arr,N);
return 0;
}
//THis is code is contributed by rathbhupendra