Algoritm tushunchasi

{
int k = n;
bool swapped = true;
while (k != 1 || swapped == true)
{
k = getNextk(gap);
swapped = false;
for (int i=0; i
{
if (a[i] > a[i+k])
{
swap(a[i], a[i+k]);
swapped = true;
}
}
}
}
20 Saralash algoritmlari. Tanlash bo’yicha saralash (Selection sort)
Tanlash boʻyicha saralash (Selection sort). Birinchidan, siz
massivning kichik qismini koʻrib chiqishingiz va undagi maksimal (yoki
minimal) miqdorni topishingiz kerak. Keyin tanlangan qiymat birinchi
saralanmagan elementning qiymati bilan almashtiriladi. Ushbu qadam
massivning saralanmagan ichki qismlari tugamaguncha takrorlanishi
kerak.
Vaqt boʻyicha murakkabligi:
Eng yomon baho: O(n2)
Oʻrtacha baho: O(n2),
Eng yaxshi baho: O(n2)
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++)
61
{
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}
Ushbu algoritmlarning elementlari soni bir xil boʻlgan holatda
qanday vaqt ichida bajarilishi va sarflangan xotira hajmi haqidagi
qiyosiy jadval quyida berilgan.
Sinov oʻtkaziladigan kompyuter quyidagi xususiyatlarga ega: AMD
A6-3400M 4x1.4 GHz, 8 Gb operativ xotira, Windows 10 x64 build
10586.36.
21 Saralash algoritmlari. Birlashtirib saralash algoritmi (Merge sort). “Bo’lib tashla va hukmronlik qil” strategiyasi
Merge sort algoritmi. Birlashtirib saralash (Merge sort) –
tartiblashning tezkor bajariladigan algoritmlaridan biri. Ushbu tartiblash
“boʻlib tashla va hukmronlik qil” prinsipining yaxshi namunasidir.
Birinchidan, vazifa bir nechta kichik topshiriqlarga boʻlinadi. Keyin
ushbu vazifalar rekursiv chaqiruv yordamida yoki toʻgʻridan-toʻgʻri
ularning hajmi yetarlicha kichik boʻlsa hal qilinadi. Nihoyat, ularning
yechimlari birlashtirilib, asl muammoning echimi olinadi.