3-Laboratoriya ishi. Mavzu: Oddiy saralash algoritmlari. Saralash va izlash nima uchun kerak?

Ikki o’zgaruvchining qiymatini almashtirish.
Topilgan minimal elementni o’rniga qo’yish uchun uni hozir bu yerda turgan element bilan o’rnini almashtirish kerak. Buning uchun bizga ikki o’zgaruvchining qiymatlarini almashtirish kerak bo’ladi.

• 
  a va b ning qiymatlarini almashtirish uchun qo’shimcha t o’zgaruvhci kiritamiz va quyidagi amallarni bajaramiz:
  
• 
  t = a;
  
• 
  a = b;
  
• 
  b = t;
  

Qo’shimcha o’zgaruvchi kiritmasdan ham almashtirish mumkin buning uchun(o’zingiz tahlil qilib ko’ring):

• 
  a = a+b; (a+b, b);
  
• 
  b = a-b; (a+b, a);
  
• 
  a = a-b; (b, a);
  

C++ dasturlash tilida swap(a, b) funksiyasi orqali o’zgarucxhilar-ning qiymatlarini almashtirish mumkin.
#include
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for (int i = 0; i < n; i++)
cin>>a[i];
for (int i = 0; i < n-1; i++) {
int minPos = i;
for (int j = i+1; j < n; j++)
if (a[j] < a[minPos])
minPos = j;
int t = a[i];
a[i] = a[minPos];
a[minPos] = t;
}
for (int i = 0; i < n; i++)
cout<}
minPos – minimal son turgan indeks.

• 
  Ishlash vatqi ( ).
  
• 
  Taqqoshlashlar soni ( ).
  
• 
  Almashtirishlar soni .
  
• 
  Qo’shimcha xotira , ya’ni t o’zgaruvchi uchun.
  

Pufakcha usulida saralash(Bubble sort).

• 
  Umumiy n-1 marta jarayon bajariladi. Har safar ikkita qo’shni element taqqoslanadi.
  

Har bir iteratsiyada:

• 
  Agar ikki qo’shni element noto’g’ri tartibda joylashib qolgan bo’lsa, ularning o’rnini almashtiramiz.
  
• 
  Elementlar o’z o’rinlariga pufakga o’xshab siljib boradi.
  

Masalan:



Pufakchali saralash turg’un saralash hisoblanadi. Ya’ni qiymatlari bir xil bo’lgan elementlar saralangandan so’ng ham bir-biriga nisbatan tartibini saqlab qoladi. Berilgan massivdagi oldin joylashgan element saralangandan so’ng ham oldin joylashadi. Bu juda muhm hisoblanadi.
#include
using namespace std;
int main() {
int n;
cin>>n;
int a[n];
for (int i = 0; i < n; i++)
cin>>a[i];
for (int i = n-1; i >= 1; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j+1]) {
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
for (int i = 0; i < n; i++)
cout<return 0;
}

• 
  Ishlash vatqi ( ).
  
• 
  Taqqoshlashlar soni ( ).
  
• 
  Almashtirishlar soni ( ).
  
• 
  Qo’shimcha xotira .