Algoritmlar nazariyasining boshlang’ich tushunchalari

TSIKLNI SARALASH:: TSIKLNI SARALASH

Tsiklik saralash qiziqarli (amaliy nuqtai nazardan qimmatli), chunki massivning elementlari orasidagi o'zgarishlar element oxirgi o'rniga qo'yilganda sodir bo'ladi. Agar massivda qayta yozish juda qimmat bo'lsa va jismoniy xotirani hurmat qilish uchun massiv elementlariga o'zgartirishlar sonini kamaytirish kerak bo'lsa, bu foydali bo'lishi mumkin.

Bu shunday ishlaydi. Massivni takrorlang, keling, X ni ushbu tashqi tsikldagi keyingi katakchaga chaqiraylik. Va biz ushbu katakdan keyingi elementni massivning qaysi joyiga kiritishimiz kerakligini ko'rib chiqamiz. Siz kiritmoqchi bo'lgan joyda boshqa element mavjud, biz uni vaqtinchalik xotiraga yuboramiz. Buferdagi ushbu element uchun biz uning massivdagi o'rnini ham qidiramiz (va uni shu joyga kiritamiz va shu joydagi elementni buferga yuboramiz). Va buferdagi yangi raqam uchun biz bir xil amallarni bajaramiz. Bu jarayon qancha davom etishi kerak? Buferdagi keyingi element X yacheykaga aniq kiritilishi kerak bo'lgan element bo'lib chiqmaguncha (algoritmning asosiy tsiklidagi massivdagi joriy joy). Ertami-kechmi, bu moment paydo bo'ladi va keyin tashqi pastadirda siz keyingi katakka o'tishingiz va buning uchun xuddi shu tartibni takrorlashingiz mumkin.

Boshqa tanlov turlarida biz ularni oxirgi/birinchi qo'yish uchun yuqori/pastni qidiramiz. Ma'lum bo'lishicha, sikl tartibida birinchi navbatda pastki qatordagi minimal o'z-o'zidan topiladi, bir nechta boshqa elementlar massivning o'rtasida qandaydir o'zlarining munosib joylariga joylashtirilishi jarayonida.
Va bu erda algoritmik murakkablik ham O() ichida qoladi. n 2). Amalda dumaloq saralash oddiy saralashdan bir necha marta sekinroq ishlaydi, chunki siz massivni ko'proq o'tkazishingiz va tez-tez taqqoslashingiz kerak. Bu minimal mumkin bo'lgan qayta yozishlar uchun narx.

2. 
   InsertSort dasturida amallar soni va vaqt sarfini aniqlash va chiqarish
   

Insertion sort
Yana bir saralash usuli insertion sort bo`lib, u ham massiv elementlarini saralashda qulay usullardan biri hisoblanadi. Insertion sort saralash algoritmida asosan boshidan boshlab 2 ta elementini keyin 3 ta so`ngra 4 ta va hakozo n ta elementni tartiblanadi. (1) - qadamda dastlabki 2 ta element tartiblanganda faqat 2 ta element, (2) - qadamda 3 ta element tartiblanganda esa 3 - element dastlabki 2 tasi bilan, (3) - qadamda 4 ta element tartiblanganda 4 - element dastlabki 3 tasi bilan va hakozo (n -1) - qadamda n ta element tartiblanganda n- element dastlabki n tasi bilan taqqoslanadi. Bizning maqsad ham shu oxirgi qadamda bajarilgan vazifa ya’ni n ta elementni saralashdan iborat edi.
#include
using namespace std;
int main()
{ int *a, i, n, j, m;
cin >> n;
a=new int [n];
for(i=0; i
cin>>a[i];
for(i=1; i
{ j=i;
while(j>0&&(a[j]
{ m=a[j];
a[j]=a[j-1];
a[j-1]=m;
j--; } }
for(i=0; i
cout << a[i] << " ";
delete []a;
return 0; }
Dastur natijasi quyidagicha:

3. 
   Algoritmni loyihalshda “Masalani tushunish” bosqichi.
   

Algoritmlami tahlil qilish.

1.