Algoritmdan nazorat savollariga javoblar Algoritm nima

Tanlash orqali saralash(Selection sort)

• 
  Algoritm ideasi massivning allaqachon saralangan qismiga saralanmagan qismidan navbatdagi eng kichik elementni qo’shib borish.
  
• 
  4 9 7 6 2 3 berilgan massiv.
  
• 
  1-qadam. 2<->4 2 9 7 6 4 3
  
• 
  2-qadam. 3<->9 2 3 7 6 4 9
  
• 
  3-qadam. 4<->7 2 3 4 6 7 9
  
• 
  4-qadam. 6<->6 2 3 4 6 7 9
  
• 
  5-qadam. 7<->7 2 3 4 6 7 9
  
• 
  (n-1) ta qadam yetarli.
  
• 
  Ishlash vaqti O(n²)
  
• 
  Asosiy masala massivning tartiblanmagan qismidan minimal element o’rnini aniqlash.
  
• 
  for (int i = 1; i < n; i++) {
  
• 
  int min_id = i;
  
• 
  for (int j = i+1; j <= n; j++) {
  
• 
  if (a[j] < a[min_id])
  
• 
  min_id = j;
  
• 
  }
  
• 
  swap(a[i], a[min_id]);
  
• 
  }
  

14.Pufakcha usulida saralash algoritmini tushuntirib bering.

• 
  Algoritm saralanayotgan massivni bir nechta marta o’tib chiqishdan iborat.
  
• 
  Har bir o’tib chiqishda ketma-ket va notog’ri tartibda joylashgan elementlar o’rni almashtiriladi.
  
• 
  Noto’g’ri tartib: if a[j]>a[j+1] -> swap(a[j], a[j+1]);
  
• 
  4 9 7 6 2 3 berilgan massiv.
  
• 
  1-qadam.9<->7,9<->6, 9<->2, 9<->3
  

4 7 6 2 3 9

• 
  2-qadam.7<->6,7<->2, 7<->3
  

4 6 2 3 7 9

• 
  3-qadam 6<->2,6<->3
  

4 2 3 6 7 9

• 
  4-qadam 4<->2,4<->3
  

2 3 4 6 7 9

• 
  5-qadam (almashinish yo’q)
  

2 3 4 6 7 9

• 
  Ishlash vaqti O(n²)
  

• 
  for (int i = n; i >= 2; i--) {
  
• 
  for (int j = 1; j < i; j++) {
  
• 
  if (a[j] > a[j+1]) {
  
• 
  swap(a[j], a[j+1]);
  
• 
  }
  
• 
  }
  
• 
  } void bubbleSort(int arr[], int n)
  
• 
  {
  
• 
  if (n == 1)
  
• 
  return;
  
• 
  for (int i=0; i
• 
  if (arr[i] > arr[i+1])
  
• 
  swap(arr[i], arr[i+1]);
  
• 
  bubbleSort(arr, n-1);
  
• 
  }
  

15.Saralangan ikkita massiv qanday qilib birlashtiriladi?

Saralangan massivlarni birlashtirish.

• 
  Ikkita saralangan massiv berilgan. Ularni birlashtirib shunday massiv hosil qilish qilish kerakki, u yana saralangan bo’lsin.
  
• 
  Xar safar hali ikki massivning hali ko’rilmagan qismlaridagi birinchi ikki elementni taqqoslaymiz. Ulardan kichigini olamiz. Bu jarayonni toki bitta massivning chetigacha chiqmagunga qadar davom ettiramiz. Ortib qolgan massiv elementlarini esa to’g’ridan to’g’ri natijaviy massiv iziga berilgan tartibda joylashtirib qo’yamiz.
  

Masalan quyida ikki saralangan massivlarni birlashtirib, saralangan bitta massiv hosil qilishni ko’rib chiqaylik: