|
Oʻzbekiston respublikasi oliy va o‘rta maxsusta’lim vazirligi
|
| bet | 8/16 | | Sana | 15.11.2023 | | Hajmi | 29,81 Mb. | | #99092 |
Bog'liq Dilshoda Algoritm mustaqil6
Birinchi qadam:
Dastlab, massivning dastlabki ikki elementi kiritish tartibida solishtiriladi.
Bu erda 12 11 dan katta, shuning uchun ular o'sish tartibida emas va 12 o'zining to'g'ri joyida emas. Shunday qilib, 11 va 12 ni almashtiring.
Shunday qilib, hozircha 11 tartiblangan pastki qatorda saqlanadi.
Ikkinchi o'tish:
Endi keyingi ikkita elementga o'ting va ularni solishtiring
Bu erda 13 12 dan katta, shuning uchun ikkala element ham o'sish tartibida ko'rinadi, shuning uchun almashtirish sodir bo'lmaydi. 12, shuningdek, 11 bilan birga tartiblangan pastki qatorda saqlanadi
Uchinchi o'tish:
Endi tartiblangan kichik massivda ikkita element mavjud, ular 11 va 12
Keyingi ikkita elementga o'tish - 13 va 5
Almashtirilgandan so'ng, 12 va 5 elementlar tartiblanmaydi, shuning uchun yana almashtiriladi
Bu erda yana 11 va 5 tartiblashtirilmaydi, shuning uchun yana almashtiring
Bu erda 5 to'g'ri holatda
To'rtinchi o'tish:
Endi tartiblangan kichik massivda mavjud bo'lgan elementlar 5, 11 va 12 dir
Keyingi ikkita elementga o'tish 13 va 6
Shubhasiz, ular tartiblanmagan, shuning uchun ikkalasini almashtirishni amalga oshiring
Endi 6 12 dan kichik, shuning uchun yana almashtiring
Nihoyat, massiv to'liq tartiblangan.
Tasvirlar:
Qo'shishning psevdo kodi
procedure insertionSort(arr):
for i = 1 to n-1
key = arr[i]
j = i-1
while j >= 0 and arr[j] > key
swap arr[j+1] with arr[j]
j = j - 1
end while
end for
end function
Bu algoritm massivning saralanmagan qismidan elementni qayta-qayta olib, massivning tartiblangan qismidagi toʻgʻri joyiga qoʻyish orqali elementlar massivini saralaydi.
Quyida amalga oshirish ko'rsatilgan:
// C# program for implementation of Insertion Sort
using System;
class InsertionSort {
// Function to sort array
// using insertion sort
void sort(int[] arr)
{
int n = arr.Length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int 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
// array of size n
static void printArray(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
Console.Write("\n");
}
// Driver Code
public static void Main()
{
int[] arr = { 12, 11, 13, 5, 6 };
InsertionSort ob = new InsertionSort();
ob.sort(arr);
printArray(arr);
}
}
Chiqish
5 6 11 12 13
Vaqt murakkabligi: O(N^2)
Yordamchi fazo: O(1)
Kiritish tartibining murakkablik tahlili: Kiritish tartibining vaqt murakkabligi
Qo'shish tartibining eng yomon vaqt murakkabligi O ( N^2)
Qo‘shish tartibining o‘rtacha ish vaqti murakkabligi O ( N^2)
Eng yaxshi holatning vaqt murakkabligi O(N) dir .
Kiritish tartibining fazoviy murakkabligi
Insertion Sort rekursiv yondashuvining yordamchi fazoviy murakkabligi rekursion stek tufayli O(n) ga teng.
Insertion Sort algoritmi qachon ishlatiladi?
Elementlar soni kichik bo'lsa, kiritish tartiblash qo'llaniladi. Kirish massivi deyarli tartiblangan bo'lsa, to'liq katta massivda faqat bir nechta elementlar noto'g'ri joylashtirilganda ham foydali bo'lishi mumkin..
Tezkor saralash
QuickSort - bu Ajra va zabt et algoritmiga asoslangan saralash algoritmi bo'lib , u elementni aylanma sifatida tanlaydi va berilgan massivni saralangan massivda to'g'ri joyiga qo'yish orqali tanlangan pivot atrofida ajratadi.
Tezkor saralash
QuickSort qanday ishlaydi?
QuickSort -dagi asosiy jarayon - bu partition(). Bo'limlarning maqsadi - pivotni (har qanday elementni aylanma sifatida tanlash mumkin) tartiblangan massivdagi to'g'ri joyiga qo'yish va barcha kichikroq elementlarni pivotning chap tomoniga va barcha katta elementlarni pivotning o'ng tomoniga qo'yishdir. .
Ushbu bo'lim rekursiv tarzda amalga oshiriladi va nihoyat massivni tartiblaydi. Yaxshiroq tushunish uchun quyidagi rasmga qarang.
Bo'lim algoritmi:
Bo'limni ajratishning ko'p usullari bo'lishi mumkin. Quyidagi psevdo-kod CLRS kitobida keltirilgan usulni qabul qiladi. Mantiq oddiy, biz eng chap elementdan boshlaymiz va kichikroq (yoki teng) elementlar indeksini i kabi kuzatib boramiz . Ketish paytida kichikroq elementni topsak, joriy elementni arr[i] bilan almashtiramiz. Aks holda, biz joriy elementni e'tiborsiz qoldiramiz.
Tez tartiblash uchun psevdokod:
/* past –> Boshlanish indeksi, yuqori –> Yakuniy indeks */
quickSort(arr[], low, high) {
if (past < high) {
/* pi boʻlish indeksi boʻlsa, arr[pi] hozir toʻgʻri joyda */
pi = boʻlim(arr, past, baland);
QuickSort(arr, past, pi – 1); // oldin pi
quickSort(arr, pi + 1, baland); // pi dan keyin
}
}
Partition() uchun psevdokod:
/* Bu funksiya oxirgi elementni pivot sifatida qabul qiladi, aylanma elementni tartiblangan massivda o‘zining to‘g‘ri joyiga qo‘yadi va kichikroq (pivotdan kichik) hammasini pivotning chap tomoniga va barcha kattaroq elementlarni pivotning o‘ng tomoniga joylashtiradi */
bo'lim (arr[], past, baland)
{
// pivot (to'g'ri joyga joylashtiriladigan element)
pivot = arr[yuqori];
i = (past – 1) // Kichikroq element indeksi va
hozirgacha topilgan pivotning // o‘ng holatini bildiradi.
uchun (j = past; j <= yuqori- 1; j++){
// Agar joriy element pivotdan kichik bo'lsa
if (arr[j] < pivot){
i++; // kichikroq elementning o'sish indeksi
arr[i] va arr[j]
}
}
almashtirish arr[i + 1] va arr[yuqori])
qaytish (i + 1)
}
Bo'limning tasviri():
Misolni ko'rib chiqamiz: arr[] = {10, 80, 30, 90, 40, 50, 70}
Indekslar: 0 1 2 3 4 5 6
past = 0, baland = 6, pivot = arr[h] = 70
Kichikroq element indeksini ishga tushiring, i = -1
Pivotni birinchi element bilan solishtiramiz:
Elementlarni j = pastdan yuqori-1 ga o'tkazing
|
| |
